정렬들(Selection, Insertion, Bubble, Quick, Merge, Heap, Radix) 비교

[ 정렬들(Selection, Insertion, Bubble, Quick, Merge, Heap, Radix)에 대하여

수행시간, 비교 횟수, Swap횟수를 통한 비교 ]

 

1) Selection Sort :

Best Case	Worst Case	Stable	In-place	비교 횟수	Swap 횟수
O( n^2 )	O( n^2 )	X	O	O( n^2 )	O( n )

분석 : 데이터의 개수가 n개 일 때, 최소값을 선택하는 데 걸리는 시간 = O( n )

-> 최솟값을 선택하여 리스트의 첫 번째 요소와 자리를 바꾼다.

안정성을 만족하지 않고, 전체 시간복잡도는 O( n^2 )을 따른다.

데이터를 0부터 n까지 매번 비교해야 하므로, n(n-1)/2 번 비교하게 되며 O( n^2 ) 이 되고,

Swap횟수는 찾은 최소값과 리스트의 첫 번째 요소와 바꿔주면 되므로, n-1번 수행되어 O( n ) 이 된다.

 

2) Insertion Sort :

Best Case	Worst Case	Stable	In-place	비교 횟수	Swap 횟수
O( n )	O( n^2 )	O	O	O( n^2 )	O( n^2 )

분석 : 리스트의 값들을 순회하며 리스트에서 정렬이 필요한 데이터는 적당한 곳에 삽입해나간다.

정렬되어 있는 부분에 새로운 레코드를 적절한 위치에 삽입해야하는 과정을 반복해야 한다.

안정성이 보장되고 이미 정렬되어있으면 O(n)이 되어 효율적이지만, 삽입하는 과정이 있으므로 데이터가 많고 정렬이 되어있지 않다면 비효율적이다.

Worst Case는 데이터가 역순으로 정렬되어 있는 경우이며, 비교 횟수는 매번 데이터들의 값을 비교하여 위치를 옮겨주는 과정을 수행해야 하므로, n(n-1)/2 번 비교하며,

Swap은 데이터를 매번 비교하여 이동하는 횟수( n(n-1)/2 ) 에, 데이터가 n개일 때, 처음 인덱스에 대하여 n-1번 만큼 수행해야 하므로 n(n-1)/2 +(n-1) = O( n^2 ) 이 되고, 결과적으로 비교 횟수와 Swap횟수 둘 다 O( n^2 )이 된다.

 

3) Bubble Sort :

Best Case	Worst Case	Stable	In-place	비교 횟수	Swap 횟수
O( n^2 )	O( n^2 )	O	O	O( n^2 )	O( n^2 )

분석 : 인접한 리스트의 요소를 매번 비교해야 하고, 비교 시마다 인접한 요소가 정렬이 되어 있지 않다면 Swap을 해야하므로, 비교 횟수의 경우에는 항상 n(n-1)/2 번 비교하게 되며,

Swap의 경우에는 Best Case의 경우에는 이미 정렬되어 Swap하지 않아도 되는 경우이므로 0이지만, Worst Case의 경우일 때에는 비교와 같이 n(n-1)/2 번 수행해야 하므로, 비교 횟수와 Swap횟수 둘 다 O( n^2 ) 이 된다.

 

4) Quick Sort :

Best Case	Worst Case	Stable	In-place	비교 횟수	Swap 횟수
O( nlogn )	O( n^2 )	X	O	O( n^2 )	O( n )

분석 : 평균적으로 가장 빠르다고 알려져 있는 정렬방법이다. 리스트를 O( n )만큼 추가적으로 할당하여 정렬하는 방법이 있긴 하지만 Stable하고 In-place하지 않으므로 보통은 추가적인 메모리를 더 필요로 하지 않는 방법을 사용한다.

pivot값을 세우고, 이 pivot값을 기준으로 왼쪽과 오른쪽을 분할하여 각각의 부분을 다시 재귀적으로 정렬하는 방법이다.

(pivot 값을 median, 즉 리스트의 중간 값으로 설정하게 되면 Worst case를 피할 수 있는 확률이 더 높아지기 때문에 효율이 높아지게 된다.)

Best Case는 왼쪽과 오른쪽 분할된 부분의 크기가 거의 균등하게 분할되는 경우이며, 분할된 Level의 크기는 logn 이며, 각 분할된 부분에 대하여 비교를 수행하는 횟수는 n 이므로, 비교 횟수는 O(logn) 이 된다.

그러나 Worst Case의 경우에는 왼쪽과 오른쪽이 불균등하게(한쪽은 1개, 한쪽은 n-1개) 분할되는 경우이며,

 

분할된 Level의 크기가 n 이 되고, 분할된 부분에 대하여 비교를 수행하는 횟수는 n 이므로 총 비교 횟수는 O( n^2 ) 이 되고, Swap횟수는 분할된 부분에 대하여만 Swap을 수행하면 되므로 비교 횟수보다 항상 적다.

 

5) Merge Sort :

Best Case	Worst Case	Stable	In-place	비교 횟수	Swap 횟수
O( nlogn )	O( nlogn )	O	X	O( nlogn )	O( nlogn )

분석 : 리스트를 두 개로 분할하는 과정을 재귀적으로 수행한 후, 다시 올라오며 각각을 정렬하며 합쳐지는 과정을 수행한다. 분할할 때에는 정렬을 하지 않으며, 전부 분할 한 후에 다시 분할된 부분을 합치며 정렬을 수행하는 방식이다.

Best Case, Worst Case에 관계없이 퀵 정렬의 이상적인 분배를 위하여 항상 균등 분할을 하게 되며, 분할된 Level의 크기는 logn 이 되며, 각 분할된 부분에서 n 번의 비교가 수행된다. 따라서 비교 횟수는 O(nlogn) 이 된다.

Swap의 경우 각 분할된 부분에서 ( n *2)번의 Swap이 수행되므로 비교 횟수는 O(nlogn) 이 된다.

 

6) Heap Sort:

Best Case	Worst Case	Stable	In-place	비교 횟수	Swap 횟수
O( nlogn )	O( nlogn )	X	O	O( nlogn )	O( nlogn )

분석 : Heap에서는 각 노드는 자식 노드의 값보다 작으면 안 된다는 성질을 가지고 있다.

n개의 노드에 대하여 완전이진트리는 log(n+1) 의 Level을 가지므로 평균 시간복잡도는 O( nlogn )이 되며,

최악의 경우에 비교는 매번 Heapify를 통해 힙을 재구성 하는 부분에서 Level의 크기( logn )에 대하여 n번 비교를 하게 되므로, O( nlogn )이 되고, Swap횟수는 heapify에서 매번 Swap이 일어나는 경우에, 루트노드와 마지막 노드를 바꿔주는 수행 횟수도 더해주어야 하므로, O( nlogn ) + O(n) = O( nlogn ) 이 된다.

 

7) Radix Sort:

Best Case	Worst Case	Stable	In-place	비교 횟수	Swap 횟수
O( d*n )	O( d*n )	O	X	O	O

분석 : 리스트의 전체를 비교하는 것이 아니라, 자리 수를 이용하여 정렬하는 방법이다.

현재 일반적인 정렬 방법의 가장 효율적인 시간복잡도는 O( nlogn )이지만, 이것보다 더 좋은 효율을 낼 수 있는 방법이기도 하지만, 정렬할 수 있는 타입이 숫자와 같이 제한적이라는 단점이 있고, 큐 방식을 이용하여 자릿수에 따라 분할하기 때문에 비교나 Swap횟수는 따로 수행하지 않아 0이 된다.

아래의 그림은 테스트 데이터(정수)의 갯수 n을 각각 100개, 1000개, 10000개, 50000개로 했을 때의 Swap횟수와 비교횟수, 수행시간의 데이터이다.

n = 100	n = 1000
n = 10000	n = 50000