[C++] Sort 함수

1. Sort 함수

C++의 algorithm 헤더에 내장되어 있는 함수다.

기본적으로 오름차순 정렬을 수행한다.

인트로 정렬을 사용하고 있다. 

#include <iostream>
#include <algorithm> //algorithm 헤더

int main()
{
    int a[10] = {3,4,1,2,5,6,7,8,9};
    sort(a, a+10); //오름차순으로 정렬
    for(int i=0;i<10;i++)
    	std::cout<<a[i]<<' '; //{1, 2, 3, 4, 5, 6, 7, 8, 9} 출력됨
}

 

내림차순 정렬을 하고싶으면, 그에 맞는 함수를 따로 만들어 sort함수의 세번째 인자 값으로 넣으면 된다.

#include <iostream>
#include <algorithm> //algorithm 헤더

bool compare(int a, int b) //왼쪽 값이 더 크도록 정렬
{
	return a < b;
}

int main()
{
    int a[10] = {3,4,1,2,5,6,7,8,9};
    sort(a, a+10, compare); //내림차순으로 정렬
    for(int i=0;i<10;i++)
    	std::cout<<a[i]<<' '; //{9, 8, 7, 6, 5, 4, 3, 2, 1} 출력됨
}

 

2. 인트로 정렬

퀵 정렬, 힙 정렬, 삽입 정렬 3개의 알고리즘이 섞인 정렬으로, 캡슐화 되어있어 내부 구현사항을 사용자가 알 수 없다.

배열의 크기가 작으면(파티션 원소 16개 이하) 삽입 정렬을 사용한다. 크기 작은 배열, 정리 거의 다 된 배열에서 빠른 속도를 내기 때문이다.

배열의 크기가 크면(파티션 원소 16~ 2logN) 퀵 정렬을 사용한다.

퀵 정렬을 사용하다가 오래 걸리면 힙 정렬을 사용한다.

합병 정렬(merge sort)의 경우 N만큼의 메모리가 추가적으로 필요하기 때문에 사용하지 않는다.

 

3. List

List 자료구조는 랜덤 접근이 안되기 때문에 알고리즘 헤더의 sort 함수로 동작하지 않는다.

따라서 알고리즘 헤더가 아닌 자료구조의 멤버 함수 sort를 사용해야 한다.

또한, 합병 정렬을 사용하기 때문에 시간 복잡도는 O(NlogN)이 된다.

 

참고자료

https://blog.naver.com/ndb796/221227975229

https://github.com/Romanticism-GameDeveloper/GameDeveloper-Client-Interview/blob/main/C%2B%2B/algorithm%20sort%EB%8A%94%20%EC%96%B4%EB%96%A4%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%B8%EA%B0%80.md