[c++] sort

---

sort 함수

• <algorithm> 해더파일에 속해 있다.

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> vec = {4, 2, 3, 1, 5};
    std::sort(vec.begin(), vec.end()); //기본 오름차순 정렬
    
    for (int n : vec) {
        std::cout << n << " "; // 1 2 3 4 5 출력
    }
    return 0;
}

👆 위와 같은 형식으로 사용한다.

vec의 요소들이 오름차순으로 정렬 된다.  두 개의 반복자를 인수로 받는다.

첫 번쨰는 범위의 시작을, 두번쨰는 범위의 끝을 나타낸다.

---

기본 사용법

sort(arr,arr+n); //배열 정렬
sort(vec.begin(),vec.end()); //백터 정렬

---

시간 복잡도

: 시간 복잡도는 O(NlogN)이다.

 

'sort' 함수는 퀵, 힙, 삽입 정렬을 혼합하여 사용한다. 최악의 경우에도 O(NlogN)를 보장한다.

👇혼합하는 이유

1. 퀵 정렬 (Quick Sort)

• 장점: 편균 시간 복잡도가 O(NlogN)으로 빠르다. 특히, 실생활 데이터에서 효율적이다.
• 단점: 최악의 경우 O(N^2) 이  될 수 있따. (피벗 선택이 나쁠떄)
• 사용 이유: 평균적으로 빠르고 효율적이어서 일반적인 경우에 좋다.

 

2. 힙 정렬 (Heap Sort)

• 장점: 항상 O(NlogN)의 시간 복잡도를 보장한다.
• 단점: 메모리 접근 패턴이 비효율 적일 수 있따.
  퀵 정렬에 비해 실생활 데이터에서 성능이 떨어질 수 있다, 
• 사용 이유: 퀵 정렬의 최악의 상황을 보완할떄 사용, 데이터가 매우 나쁠떄 안정적임

 

3. 삽입 정렬 (Insertion Sort)

• 장점: 거의 정렬된 데이터에선 O(N)의 시간복잡도 이다, 소규모 데이터에서 빠르다.
• 단점: 큰 데이터 집합에선 O(N^2) 이다.
• 사용 이유: 소규모 데이터 집합이나, 거의 정렬될떄, 작은 부분을 정렬할 떄 사용한다.

---

pair의 정렬

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
   	vector<pair<int, int>> vec = { {1, 2}, {3, 1}, {2, 3}, {1, 4} };

    // 기본 정렬: 첫 번째 요소를 기준으로, 첫 번째 요소가 같으면 두 번째 요소를 기준으로 정렬
    sort(vec.begin(), vec.end());


    return 0;
}

기본적으론 첫 번째 요소를 기준으로 정렬한다.

그러나 첫번쨰 요소가 동일하면 두번쨰 요소를 기준으로 정렬한다.

 

사용자 정의 비교 함수를 사용하여 원하는 방식으로 정렬할 수 있따.

#include <iostream>
#include <vector>
#include <algorithm>

// 사용자 정의 비교 함수: 문자열의 길이를 기준으로 정렬, 길이가 같다면 사전 순으로 정렬
bool comp(const pair<std::string, int>& a, const pair<string, int>& b) {
    if (a.first.length() == b.first.length()) {
        return a.first < b.first; // 길이가 같다면 사전 순으로 비교
    }
    return a.first.length() < b.first.length(); // 기본적으로 문자열 길이로 비교
}

int main() {
  	vector<pair<string, int>> vec = { {"apple", 3}, {"banana", 2}, {"pear", 5}, {"kiwi", 4} };

    // 문자열의 길이와 사전 순으로 정렬
    sort(vec.begin(), vec.end(), comp);

    return 0;
}

---

내림 차순 정렬

기본적으로 sort함수는 오름차순으로 정렬한다.

아래는 내림차순 정렬을 하는 방법들 이다.

사용자 정의 비교 함수

// 사용자 정의 비교 함수: 내림차순 정렬
bool customCompare(int a, int b) {
    return a > b; // a가 b보다 클 때 true를 반환하여 내림차순으로 정렬
}

int main() {
    std::vector<int> vec = {4, 2, 5, 1, 3};

    // 사용자 정의 비교 함수를 사용한 정렬
    std::sort(vec.begin(), vec.end(), customCompare);

    // 결과 출력
    for (int num : vec) {
        std::cout << num << " ";
    }

    return 0;
}

---

greter<int>()

int main() {
    std::vector<int> vec = {4, 2, 5, 1, 3};

    // std::greater를 사용하여 내림차순 정렬
    std::sort(vec.begin(), vec.end(), std::greater<int>());

    // 결과 출력
    for (int num : vec) {
        std::cout << num << " ";
    }

    return 0;
}

---

끝