정렬(Sort)

1. 정렬(Sort)이란?

컴퓨터 기억 공간 내에 순서 없이 배열된 자료들 중에서 특정 항목을 키로 하여 키 값에 따라 오름차순 또는 내림차순으로 자료를 재배열하는 것

2. 수행되는 장소에 따른 정렬의 구분

1) 내부정렬 - 정렬되는 자료가 적어서 자료 전체의 정렬이 주기억 장치에서 이루어지는 정렬 방식

삽입법 : 레코드의 키를 비교하여 삽입하는 방식 ex) 삽입 정렬(insertion sort), 쉘 정렬(shell sort)

교환법 : 레코드의 키를 비교하여 교환하는 방식 ex) 선택 정렬(selection sort), 퀵 정렬(quick sort), 버블 정렬(bubble sort)

선택법 : 레코드의 키들 중에서 가장 큰 값이나 작은 값을 선택하는 방식 ex) 힙 정렬(heap sort)

병합법 : 레코드의 키를 병합하는 방식 ex) 병합 정렬(merge sort)

분배법 : 레코드의 키를 구성하는 각 자릿수를 특정 버킷에 분배하여 정렬하는 방식 ex) 기수 정렬(radix sort)

2) 외부정렬 - 정렬되어야 할 자료가 매우 많아 자료를 보조 기억 장치에 기억시켜 놓은 상태에서 주기억 장치에서 처리할 수 있는 양만큼을 가져와 정렬하고 보조 기억 장치에 저장하는 과정을 반복하면서 자료 전체의 정렬이 보조 기억 장치에서 이루어지는 정렬 방식

ex) 병합 정렬(merge sort)

3. 정렬에 따른 수행 속도 비교

삽입 정렬, 선택 정렬, 버블 정렬 : O(n^2)                                                                              

- 대량의 데이터를 정렬하는 방법으로는 이용 x

쉘 정렬 : 증분에 따라 성능이 조금씩 달라지만 일반적으로 O(n(logn)^2) ~ O(n^2)의 성능을 가짐      

- 속도면에서 빠르고 안정적임. 부분적으로 정렬되어 있을 때 더 효율적.

힙 정렬 : O(nlogn)

- 힙을 생성하는데 O(n)의 수행 과정을 거치고 n번 삭제하는데 O(nlogn)의 수행 과정을 거침. 수나 형태에 무관하게 거의 고른 성능을 보여줌.

퀵 정렬 : O(nlogn)

- 보통 pivot값은 배열의 끝의 값을 이용하지만 한 번의 탐색을 통해 average 값을 pivot 값으로 설정하면 효율을 높일 수 있다. 매우 빠르고 성능이 좋지만 구간이 넓을 경우에 한하고 구간이 어느 정도 좁혀지면 그다지 빠르지 않음. 분할된 데이터 수가 적다면 삽입 or 선택 정렬이 오히려 더 빠를 수 있음.

n개의 레코드 개수가 있을때 레코드 위치를 결정하기 위해 n번의 비교를 하고 서브 파일에 대해 n/2번 비교를 하고 계속해서 n/4, n/8 ... 번 비교를 하게 됨.

병합 정렬 :

2-way 병합 정렬 알고리즘 : O(m+n)

- 이미 정렬된 두 개의 파일을 정렬하여 한 개의 다른 파일로 만드는 것. 두개의 while문은 두 배열중 어느 한쪽이 끝나면 다른 한쪽에 있는 자료를 새로운 배열에 비교 없이 넣는 연산을 수행하므로 첫 번째 파일 개수를 m, 두 번째 파일 개수를 n이라 하면 두 개의 정렬된 파일을 병합하는데 이를 더한 수행 시간이 소요됨.

n-way 병합 정렬 알고리즘 : O(nlogn)

- n개의 데이터를 분할하는데 O(n), 분할을 한 번 할때마다 부분 배열의 길이가 절반으로 줄기 때문에 log₂n회 분할됨.

기수 정렬 : O(n)

- 각 버킷을 배열을 이용하기 보다는 연결리스트를 이용하여 처리하면 기억 장소를 절약할 수 있음.

  정렬될 자료의 개수가 n일때 비교 횟수는 각각의 레코드에 대해 n번씩 수행됨 -> O(n), 자리수가 b일때 O(bn)의 수행 시간이 걸리지만 b를 상수 취급.

4. 빅오표기법으로 본 수행 시간 비교(레코드의 수, 키값 무시. 병합정렬 제외)

기수 정렬(O(n)) > 퀵 정렬(O(nlogn)) > 힙 정렬(O(nlogn)) > 쉘 정렬(O(n(logn)^2) ~ O(n^2)) >= 삽입 정렬, 선택 정렬, 버블 정렬(O(n^2))