Selection Sort, Shell Sort

Selection Sort

가장 작은 원소를 array의 앞에 놓는 것은 bubble sort와 유사하다.

 

다만 bubble sort는 원소를 옮길 때 주변의 원소와 위치를 바꾸는 것을 반복하여 옮기는 반면,

selection sort는 array를 scan하여 가장 작은 원소를 찾고 array의 가장 첫번째 원소와 위치를 바꾼다.

 

Selection Sort

가장 작은 원소의 index를 찾아야 하기 때문에 i번째 iteration 마다 n-i번의 비교를 하게 된다.

 

Best Case : 0번 위치 바꿈, O(n^2/2)번의 비교

Worst Case : n-1번의 위치 바꿈, O(n^2/2)번의 비교

Average Case : O(n)번의 위치 바꿈, O(n^2/2)번의 비교

 

Bubble Sort와 비교하면 위치를 바꾸는 횟수가 매우 줄어든다.

 

 

	Insertion	Bubble	Selection
Comparisons
Best Case	O(n)	O(n^2)	O(n^2)
Average Case	O(n^2)	O(n^2)	O(n^2)
Worst Case	O(n^2)	O(n^2)	O(n^2)
Swaps
Best Case	0	0	0
Average Case	O(n^2)	O(n^2)	O(n)
Worst Case	O(n^2)	O(n^2)	O(n)

 

Shell Sort

n size를 가진 array x를 생각하자.

이 x를 짝수번째 index를 가진 element들을 포함하는 array와 홀수번째 index를 가진 element들을 포함하는 array로 나눠보자.

 

각각의 array를 따로 sort하고 그 두 개의 array에 대해 insertion sort를 수행하여 x를 sort한다면 효율적으로 sort할 수 있다.(insertion sort는 거의 정렬된 array에 대해서 효율적이기 때문)

 

정확한 절차는 다음과 같다.

1. 2개의 element를 가진 n/2개의 sublist들을 만들어 각각의 sublist에 대해 insertion sort를 수행한다.

 

2. 4개의 element를 가진 n/4개의 sublist들을 만들어 각각의 sublist에 대해 insertion sort를 수행한다.

.

.

.

log(n) . n개의 element를 가진 1개의 sublist에 대해 insertion sort를 수행한다.

 

Shell Sort

 거의 정렬된 경우가 아니라면 Shell Sort가 Insetion Sort보다 효율적이라고 한다.

 

average case performance가 O(n^1.5)로 insertion sort보다 좋은 performance를 보인다.

 

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업