기말준비-정렬(Sort)

배열 A[1...N]의 N개 데이터를 Sort하는 가장 빠른 방법?

 - 비교기반 정렬 (Comparison based Sorting) = Ω(N lgN)

  - 선택정렬, 삽입정렬, 버블정렬      -> O(N^2)

  - 쉘 정렬                                  -> O(N√N) / 최악 : O(N^2)

  - 합병 정렬, 퀵 정렬, 힙 정렬, BST  -> O(N lgN)

  - 기수 정렬                               -> O(N)  [비교기반 정렬이 아님]

 

 

1. 선택 정렬 (Selection Sort)

 전체를 탐색한 후, 최소or최대값을 왼쪽으로 이동시킴

 - 왼쪽부터 차례로 검사하면서 가장 큰 수를 가장 왼쪽으로 이동

 - 가장 왼쪽은 반복할때마다 한 칸씩 오른쪽으로 당겨짐

 정상적으로 정렬된 것을 확인할 수 있음.

 

 

 

2. 삽입 정렬 (Insertion Sort)

 뒤에서 시작해서 앞으로 가면서 작은 것을 만나면 멈춤.

 Sort된 Data에는 Selection Sort보다 빠름.

 - k의 데이터를 k-1 데이터와 비교하면서 k-1보다 k가 크면 swap을 반복

 - k-1가 k보다 크면 정지.

Selection Sort와 달리 Instruction Count가 계속 달라짐. 24~37까지 본듯

Sort 된 data를 한번 더 Insertion Sort하면 Instruction Count가 9로 고정됨.

 

 

 

3. 버블 정렬 (Bubble Sort)

 인접 두 원소를 비교하며 교환하는 작업을 반복

 count == 0이 될때까지 j-1이 j보다 크면 위치교환을 반복.

 해당 코드는 작은 숫자가 위로 오게 됨. (큰 숫자가 위로 오게 할려면 j-1 < j)

 Sort에 걸리는 시간은 대부분 45근처로 나오되, 일부 정렬된 경우가 같이 있다면 저렇게 30근처까지 줄어들기도 함.

 대신 2번 After Sort와 같이 역순으로 정렬된 데이터를 입력하면 무조건 최대의 시간을 사용함.

 

 

 

4. 쉘 정렬 (Shell Sorting)

 간격별 subList를 만들고, 그걸 삽입정렬함. -> 약간 정렬된 데이터는 빠르게 끝남.

위 이미지와 같이 gap이 size의 절반으로 시작하고, gap 차이만큼의 원소들을 묶어서 subList로 만든 후 Insertion Sort.

gap이 1이하가 되면 끝.

이런식으로 구현했고, 정렬은 잘 작동한다.

이런식으로 정렬된 데이터는 똑같고, 이번 test에서는 Shell Sort가 Insertion Sort보다 빨랐다.

Insertion Sort가 더 빠른 경우도 존재함. 최악이 O(N^2)로 같으니까 데이터 형태에 따라 다른듯함.

 

 

 

5. 병합 정렬 (Merge Sort)

계속 배열을 반갈죽 내다가, 배열 내용이 1개가 되면 그 1개들 끼리 정렬해서 2개짜리가되고 이런식으로 배열을 계속 쪼개고 쪼개가지고 쪼개진 배열들끼리 정렬하는 방식이다.

이번 테스트코드는 10개의 데이터이므로

 1. 1~5 / 6~10

 2. 1~2 / 3~5 / 6~7 / 8~10

 3. {1} / {2} / {3} / 4~5 / {6} / {7} / {8} / 9~10

 4. {1, 2} / {3} / {4} / {5} / {6,7} / {8} / {9} / {10}

 5. {1, 2} / {3} / {4, 5} / {6, 7} / {8} / {9, 10}

 6. {1, 2} / {3, 4, 5} / {6, 7 } / {8, 9, 10}

 7. {1, 2, 3, 4, 5} / {6, 7, 8, 9, 10}

 8. {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

이런식으로 진행됬을 것, 근데 이거 빠른거 맞나?

정렬은 잘 작동한것을 볼 수 있다. Instruction Count는 34로 고정.

선택정렬이 45인것에 비해 벌써 30%? 정도 빨라진것을 볼 수 있음.

 

 

 

6. 퀵 정렬 (Quick Sort) | 같은 O(N lgN) 정렬 중에 가장 빠름

 첫번째 원소를 pivot으로 두고, 그 원소보다 작은 원소와 큰 원소를 분리해서 배치함.

 Pivot부터 오른쪽으로 진행하는 반복과 Pivot 정반대에서 왼쪽으로 진행하는 반복을 통해, pivot을 중점으로 정렬하고

 pivot원소를 중앙으로 이동. 이것을 반복

list[0]을 pivot 원소로 지정하고

pivot보다 작은것, 큰것끼리 모은 후에 모아진 집단 사이에 pivot을 넣음. (for문 부분 + swap)

이 작업을 반복 (doQuick 2줄)

Quick Sort는 Pivot원소가 중앙으로 가면 갈수록 빠른 정렬이 가능해진다.

 - 좌우 크기가 비슷하면 O(N lgN)   평균 속도

 - 정렬된 데이터 -> O(N^2)    Insertion Sort로 정렬된 데이터를 Quick Sort에 넣으면 근접해진다.

(함수 호출의 Inst count를 빼면 Insertion Sort를 거친건 24, 안거친건 6~ 까지 보임)

 

 

7. Heap 정렬

 Heap을 구성한 후, 배열로 구성한다.

 

 

 

8. BST

 - A[1...N] 배열에 N개 data의 BST(Balanced BST)를 구성함 : O(N lgN)

 - 이 BST를 in-order로 방문하면서 data를 A에 다시 입력 : O(N)

 => O(N lgN) + O(N) = O(N lgN)

 

 

 

9. 선형 정렬(Linear Sort)

 9-1) 기수 정렬 (Radix Sort, Bucket Sort) -> O(N)

  A[1...N] 배열에 N개의 K자릿수의 10진 정수가 들어있음. (중복은 없으며, 배열 size N은 10^k보다 작다.)

 이런식으로, 일의 자릿수부터 각 자릿수별로 정렬해서 다음 bucket에 입력.

 bucket에 입력된 데이터를 위에서 부터 차례대로 수집.

 수집한 데이터를 다음 자릿수로 다시 정렬.. 이것을 반복함.

 

 9-2) 해시 데이터 (Hashing Sort) -> O(N)

  해시는 매우 큰 size의 배열에 저장해서, 모든 항목을 검사할 필요 없이 데이터를 뽑아낼 수 있는 알고리즘임.

  예를 들어, 32767이라는 숫자를 저장할때 Hash[32767]에 저장하는 느낌?

 

  배열 내의 데이터를 모두 Hash에 넣은 뒤, 위에서부터 차례대로 수거하면 정렬됨.

  {27, 05, 13, 49}가 있으면 Hash[05] = 05; Hash[13] =13; Hash[27] = 27; Hash[49] = 49; 가 되서

  Hash[0]~Hash[M]까지 검사하면서 데이터를 수거하면 {05, 13, 27, 49}가 됨.

 

  이 Hash는 정렬을 위한 알고리즘이 아님. ( 속도만을 위한 효율을 버린 알고리즘이 정렬을 위할 수는 없다.. )