[자료구조] 1128

12. 정렬

1. 정렬이란?
2. 선택 정렬
3. 삽입 정렬
4. 버블 정렬
5. 셸 정렬
6. 합병 정렬
7. 퀵 정렬
8. 히프 정렬
9. 기수 정렬
10. 정렬 알고리즘의 비교

 

---

12.6 합병 정렬

: 리스트를 두 개의 균등한 크기로 분할하고, 분할된 부분 리스트를 정렬한다.

 

분할 정복(Devide & COnquer)

합병정렬 과정

1. 분할: Data set 크기가 1이 될 때까지 분할한다.
2. 합병: 비교하여, 정렬한다.

**합병 시, sorted 배열(임시 추가 공간)을 list 배열(원래 공간)로 복사해야한다!

 

합병 알고리즘

: 분할된 두 배열을 비교하여, 작은 것을 새로운 배열에 넣는다. (Shorted 배열)

• 추가 공간이 필요하다. (in-place 아님!)

 

합병정렬 알고리즘

**엔트리 개수가 짝수 개인 경우, mid 계산 주의!!

 

합병정렬 프로그램

• Stable sorting
• Not in-place (임시 추가 공간 필요하다.)
• 시간 복잡도: O(n*log(n))
• 레코드의 크기가 큰 경우에는 매우 큰 시간적 낭비를 초래한다.

 

---

12.7 퀵 정렬

: 리스트를 2개의 부분리스트로 비균등 분할하고, 각각의 부분리스트를 다시 퀵정렬 한다. (재귀 호출)

 

▶ 분할 정복법

• 합병정렬: 균등 분할 (mid)
• 퀵정렬: 비균등 분할 (pivot)

퀵 정렬

 

분할 과정

1. 배열의 가장 왼쪽에 있는 것이 피벗이 되도록 한다.
2. low 포인터와 high 포인터를 점점 가운데로 이동하며, 이동 중 low의 경우 포인터가 가리키는 값이 피벗보다 클 때, high의 경우 포인터가 가리키는 값이 피벗보다 작을 때, 두 배열을 교환한다.
3. 마지막에 low 포인터와 high 포인터가 만나면, 그 사이에 피벗을 끼워넣는다.

partition 함수

 

퀵정렬 알고리즘

퀵정렬 코드

 

퀵정렬 과정

: 피봇의 위치는 최종 위치로 결정된다.

 

---