[STL] Algorithm - 정렬 알고리즘

치치·2025년 7월 22일

stl

STL

목록 보기

19/21

Algorithm 알고리즘

정렬 알고리즘

'변경 알고리즘'의 특수한 형태로, 특정 정렬 기준으로 원소의 순서를 변경하며 정렬한다.

알고리즘 함수	사용 형태 (인자)	역할
partition	`partition(begin, end, cond)`	조건에 따라 참인 원소를 앞쪽으로 재배열 (순서 X)
stable_partition	`stable_partition(begin, end, cond)`	조건에 따라 앞쪽으로 재배열 (순서 유지 O)
make_heap	`make_heap(begin, end)` `make_heap(begin, end, comp)`	범위를 힙 구조(기본 최대힙)로 변환
push_heap	`push_heap(begin, end)` `push_heap(begin, end, comp)`	새로 추가된 마지막 원소 포함해 힙 재구성
pop_heap	`pop_heap(begin, end)` `pop_heap(begin, end, comp)`	힙의 첫 원소를 뒤로 보내고 재구성
sort_heap	`sort_heap(begin, end)` `sort_heap(begin, end, comp)`	힙 구조를 정렬된 순서로 변환
nth_element	`nth_element(begin, nth, end)` `nth_element(begin, nth, end, comp)`	nth 위치 원소 기준으로 앞은 작게, 뒤는 크게 배치
sort	`sort(begin, end)` `sort(begin, end, comp)`	범위 정렬 (기본 오름차순) ➡ 퀵 정렬
stable_sort	`stable_sort(begin, end)` `stable_sort(begin, end, comp)`	순서를 유지 정렬 ➡ 병합 정렬
partial_sort	`partial_sort(begin, mid, end)` `partial_sort(begin, mid, end, comp)`	구간 [mid - begin)만큼의 원소를 정렬하여 순차열에 배치
partial_sort_copy	`partial_sort_copy(1begin, 1end, 2begin, 2end)` `partial_sort_copy(1begin, 1end, 2begin, 2end, comp)`	원본 범위에서 (2end - 2begin)개를 정렬하여 `[2begin(), 2end())`로 복사

힙 관련 알고리즘

🔷 Heap 자료구조에 대한 간단한 복습

노드 관련된 내용은 아래의 블로그에서 다룰 것이고, 이번 글에서는 알고리즘 stl 사용만 다룰 것이다.

https://velog.io/@yangju058/자료구조-Heap-우선스택-큐

🔹 Heap 자료구조는 완전 이진 트리 구조로, 중복을 허용한다.

➡ 즉, 부모노드가 자식보다 크거나 같아야한다. 기본은 '최대힙'이기 때문에 부모노드가 자식보다 커야한다.
➡ 완전 이진 트리 구조이기 때문에, 왼쪽부터 노드가 채워져 있어야 한다.

'최대힙' : 부모노드 > 자식노드
'최소힙' : 부모노드 < 자식노드

🔹 완전 이진 트리 != 이진 탐색 트리

이름이 비슷하다고 착각하지 말자!!

완전 이진 트리 : 부모노드가 자식보다 크거나 같아야 한다.
이진 탐색 트리 : 왼쪽노드 < 부모노드 < 오른쪽노드가 성립되야한다.

🔹 힙의 연산

추가연산 insert() : 완전 이진 트리 가장 끝에 원소 추가 & 힙 규칙 유지
제거연산 Remove() : 루트 노드 삭제 & 힙 규칙 유지

🔹 heap 사용 주의점

힙 자료구조로 컨테이너의 내부 순서를 바꿔 힙의 규칙을 만족하게 하는 것이다.
내부 순서만 바꾸는 것이기 때문에, 값을 넣거나 제거하는 것은 컨테이너의 멤버함수를 사용해야한다.
힙 자료구조는 정렬되지 않기 때문에 넣은 순서대로 힙 구조만 유지하도록 순서가 바뀌는 것이다. ➡ 정렬을 사용하려면 sort_heap()을 사용한다.

아래에서 다뤄보자!

📌make_heap()

기본 최대힙이라 가장 원소값이 큰 60이 루트노드가 된다. ➡ 모든 자식노드는 부모노드보다 작다.

int main() 
{
    vector<int>v;    // 10 20 30 40 50 60

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
    v.push_back(60);

    make_heap(v.begin(), v.end());

    for (int c : v)
    {
        cout << c << " "; // 60 50 30 40 20 10
    }
}

📌 push_heap()

push_heap()은 실제 원소의 값을 추가하는 것이 아닌, 마지막 요소만 힙에 맞게 정렬하는 것이다.
➡ 반드시 값을 추가하기 전에 컨테이너의 추가함수를 사용한 뒤 push_heap()을 진행한다.

값 추가 시, 완전 이진 트리 노드의 가장 마지막 부분에 추가되고, 힙 규칙에 따라 원소의 정렬이 진행된다.

🔹 make_heap() / push_heap()

➡ 값을 추가 후 힙 알고리즘에 따른 차이

방식	설명	시간 복잡도	결과
`push_back()` → `push_heap()`	마지막 요소만 힙에 맞게 정렬	O(log N)	✅ 힙 조건 유지
`push_back()` → `make_heap()`	전체를 다시 힙 구조로 재배열	O(N)	✅ 힙 조건 유지 (하지만 느림)

int main() 
{
    vector<int>v;    // 10 20 30 40 50

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

    make_heap(v.begin(), v.end());

    v.push_back(60); // 60 삽입

    push_heap(v.begin(), v.end()); // 힙 원소 추가

    for (int c : v)
    {
        cout << c << " "; // 60 40 50 10 20 30
    }
}

📌 pop_heap()

pop_heap()은 push_heap()과 동일하게 실제 원소값에서 빼는 것이 아닌,
단지 루트 노드와 마지막 노드를 swap한 뒤 힙 범위를 하나 줄인 상태로 재정렬 한 것이다.
➡ 실제 원소를 제거하려면 pop_heap()진행 후 컨테이너의 제거함수를 사용한다.

int main() 
{
    vector<int>v;    // 10 20 30 40 50 60 

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
    v.push_back(60);

    make_heap(v.begin(),v.end());

    pop_heap(v.begin(), v.end()); // 마지막 원소 <-> 루트 노드 

    for (int c : v)
    {
        cout << c << " "; // 50 40 30 10 20 60
    }
    
    // 실제 원소 제거 
    v.pop_back();         // 50 40 30 10 20
}

📌 sort_heap()

sort_heap()은 말그대로 '힙을 기반으로 정렬하는 것'이다.
➡ make_heap()으로 생성한 순차열(힙 구조)에서만 동작 가능

정렬 후의 구조 상태는 힙 구조를 따르지 않게 된다.
➡ 내부적으로 반복해서 pop_heap()을 통해 재정렬된다.

int main() 
{
    vector<int>v;    // 10 20 30 40 50 60 

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);
    v.push_back(60);

    make_heap(v.begin(),v.end());

    sort_heap(v.begin(), v.end()); // 기본 오름차순 정렬 

    for (int c : v)
    {
        cout << c << " "; // 10 20 30 40 50 60
    }
}

📌 조건자 버전 heap 알고리즘

기본 함수 객체는 less<int>()인 오름차순으로 되어 있는데, 함수 객체 greater<int>()를 사용하면 내림차순으로 정렬된다.

make_heap()으로 힙구조 생성 시 greater<int>()를 사용하게 되면 최소힙으로 구성된다.
➡ '최소힙' : 부모노드 < 자식노드

int main() 
{
    vector<int>v;    // 10 20 30 40 50 

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

    make_heap(v.begin(),v.end(), greater<int>()); // 최소힙

    for (int c : v)
    {
        cout << c << " "; // 10 20 30 40 50
    }

    v.push_back(5);
    
    push_heap(v.begin(), v.end(), greater<int>()); // 최소힙 연산

    for (int c : v)
    {
        cout << c << " "; // 5 20 10 40 50 30
    }

    sort_heap(v.begin(), v.end(), greater<int>()); // 내림차순 정렬

    for (int c : v)
    {
        cout << c << " "; // 50 40 30 20 10 5
    }
}

📌 nth_element()

순차열의 원소 중 n개의 원소를 선별하고자 할 때 사용한다.

🔹 nth_element(b, m, e);
➡ [b, e) 구간의 원소 중 (m - b)개 만큼의 원소를 선별하여 순차열에 놓이게 한다.
(b : 시작 반복자, m : 원하는 구간 반복자, e : 끝 반복자)

🔹 전체 정렬은 하지 않지만, m을 기준으로 범위를 나누는 느낌으로 사용한다.

➡ m 이전에 값들은 m번째 원소를 기준으로 작은 값들로 위치
➡ m 이후의 값들은 m번째 원소를 기준으로 큰 값들로 위치

int main() 
{
    vector<int>v;

    for (int i = 0; i < 100; i++)
    {
        v.push_back(rand() % 1000);
    }

    // 20개 선별 : (v.begin() + 20 - v.begin())
    nth_element(v.begin(), v.begin() + 20, v.end());


    cout << "v[상위 20개] : ";

    for (int i = 0; i < 20; i++) cout << v[i] << " ";


    cout << endl << "v[하위 80개] : ";

    for (int i = 20; i < v.size(); i++) cout << v[i] << " ";

}

🔷 sort & stable_sort & partial_sort

sort
➡ 퀵 정렬 (NlogN) https://velog.io/@yangju058/알고리즘-Quick-Sort
stable_sort
➡ 병합 정렬 (NlogN, 최악N²) , 상대적 순서 유지 https://velog.io/@yangju058/알고리즘-Merge-Sort
partial_sort
➡ 퀵 정렬 (NlogN)

📌 sort() - 퀵 정렬

순차열의 상대적인 순서를 유지하지 않는다.

Less<int>() : 기본 내림차순 정렬
Greater<int>() : 오름차순 정렬

int main() 
{
    vector<int>v;
    
    v.push_back(10);
    v.push_back(40);
    v.push_back(30);
    v.push_back(20);
    v.push_back(50);

    sort(v.begin(), v.end()); // 오름차순 정렬

    for (int c : v) cout << c << " "; // 10 20 30 40 50

    sort(v.begin(), v.end(), greater<int>()); // 내림차순 정렬

    for (int c : v) cout << c << " "; // 50 40 30 20 10
}

📌 stable_sort() - 병합 정렬

순차열의 상대적인 순서를 유지한다.

int main() 
{
    vector<int>v;
    
    v.push_back(10);
    v.push_back(40); // 40_A
    v.push_back(40); // 40_B
    v.push_back(30);
    v.push_back(20); // 20_A
    v.push_back(20); // 20_B
    v.push_back(50);

    stable_sort(v.begin(), v.end()); // 오름차순 정렬

    for (int c : v) cout << c << " "; // 10 20A 20B 30 40A 40B 50

    sort(v.begin(), v.end(), greater<int>()); // 내림차순 정렬

    for (int c : v) cout << c << " "; // 50 40A 40B 30 20A 20B 10
}

📌 partial_sort() - 힙 정렬

특정 구간만 정렬을 원할 때 사용한다.

🔹 partial_sort(b, m, e);
➡ [b, e) 구간의 원소를 [b, m)의 순차열에 원소를 정렬한다.
🔹 정렬되지 않은 나머지 부분은 순서도 보장되지 않는다.
➡ 오직 앞쪽 m - b개의 원소만 정렬되고 나머지는 정렬되지 않는다.

int main() 
{
    vector<int>v;
    
    v.push_back(10);
    v.push_back(40);
    v.push_back(30);
    v.push_back(20);
    v.push_back(50);

    partial_sort(v.begin(), v.begin()+2, v.end()); // 원소 2개만 정렬

    for (int c : v) cout << c << " "; // 정렬됨(10 20) 정렬안됨(40 30 50)

    partial_sort(v.begin(), v.begin() +2, v.end(), greater<int>()); // 원소 2개만 정렬

    for (int c : v) cout << c << " "; // 정렬됨(50 40) 정렬안됨(10 20 30)
}

📌 partial_sort_copy()

순차열 상위 구간만을 정렬하여 목적지 순차열로 복사한다.

🔹 partial_sort_copy(b, e, b2, e2);
➡ [b, e) 구간의 원소 중 e2 - b2개의 상위 원소를 정렬하여 [b2, e2)의 순차열로 복사한다.

int main() 
{
    vector<int>v;
    
    v.push_back(10);
    v.push_back(40);
    v.push_back(30);
    v.push_back(20);
    v.push_back(50);
    v.push_back(80);
    v.push_back(60);
    v.push_back(70);
    v.push_back(90);

    vector<int>v2(4);
    vector<int>v3(4);

    partial_sort_copy(v.begin(), v.end(), v2.begin(), v2.end());
    
    for (int c : v2) cout << c << " "; // 10 20 30 40

    partial_sort_copy(v.begin(), v.end(), v3.begin(), v3.end(), greater<int>());

    for (int c : v3) cout << c << " "; // 90 80 70 60
}

치치

뉴비 개발자

이전 포스트

[STL] Algorithm - 변경 알고리즘

다음 포스트