[STL]sort, stable_sort

sort, stable_sort 공통점

 - 둘 다 sorting(정렬)의 일종이다.

 - sort 의 기본은 오름차순 정렬이다.

- 평균적으로 O(NlogN)의 시간복잡도를 가진다.

 

 

sort, stable_sort 차이점

 - sort는 퀵정렬, stable_sort는 병합정렬로 이루어져 있다.

 - sort와 stable_sort의 차이점은 같은 항목의 정렬에 있어서 있다.

   * sort(불안정 정렬), stable_sort(안정 정렬) : sort는 같은 항목에 있어서 정렬 후와 정렬 전의 순서가 변할 수도 있고,

     stable_sort는 같은 항목은 정렬 전과 정렬 후 순서가 변하지 않는다는 특징이 있다.

 

 

사용법

 - algorithm 헤더에 포함되어 있다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

vector<int> v;
...

// sort
sort(v.begin(), v.end(),compare);

// stable_sort
stable_sort(v.begin(), v.end(),compare);

 ※ compare은 사용자가 임의로 만든 비교함수 이다.

    만약 compare 자리에 아무것도 넣지 않는다면 기본적으로 sort는 오름차순으로 실행된다.

 

 관련된 문제는 BOJ 10814번 나이순 정렬 (www.acmicpc.net/problem/10814)

 

 

 

코딩을 공부하고 있는 학생입니다.

공부한 것을 정리, 공유하기 위해 블로그를 운영하고 있습니다.

포스팅에 틀린 부분이 있다면 과감한 지적, 수정의 한 마디 부탁드립니다! 감사합니다 :)

github.com/holicAZ

holicAZ - Overview