Ch.12 정렬

Chapter 12. Sorting

stable한가? in-place인가? 움직인 위치가 최종 위치인가? 

• 데이터들을 특정순서(Decreasing order, Non-increasing order, Increasing order, Non-decreasing order)로 정리하는 것.
• 데이터들의 searching, analyzing, manipulating 을 효율적으로 수행할 수 있게 하여 IT 분야에 기본적이며 필수적인 연산(알고리즘)임.
• 모든 경우에 최적인 정렬 알고리즘은 없으므로 정렬의 대상과 정렬을 실행할 환경에 따라 아래의 상황을 고려하여 알고리즘을 선택해야함.

1. 정렬할 대상의 개수 (dataset의 크기)는?
2. 정렬할 대상의 일부가 이미 정렬되어 있을 수도 있나?
3. 필요한 (비교연산과 이동연산을 포함한) 수행시간(time complexity) 은?
4. 가용한 memory or disk 크기(space complexity)는? 
5. 정렬 알고리즘이 (input size에 비례하는) 추가 공간을 필요로 하는가?

• 대표적으로 merge sorting은 time complexity는 최고(nlogn, n=정렬대상의개수)이나 space complexity는 n에 비례한 extra memory 가 필요하여 O(n)이다. 
• 반면, selection sorting은 time complexity는 나쁘나(n^2) space complexity가 O(1) 이다.

Sorting animation 1)
Sorting animation 2)
 

• Stability of sorting algorithm : (10  30  20  30'  5  7) 을 selection/insertion/bubble/shell sorting 하면 (30 --> 30') 의 순서가 유지될까?

• dataset의 크기가 n일때 selection/insertion/bubble/shell sort algorithm은 n에 관한 함수만큼의 추가 공간이 필요할까? == 이 알고리즘들이 in-place sort algorithm 인가? == 이 알고리즘들의 space complexity가 O(1) 인가?

 
아래는 non-decreasing order로 설명되고있음.

• Selection sort 

1. 정렬 중 (sorted part + unsorted part) 를 유지함.
2. 각 iteration 마다 unsorted part에서 비교연산이 일어남.
3. 각 iteration 마다 unsorted part에서 가장 작은 값이  최종 output에서의 자신의 정렬된 위치를 찾아감.

• Insertion sort 

1. 정렬 중 (sorted part + unsorted part) 를 유지함.
2. 각 iteration 마다 unsorted part의 가장 왼쪽 값을 key로 sorted part에 정렬시켜 삽입함.
3. sorted part 에서 비교 연산이 일어남.
4. 각 라운드 (iteration)에서 sorted part 추가 된 값은 최종 sorted output에서의 위치와 동일하지 않을 수 있음.

• Bubble sort 

1. 정렬 중  (unsorted part + sorted part) 를 유지함.
2. 각 iteration 마다 왼쪽의 unsorted part에서 가장 큰 값이 sorted part로 이동함.
3. 각 iteration 에서 sorted part로 이동한 값은 최종 output에서의 자신의 위치임.

• Shell sort

1. insertion sort의 upgrade version으로 속도가 훨씬 빠른 것으로 증명됨.
2. 단, 성능은 gap sequence를 어떻게 설정하는가에 따라 다르게 분석될 수 있음.
3. 여기서 빠르다는 것은 (time complexity가 O(n^2) 보다 좋다)는 의미임.

 

Radix sort 기수정렬

• (조건) 정렬하고자하는 record의 key 값의 data type이 discrete 하게 분류(d개의 자리수로)가 가능해야함. (예) 십진수, 이진수, 알파벳, (실수/한글/한자는 안됨)
• (아이디어) 각 자리수를 표현할 수 있는 경우의 수(b) 만큼의 queue(bucket)를 사용하여, 낮은 자리 수 부터 높은 자리수로 각 자리수에 해당하는 queue에 넣고(enqueue) 정렬하고자 하는 순서에 따른 queue 순서(queue0->queue1-->queue2...-->queue9)대로 dequeue()를 실행하는 것을 d(자리수)번 반복한다.  

1. (예) 64bit 로 표현되는 key 가 있다. key 값의 한 자리수를 4bit로 표현한다고 가정하면 b = 2^4 = 16개의 queue 가 필요하며, 총 d=(64/4)=16 번 enqueue/dequeue를 반복해야 정렬됨.
2. 1의 자리를 정렬하고 나면, 동일한 10의 자리 수를 가진 숫자들 끼리는 정렬된 상태임. 

• (잇점) key 값이 radix 정렬이 가능한 조건이라면 time complexity가 O(n)에 bound 하므로 정렬 알고리즘의 상한선이 O(nlogn) 을 자랑하는 merge sort  보다 성능이 좋음. 예를 들어,

1. 5자리 정수인 학수번호를 key 값으로 정렬하는 경우 radix sort 가 merge sort 보다 성능이 좋음. (참)
2. 한국이름을 key 값으로 정렬을 할 때 radix sort 가 merge sort 보다 성능이 좋음. (거짓)

• Space complexity : d 개의 bucket이 필요하며 각 bucket의 크기는 최악의 경우 (input size n 의 모든 record들의 key 값이 동일한 경우) n 이므로 O(dn), O(n).

 

Summary of sort algorithms (n : 정렬하고자 하는 record의 개수)

• Time complxity

1. 실수 혹은 한글을 key로 하는 dataset을 정렬할 경우, O(nlogn)이 best 알고리즘임. (최악의 경우 time complexity가 가장 좋은 알고리즘은 heap/merge sort)
2. 100000 자리 정수로 구성된 key를 정렬할 경우 radix sort 가 O(n)으로 O(nlogn)인 merge sort 보다 빠름.

• Space complexity of Merge sort and Radix sort is NOT bounded to O(1).

1. Merge/Radix sort의 space complexity는 O(n)

• Insertion/Bubble/Merge/Radix sort algorithms are stable.

1. Radix sort를 제외하고 stable sort algorithm들은 비교/이동 연산이 인접한 두 index 사이에서 일어난다는 특징이 있음. 

---

정렬이란
특정 데이터들을 특정 순서로 정리하는 것.
→ 데이터들의 searching, analyzing, manipulating을 효율적으로 수행할 수 있게 함
→ 모든 경우에 최적인 정렬 알고리즘은 없다. 따라서 각 프로그램의 목적 및 실행환경에 적합한 방법을 사용해야 한다.
 
정렬 알고리즘의 평가 기준
- 비교 횟수의 많고 적음
- 이동 횟수의 많고 적음
 
1) 분류기준 1

단순 but 비효율적	복잡 but 효율적
삽입(Shell), 선택, 버블정렬 등	퀵, 히프, 합병, 기수 정렬 등

 
2) 분류기준 2
- 내부 정렬: 모든 데이터가 주기억장치에 저장되어진 상태에서 정렬
- 외부 정렬: 외부기억장치에 대부분의 데이터가 있고 일부만 주기억장치에 저장된 상태에서 정렬
 
3) 분류기준 3
정렬 알고리즘의 안정성 (Stability)
→ 안정성 있는 정렬은 동일한 키 값을 갖는 레코드들의 상대적인 위치가 정렬 후에도 바뀌지 않는다. (== 순서 유지)
ex) 삽입정렬, 버블정렬, 합병정렬 등
 
바뀌는 경우 (안정 X)
ex) 선택정렬, 히프정렬 등

---

선택 정렬 (Selection Sort) - unsorted part에서 가장 작은 수를 선택(오른쪽)

: 정렬된 왼쪽 리스트와 정렬되지 않은 오른쪽 리스트를 가정한다.
→ 초기에는 왼쪽 리스트는 비어있고, 정렬할 숫자들은 모두 오른쪽 리스트에 존재한다.
: non-decreasing order로 정렬한다고 가정
: 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 되풀이한다. (오른쪽 리스트가 공백상태가 될 때까지 반복한다. 그니까 n-1번 반복한다.)

• 배열의 앞쪽은 sorted part (왼쪽), 뒤는 unsorted part로 구분하고 swapping을 하면 in-place sorting이 가능하다.
• 따라서 추가적인 메모리 공간이 필요하지 않다.
• unsorted part에서 비교연산이 발생한다.
•  
• 선택정렬은 더이상의 이동이 필요 없더라도 계속 swapping(이동연산)을 진행한다.
• → 이동을 하지 않는게 더 효율적인 경우는?
• - record size가 큰 경우
• - input data set이 거의 정렬된 경우
•  
• 마지막은 이미 max값이기 때문에 0에서 n-2번 인덱스번호까지 총 n-1번만 반복한다.
• 매 round마다 하나의 레코드가 정렬된 최종 위치를 찾게 된다. (더이상 바뀌지 않는 최종 위치임)

비교횟수	O(n*n)
이동횟수	3*(n-1) → O(n)

 
* best/worst case 모두 비교횟수는 항상 모두 동일하다.
* 전체 시간적 복잡도: O(n*n)
* unstable sort (input된 순서가 바뀔 수도 있다.)
* in-place sort (메모리 사용 최소화, space complicity O(1))
* small datasets에 적합하다.

---

삽입 정렬 (insertion sort) - sorted part에서 비교연산을 한다. (왼쪽)

정렬되어 있는 리스트에 새로운 레코드를 정렬이 유지되는 위치에 삽입하는 과정을 반복
단, 맨 끝까지 해야 각 수의 최종 위치를 정확하게 알 수 있다.

• 앞: sorted part
• 뒤: unsorted part

* Best case에서의 시간 복잡도: O(N)
→ 한 번만 비교한다.
 
추가 공간은 변수(key) 하나이다. 따라서 space complexity = O(1)
고정된 양의 추가 메모리만 필요하기 때문에 in-place sort 알고리즘이다.
 
- best case: list가 기정렬된 상태이므로 비교 n-1회  → O(N)
바로 앞에것과 1회씩만 비교한다.
selection sort 선택 정렬에서는 기 정렬된 경우에도 unsorted part에서 비교연산이 일어나기 때문에 O(n*n) 이다.
 
- worst case: list가 역정렬됨 → O(N*N)
- 평균: O(N*N)
 
* 많은 이동이 필요하기 때문에 small dataset에 적합하다.
* 안정된 stable 정렬 방법이다. 
selection sort 선택 정렬과는 달리 낮은 index부터 순서대로 정렬하기 때문
* 대부분 정렬되어 있는 경우 매우 효율적인 알고리즘이다. O(N)

---

버블 정렬 (Bubble sort) - non decreasing 

인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면서 서로 교환하는 비교-교환 과정(비교/연산의 기본 단위가 2개임)을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행 (서로 교환)
 
비교-교환 과정이 한 번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동한다.
전체 숫자가 전부 정렬될 때까지 계속된다. N-1번 반복한다.
 
In each round, unsorted part에서 가장 큰 record가 최종 위치를 찾아간다.
 
비교횟수: O(n*n)
최상, 평균, 최악의 경우 모두 동일하다.
(insertion sort 삽입 정렬은 기 정렬되어 있는 best case의 경우 바로 앞에 것과 1회씩만 비교하기 때문에 O(n)이다.)
 
이동횟수: 
역순으로 정렬된 경우(worst case): 3 * 비교횟수 번
이미 정렬된 경우(best case): 0번
평균의 경우: O(n*n)
 
이동연산은 비교 연산보다 더 많은 시간이 소요된다.
→ 부분적으로 정렬된 데이터 셋에서 더 효율적이다.
- small dataset에 적합하다.
- 역순이 아니면 이동하지 않으므로 stable sort이다.
- in-place sort

---

셸 정렬 (Shell sort)

1. insertion sort의 upgrade version으로 속도가 훨씬 빠른 것으로 증명됨.
2. 삽입 정렬이 어느 정도 정렬된 리스트에서 대단히 빠른 것에 착안
3. = input에 있는 값들이 어느 정도 이미 정렬된 위치에 있다.
4. 단, 성능은 gap sequence를 어떻게 설정하는가에 따라 다르게 분석될 수 있음.
5. 여기서 빠르다는 것은 (time complexity가 O(n^2) 보다 좋다)는 의미임.

 전체 리스트를 일정 간격 (gap)의 부분 리스트로 나눈다. → 나뉘어진 각각의 부분 리스트를 삽입정렬 한다.
- 불연속적인 부분 리스트에서 원거리 자료 이동보다 적은 위치 교환으로 제자리를 찾을 가능성이 높다.
- 부분 리스트가 점진적으로 정렬된 상태가 되므로 삽입정렬 속도가 증가한다.
- unstable sort due to gap
- in-place sort → space complexity = O(1) / 실제 부분 리스트들이 만들어지는 것이 아니라 일정한 간격으로 삽입 정렬을 수행하는 것이기 때문이다.

---

이제는 복잡하지만 효율적인 방법에 대해서 본다. (입력 데이터가 많으면서 자주 정렬해야 하는 경우)

*** n개의 record로 구성된 dataset을 non-decreasing order로 정렬하려고 한다. ***
Merge sort

• (unlike quick sort) 주어진 dataset이 균등한 크기로 분할(by calling merge_sort())되었다가 크기가 1이되면 합병(by calling merge())되면서 정렬됨.

1. (n개가 2의 배수가 아닌 경우 분할되는 패턴에 주의 할 것!)  (예) n = 10 --> (((0 1) (2)) ((3) (4))) (((5 6) (7)) ((8) (9)))

• Space complexity  O(n)

1. 두 sorted subset이 merge 될 때 임시 메모리(배열C 라고 하자)가 필요하며, 마지막 round의 merge( ) 에서 n개가 병합되므로 O(n)의 extra space가 필요함.
2. 각 merge( ) 함수는 주어진 input (슬라이드에서 list[ ])의 list[0] ~ list[9] 사이의 일부분을 정렬하는 것임. 
3. 정렬된 값들은 임시저장소(배열 C)에 저장되어있으므로 merge( ) 함수 종료 직전에 input (list[ ]) 배열의 해당 인덱스에 copy해 놓아야 merge( ) 함수에서 행한 정렬 결과가 다음 recursive call에 반영됨.

• Time Complexity 

1. n개의 record가 각 round 마다 균등하게 분할되므로 총 O(logn)의 iteration이 필요함.
2. 각 merge( ) 함수는 전체의 일부분을 merge 하나, 각 round에서 호출되는 merge( ) 를 통합하면 최대 (n-1) 번의 비교연산이 일어나게 되므로 O(n)의 시간이 소요됨.  (이동은 비교하면서 최대 (n-1)번 이후 temporary memory에서 original list[]로 copy 되면서 또 최대 n 번 일어남.) 결국 각 round 마다 연산은 O(n) 임.
3. 따라서 merge sort의 time complexity는 O(nlogn)임.

• Stable sort algorithm 임.

1. merge() 함수에서 두 sub list를 통합하며 정렬할때 비교하는 두 key 값이 같은 경우 앞쪽 sub list의 값을 우선적으로 선택함으로써 stable 하게 구현할 수 있음.

 
Quick sort

• 매 round 마다 pivot을 결정함. (강의 슬라이드에서는 해당 round의 input 배열들 중 가장 index가 낮은 항의 값을 pivot으로 정함) 
• pivot 값이 quick sort의 성능(time complexity)에 영향을 줌.

1. 현재 round의 input값들 중 중간 크기의 값을 정할 때에는 (merge sort)처럼 크기가 균등한 두 subset으로 분할되어 반복되는 round의 횟수가 O(logn)에 바운드 함.
2. 이미 정렬된것을 다시 정렬하면서 항상 남은 정렬대상에서 가장 작은 key 값을 pivot으로 정하는 경우처럼, 한쪽으로 치우치게 분할될 경우 O(n) 만큼의 iteration이 발생하게 됨.

• 각 iteration 마다, partition( ) 함수가 실행됨. n번

1. partition( ) 함수에서 pivot의 최종위치는 가장 왼쪽부터 index가 커지는 방향으로 scan 하여 pivot 보다 큰 첫 번째 항(low)과 가장 오른쪽에서 index가 작아지는 방향으로 scan하여 pivot 보다 작은 첫 번째 항(high)을 찾아 이 두 항의 값을 swapping 하는 과정을 반복하게 됨. 
2. swapping 만으로 해결되므로 partition()의 space complexity는 O(1).
3. 결과적으로 pivot 값이 최종 정렬된 위치에 저장되고,
4. pivot이 저장된 위치에서 왼쪽 subset에는 pivot 보다 작은 key 값들이,
5. pivot이 저장된 위치에서 오른쪽 subset에는 pivot보다 큰 key 값들이 저장됨.
6. 왼쪽 subset과 오른쪽 subset은 다시 정렬해야함.

• selection/bubble sort 처럼, Quick sort algorithm도 한 round(iteration) 마다 n개 중 1개의 record가 최종 정렬된 위치로 이동하는 알고리즘임.

• Quick sort algorithm is not stable. 

1. counter example) list[] = (10, 8, 7, 6, 10', 5, 4, 3, 2, 1)

• pivot을 결정하는 알고리즘에 따라 성능이 달라질 수 있음.

---

합병 정렬 (merge sort) - 분할 정복 기법

하나의 리스트를 두 개의 균등한 크기로 분할하고(unlike quick sort) 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는다.
→ 균등하게 분할하기 때문에 O(log n)
 
Q. 몇 개의 단계(round)로 분할될까? 즉, 부분 리스트를 합하는 연산은 몇 번 일어날까?
A. log N, N=input size (균등하게 분할했기 때문에)
딱 나누어지면 perfect binary tree처럼 생기게 된다. (높이)
 
- 독립적인 recursive call을 한다.

[non-decreasing order]
1. 분할 (Devide)
배열을 같은 크기의 2개 부분 배열로 분할
→ dataset의 크기가 1이 될 때까지 분할한다. → 비교연산은 두 개의 key값으로 이우러지기 때문 

2. 정복 (Conquer)
부분 배열을 정렬한다. 부분배열의 크기가 충분히 작지 않으면 재귀호출을 이용하여 다시 분할-정복기법을 적용한다. 
→ 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 적용하면 된다.

3. 결합 (Combine) / 합병 (merge)
정렬된 부분배열을 하나의 배열에 통합한다. → 여기서 정렬이 수행된다. (합병)
→ 정렬한 배열을 다시 original space에 저장해야 한다.

 
- 왼쪽배열이 끝나야 오른쪽 배열이 분할-정복 과정을 수행하게 된다.  
- extra space memory → O(n) → in-place sorting algorithm이 아니다.
 
[합병]
Q. 만약 기 정렬된 경우라면?
A. 비교 / 이동 횟수가 모두 반으로 줄어든다.
→ comparisons 없이 복사할 수 있는 경우가 생기기 때문이다.
 
[합병]
sorted 배열은 임시 저장소이므로 original list에 copy해야 recursive call이 제대로 수행된다.
 
merge()에서 |right - left| 만큼의 비교연산 발생 → O(n)
merge()에서 worst case의 경우에 |right - left| 만큼의 비교연산 발생 → O(n)
 
recursive call의 횟수는 log(n)이다. (n== dataset의 크기, 정렬하고자 하는 record의 개수, input의 크기)
 
→ 따라서 merge sort 합병정렬의 시간복잡도는 O(n * log n)이다.
 
만약 record의 개수가 33개인 dataset을 merge sort하면 merge()함수는 총 몇 번 호출되는가?
→ 곤란..... 2의 k승이 아니기 때문에... 
 
- 레코드의 크기가 큰 경우에는 매우 큰 시간적 낭비를 초래한다.
- 레코드를 연결 리스트로 구성하여 합병 정렬할 경우, 매우 효율적이다.

---

퀵 정렬 (Quick sort)

리스트를 2개의 부분리스트로 비균등 분할하고, 각각의 부분리스트를 다시 퀵정렬한다. (재귀호출)
- 평균적으로 가장 빠른 정렬 방법이다.
- 분할-정복법을 사용한다.
 
- 가능하면 선택된 pivot에 의해 얻어진 부분리스트의 길이가 비슷하도록 / unsorted list 내 key들 중 중간 값을 pivot로 선택
- pivot은 최종 (in the sorted list) 자리로 이동하게 된다.
- 현 리스트의 가장 왼쪽 record의 key가 pivot이 된다.

pivot보다 작은 값들

pivot

pivot보다 큰 값들

 
high < low가 되면 swapping을 멈추고 done!
→ 이 때 high 위치가 pivot이 들어갈 정렬된 위치이다. (최종 위치) 
 
퀵소트는 unstable algorithm이다.
 
left < right인 경우에만 quick sort를 반복하고 이 조건이 어긋나는 경우 sorting을 종료한다.

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

---