[알고리즘] 기본적인 정렬 알고리즘 자세히 정리

1. O(nlogn)인 것

1. 병합 정렬

배열을 최소단위까지 분할 후, 합치면서 정렬하여 하나의 배열을 만드는 방식이다.

합칠 때는 두 배열의 0번째 원소를 비교하며 더 작은 원소를 추가하고 다시 비교하는 과정을 반복한다.

 

분할 과정은 logN만큼 일어나며, 2N의 공간을 사용한다. 이때 배열이 아닌 linked list를 사용하면 N의 저장공간으로 구현이 가능하다. 기존 저장공간에서 포인터만 바꾸는 식으로 수행할 수 있다. 배열을 쪼갤 경우 head 포인터를 추가로 만들고, 합병 과정에서는 next 주소값을 적절히 설정해주면 된다.

 

합병정렬은 같은 숫자의 경우 순서가 뒤바뀌지 않는 stable sort이다.

 

<코드 추가>

2. 힙 정렬

원소들을 힙에 삽입하는데 각 노드의 값이 자식노드보다 큰 이진트리가 되도록 삽입한다. 트리를 완성하면 트리 내에서 가장 큰 값을 가지는 루트부터 제거하며 새로운 배열의 마지막부터 채워나간다. 제거한 뒤에도 이진트리 구조를 유지할 수 있도록 한다. 선택정렬과 거의 같은 알고리즘이다.

 

힙 정렬은 추가적인 메모리를 필요로하지 않으며, 경우에 상관없이 O(nlogn)으로 안정적인 성능을 보인다.

 

<코드 추가>

3. 퀵 정렬

가장 간단한 partition step, 로무토 파티션

적절한 원소를 기준으로 삼고(pivot) 이보다 작은 원소는 왼쪽에, 큰 원소는 오른쪽에 위치하도록 정렬한다. 이 과정을 partition step이라고 한다. partition step을 어떻게 하느냐에 따라 세부적인 알고리즘은 다양할 수 있다. 이후 pivot을 기준으로 리스트를 분할하고, 분할된 두개 리스트에 각각 재귀적으로 위 과정을 반복하며 left<right를 만족하지 않을 때까지 반복한다.

좋은 예와 나쁜 예

퀵 정렬은 같은 O(nlogn)인 상황에서 가장 빠르고, 최악의 경우 O(n²)이다. 이미 정렬된 배열을 정렬할 때나, pivot을 항상 첫번째 원소로 하도록 구현했을 때가 그런 경우이다.

따라서 퀵 정렬을 조금 수정하여 최악의 경우가 거의 발생하지 않도록하고 나쁜 경우다 싶으면 힙 정렬로 전환하도록 코딩한다. 수정하는 방법 중 한 가지는 pivot을 랜덤으로 잡는 것이다.이렇게 퀵 정렬의 재귀가 일정 깊이 이상이 되면 힙 정렬을 사용하는 알고리즘을 '인트로 정렬'이라고 한다.

그런데 실제로 돌려보면 퀵소트가 오히려 빠른 경우가 종종 있다. 비교하는 기준점이 하나로 고정되고 그 기준점이 많은 비교를 수행하는 퀵 정렬의 특성상 레지스터에 비교할 기준값을 올려놓고 다음 비교할 원소를 예측하여 가져오는 경우, 다른 알고리즘이 메모리에서 여러번 레지스터로 올리는 시간이 생략되어 오히려 더 빠른 경우를 볼 수 있다.

 

<코드 추가>

2. O(n²)인 것

1. 버블 정렬

2. 선택 정렬

3. 삽입 정렬

3. 기타

1. 팀 정렬

python의 sort() 함수, java의 Array.sort()

 

'실제 데이터는 대부분 이미 정렬이 되어있을 것이다'라고 가정하고 실제 데이터에서 고성능을 낼 수 있도록 설계한 알고리즘. 병합과 삽입 정렬을 조합한 알고리즘이다. 병합 정렬은 원소의 개수가 적을 때 오버헤드가 발생하기 때문에 파티션 크기가 특정 값 이하(16/32)가 되면 삽입 정렬을 사용한다.

병합 정렬을 기반으로 하기 때문에 적어도 O((1/2)n)의 추가 메모리 공간이 필요하다.

 

---

<참고자료 및 출처>

 

https://hsp1116.tistory.com/33

기본 정렬 알고리즘(Sorting Algoritm) 요약 정리 (선택, 삽입, 버블, 합병, 퀵) v1.1

 

https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#fn-14

정렬 알고리즘 - 나무위키