unstable/stable sort

대표적인

stable sort:

• Insertion Sort 삽입 정렬
• Merge Sort 합병 정렬
• Bubble Sort 버블 정렬
• Counting Sort 계수 정렬

unstable sort:

• Selection sort 선택 정렬
• Heap Sort  히프 정렬
• Shell Sort 쉘 정렬
• Quick Sort 퀵 정렬

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

using namespace std;

bool compare(pair<int, string> l1, pair<int, string> l2){
    return l1.first < l2.first;
}

int main(){

    int n;
    cin >> n;

    vector<pair<int, string>> member;
    for(int i=0; i<n; i++){
        int age;
        string name;
        cin >> age >> name;
        member.emplace_back(age, name);
    }

    stable_sort(member.begin(), member.end(), compare);

    for(int i=0; i<n; i++){
        cout << member[i].first << ' ' << member[i].second << '\n';
    }

}

sort는 quick sort, stable_sort는 merge sort로 구현된다.

 

그냥 sort는 comparator에서 & 주소연산자를 써야하는데(안써도 되나?)

stable_sort는 & 주소 연산자를 쓰면 에러가 나는 이유는 뭘까