[자료구조] 정렬 (sorting) - 퀵, 힙, 병합, 기수 정렬

공부용으로 작성되는 페이지입니다. 틀린 부분이나 환경에 따라 오류가 발생할 수 있습니다. 

 

---

 

복습 

앞서 학습했던 Big-O 표기법을 숙지해가며 공부하자. 

 

스택(LIFO) : 가장 나중에 들어온 데이터가 먼저 삭제 

큐(FIFO) : 가장 먼저 들어온 데이터가 먼저 삭제 

 

 

퀵 정렬 (Quick Sort)

데이터들을 피벗(키)으로 부분적으로 나누어 가며 정렬하는 방법

앞서 살펴본 정렬들과 달리 평균 시간복잡도는 O(n log n)이다. 최악 시간복잡도는 여전히 O(n^2)

 

1. Pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할
2. 프로그램을 Recall해야하므로 Stack 요구
3. 분할(Divide)와 정복(Conquer)을 활용

 

ex)

 

초기값 : 15 30 60 5 35 18

예시에서는 가장 오른쪽 수인 18을 pivot으로 설정한다.

따라서 35가 right를 담당하고 15가 left를 담당한다. 

 

(1) Left 값 > pivot 값 만족할 때 까지 Left 위치 증가 : left가 30으로 변화

(2) Right 값 < pivot 값 만족 시 까지 Right 위치 감소 : right가 5로 변화 

 

3,4번의 과정은 '값'이 아니라 '위치'를 기준으로 생각해야한다.

 

(3) Left >= Right면, Left와 Pivot 변경  : 해당x 

(4) Left < Right면, Left와 Right 값 교환 

 -> 30(left)와 5(right)의 위치를 비교해보면 Left < Right인것을 알 수 있다.

따라서, 5(left) 30(right)로 값이 교환된다. 

 

(5) 이후 Pivot 기준으로 분할 및 반복  :

현재 한 바퀴 돌았을 때 변화는 15 5 60 30 35 18 이다. 

쉬운듯...복잡하다

힙 정렬 (Heap Sort)

전이진 트리(Complete Binary Tree)를 이용한 정렬 방식

평균과 최악 모두 시간복잡도는 O(n log n)이다. 

 

ex) 17, 14 , 13, 15 ,16, 19 , 11, 18, 12 를 Heap 트리로 구성 

즉, 18과 15를 비교했을 땐 18을 위쪽으로 올린다.

 

 

 

 

힙 기반 데이터에는 특징이 있는데, 저장이나 삭제 정렬 시간 복잡도가 O(log n)이다.

 

 

 

반면 리스트 기반 데이터는 저장 시에는 모든 노드를 체크해야하므로 정렬 시간 복잡도는 O(n)이지만,

데이터 삭제 후 정렬하는데에는 바로 삭제 후 정렬만 하면 되므로 복잡도가 o(1) 밖에 되지 않는다. 

즉, 힙은 저장과 삭제 시에 굉장히 높은 효율을 보여준다는 것을 알 수 있다. 

 

우선순위 큐 

우선순위를 가진 항목들을 저장하고, 가장 우선순위가 높은 데이터가 먼저 삭제되는 구조이다.

이름에 힙과 관련된 용어는 들어가있지 않지만, 힙 정렬 기반으로 만들어진 자료구조다.  

우선 순위가 높은 처리를 먼저 한다는 특징 때문에 주로 네트워크 트래픽 제어나 운영체제 작업 스케줄링에서 사용된다.

 

병합 정렬 (Merge Sort)

이미 정렬되어 있는 2개의 리스트를 하나의 리스트로 합병하는 방식으로

평균과 최악 모두 시간복잡도는 O(n log n) 이다.

2개의 리스트를 만들어서 하나씩 병합하는 방법이다.

기수 정렬 (Radix Sort =Bucket Sort) 

큐(Queue)를 사용하여 자릿수(Digit)별로 정렬하는 방식으로

평균과 최악 모두 시간복잡도는 O(dn)이다.

 

ex) 15,27,64,25,50,17,39,28를 기수 정렬로 정렬하기 

 

1. 1의 자리에 해당하는 Bucket(큐 자료구조)에 데이터를 분배 후, 꺼내서 정렬한다. 
2. 10의 자리에 해당하는 Bucket(큐 자료구조)에 데이터를 분배 후, 꺼내서 정렬한다.

 

참고자료

https://youtu.be/7Gt9VpCYoF0?si=H6x-PcGlpd0wHbqL