실전 알고리즘 0x0E강 - 정렬1

정렬 1

[ 기초 정렬 ]

- 정렬 알고리즘은 30여가지가 있다.

- 삽입, 버블, 선택 정렬의 시간복잡도는 O(N^2)이다.

- 선택 정렬 : 가장 큰 값을 찾아서 맨 뒤로 보낸다.

int arr[10] = {3, 2, 7, 116, 62, 235, 1, 23, 55, 77};
int n = 10;
for(int i = n-1; i > 0; i--){
	swap(*max_element(arr, arr+i+1), arr[i]);
}

- 버블정렬 : 뒤에 값과 비교하여 큰 값을 뒤로 보내는걸 반복한다

int arr[5] = {-2, 2, 4, 6, 13};
int n = 5;
for(int i = 0; i < n; i++){
	for(int j = 0; j < n-1-i; j++){
    	if(arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
    }
}

[ Merge Sort ]

https://gideok0918.tistory.com/106

- 시간복잡도 O(N logN) 이다. ( 분할은 O(N)이고 합칠 때 O(N logN)이다.

- Stable Sort : 우선순위가 같은 원소가 여러개일 때, 원래의 순서를 따라가도록 하는 정렬 이다.

- 활용 예시 : 1번만 merge sort를 하면 원하는 대로 정렬할 수 있다.

 

[ Quick Sort ]

- 가장 빠른 정렬이다.

- 코딩테스트에 STL을 못 쓰고 직접 구현해야하면 절대 Quick Sort를 쓰지 말고 Merge Sort, 힙 소트, .. O(N logN)을 사용한다.

- 매 단계마다 pivot이라고 이름을 붙인 원소 하나를 제자리로 보내는 작업을 반복한다.

- 재귀를 사용하여 pivot을 기준으로 작은 수는 왼쪽, 큰 수는 오른쪽으로 이동시키는 과정을 반복한다.

int arr[8] = {6, -8, 1, 12, 8, 3, 7, -7};
int tmp[8];
int tidx = 0;
int pivot = arr[0];
for(int i = 1; i < 8; i++)
	if(arr[i] <= pivot) tmp[tidx++] = arr[i];
tmp[tidx++] = pivot;
for(int i = 1; i < 8; i++)
	if(arr[i] > pivot) tmp[tidx++] = arr[i];
for(int i = 0; i < 8; i++) arr[i] = tmp[i];

- 위 코드는 O(N)으로 작동한다.

- 위 방법은 퀵소트의 장점을 뭉개버린다. 퀵소트의 장점은 추가적인 공간이 필요하지 않다. cache hit rate가 높아서 속도가 빠르다. ( 추가적인 공간을 사용하지 않는 정렬 : In-Place Sort )

- 양쪽에 포인터 2개를 두고 left 는 pivot보다 큰 값이 나올 때 까지 오른쪽으로 이동하고 right는 pivot보다 작은 값이 나올 때 까지 왼쪽으로 이동한다. 그 다음 left와 right이 교차(left > right)하는지 확인하고 아니면 두 값을 swap한다. 교차하면 pivot과 right를 swap하며 과정을 멈춘다.

- 시간 복잡도는 pivot을 가운데로 잘 잡으면 평균적으로 O(N logN)이고 최악의 경우는 O(N^2)이다. 그렇기 때문에 STL이 없으면 퀵소트를 짜면 안된다. (라이브러리에서는 pivot을 랜덤하게 하거나 3개의 후보를 골라 중간값을 선택한다. 일정 깊이 이상 들어가면 O(N logN)이 보장되는 힙 소트로 정렬하는 처리를 한다.(introspective sort라고 부른다))