C++ vector 정렬

🤖 Algorithm

---

🟦 C++ vector 정렬

🔵 크기 기준 정렬

algoritm 라이브러리의 sort 함수 활용

std::sort 함수는 컨테이너의 요소를 정렬하는 데 사용
-> Quick Sort, Merge Sort, Heap Sort 등의 효율적인 알고리즘을 기반으로 동작

sort(RandomAccessIterator first, RandomAccessIterator last, Comparator)

RandomAccessIterator : 임의 위치로 직접 접근할 수 있는 반복자
반복자 : 컨테이너의 요소에 접근하고 조작하기 위한 일종의 포인터

RandomAccessIterator first : 벡터의 첫 번째 요소를 가리키는 반복자
RandomAccessIterator last : 벡터의 끝 다음을 가리키는 반복자
Comparator : true -> 유지 (default로 '<' 연산자 사용)

#include <algorithm>
//...
vector<int> nums;
//...

//오름차순
sort(nums.begin(), nums.end());

//내림차순
//vector의 자료형과 greater의 자료형 일치 주의
//std::greator<int>()는 함수 객체로 첫 번째 값이 두 번째 값보다 크면 true 반환
sort((nums.begin(), nums.end(), greater<int>());

//Comparaor 사용한 내림차순 정렬
bool greator(int a, int b) {
	return a>b;
}

int main() {
	//...
    sort(nums.begin(), nums.end(), greator);
    //...
}

🔵 빈도 기준 정렬

sort함수와 map, pair를 사용하여 정렬

vector<int> nums;
//nums에 값 할당

// 각 값을 key로 하여 빈도 수 만큼 +1 
map<int, int> prequency;

for(int num : nums)
{
	frequency[num]++;
}

// map -> vector로 변환
vector<pair<int, int>> frequencyVector(frequency.begin(), frequendcy.end());

// 빈도수를 기준으로 정렬
sort(frequencyVector.begin(),frequencyVector.end(),
		[](const auto &left, const auto &right){return left.second > right.second;}
);

람다 함수

[](const auto &left, const auto &right) {

	return left.second > right.second;
}

[](const auto &left, const auto &right) -> 람다 함수의 시작을 알림
const auto &left, &right -> 람다 함수의 매개변수, 정렬될 두 요소
left.second > right.second 이면 true 반환 -> 내림차순 정렬

🔵 예제 - 백준 BOJ 2108번 통계학

#define _CRT_SECURE_NO_WARNINGS

using namespace std;

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>

int main() 
{

    int N;
    scanf("%d",&N);

    int avg,mid,most,dif;
    vector<int> nums;
    map<int, int> frequency;

    for(int i=0;i<N;i++)
    {
        int num;
        scanf("%d",&num);
        nums.push_back(num);
    }

    if(N==1)
    {
        avg=nums[0];
        mid=nums[0];
        most=nums[0];
        dif=0;
    }

    else
    {
        for(int num : nums)
        {
            frequency[num]++;
        }

        vector<pair<int,int>> frequencyVector(frequency.begin(), frequency.end());

        sort(frequencyVector.begin(),frequencyVector.end(),[](const auto &left, const auto &right)
        {
            return left.second > right.second;
        });

        sort(nums.begin(),nums.end());

        int sum=0;

        for(int i=0;i<N;i++)
        {
            sum+=nums[i];
        }

        double double_avg = static_cast<double>(sum)/N;

        avg =round(double_avg);

        mid=nums[(N-1)/2];

        if (frequencyVector.size() > 1 && frequencyVector[0].second == frequencyVector[1].second) 
        {
             most = frequencyVector[1].first;
        }

        else
        {
            most = frequencyVector[0].first;
        }

        dif=nums[N-1]-nums[0];
    }

    printf("%d\n",avg);
    printf("%d\n",mid);
    printf("%d\n",most);
    printf("%d\n",dif);

    return 0;

}