6. Selection sort, Insertion sort, Shell sort

정렬의 설명은 오름차순을 기준으로 설명한다.

 

1. Selection sort

selection sort는

1) 포인터가 가리키는 요소를 기준으로 오른쪽에 모든 요소중에서 가장 작은 요소를 선택하고,  그것을 포인터가 가리키는 요소와 교환한다.

2) 배열의 첫번째 요소부터 시작해서, 마지막요소까지 차례대로 포인터를 옮겨가며 정렬을 시도한다.

 

포인터를 기준으로 좌측 부분배열은 항상 우측의 어떤 요소보다도 작게된다.

다음의  예시에서, 포인터는 빨간글자이며 정렬은 다음과 같이 이루어진다.

1 4 2 5 3 

1 4 2 5 3

1 2 4 5 3

1 2 3 5 4

1 2 3 4 5

 

따라서, 정렬은 입력에 관계없이 N개의 요소가 있을 때, 항상 (N-1) + (N-2) + ... + 1 + 0 ~ N^2 / 2 만큼의 비교가 일어난다.

심지어 이미 정렬되어있더라도 Quadratic time의 시간이 걸리므로 굉장히 성능이 좋지 않다.

 

2. Insertion sort

Insertion sort는

1) 포인터를 기준으로 좌측 부분배열의 맨 오른쪽 요소부터 시작해서 왼쪽방향으로 옮겨가며, 포인터가 가리키는 요소가 더 작다면 교환(삽입)함을 반복한다. 포인터가 가리키는 요소가 더 커지는 시점에 멈춘다. 

2) 배열의 첫번째 요소부터 시작해서, 마지막요소까지 차례대로 포인터를 옮겨가며 정렬을 시도한다.

 

포인터를 기준으로 좌측부분배열은 항상 정렬되어 있게된다.

다음의  예시에서, 포인터는 빨간글자이며 정렬은 다음과 같이 이루어진다.

1 4 2 5 3

1 4 2 5 3

1 4 2 5 3

1 2 4 5 3

1 2 4 5 3

1 2 3 4 5 // exch(5, 3) -> exch(4, 3)

 

만약, 이미 정렬되어있을 경우 포인터가 가리키는 요소가 더 커지는 시점에 멈추게 되므로, 포인터의 옮김만큼만의 비교가 이루어진다.  N-1 만큼의 비교가 이루어진다. 역으로 정렬되어있을 경우는, ~N^2 / 2 로 selection sort와 동일한 성능이다.

랜덤한 입력에 대하여 평균적인 성능은 ~N^2 / 4 만큼의 성능을 내게 된다. 따라서, selection sort보다는 두배정도 성능이좋다고 볼수 있다. 하지만, 여전히 Quadratic time의 시간이 걸리므로 성능이 좋다고 볼순없다.

 

3. Shell sort

shell sort는

1) 포인터를 기준으로 좌측으로 h만큼 떨어진 맨 오른쪽 요소부터 시작해서 h만큼의 간격으로 왼쪽방향으로 옮겨가며, 포인터가 가리키는 요소가 더 작다면 교환(삽입)함을 반복한다. 포인터가 가리키는 요소가 더 커지는 시점에 멈춘다.

2) 배열의 n+1 번째요소부터 시작해서, 마지막요소까지 차례대로 포인터를 옮겨가며 정렬을 시도한다.

3) 위의 1), 2) 과정을 h-sort라고 하며, h의 값을 점차 축소해서 최종적으로 1까지 축소하면서 h-sort를 시도한다.

 

다음의  예시에서, 포인터는 빨간글자이며 정렬은 다음과 같이 이루어진다.

h = 2n+1 (n=1, 3, 5) 이라고 가정한다.

 

5-sort

1 4 2 5 3 6 8 9 0

1 4 2 5 3 6 8 9 0

1 4 2 5 3 6 8 9 0

1 4 2 9 3 6 8 5 0 //exch(9, 0)

 

3-sort

1 4 2 9 3 6 8 5 0

1 4 2 9 3 6 8 5 0

1 3 2 9 4 6 8 5 0

1 3 2 9 4 6 8 5 0

1 3 2 8 4 6 9 5 0

1 3 2 8 4 6 9 5 0 //exch(6, 0), exch(2, 0)

1 3 0 8 4 2 9 5 6

 

1-sort

=> Insertion sort와 동일

 

부분적으로 정렬이 되어있을 경우, 성능이 insertion sort는 성능이 향상되기 때문에 위와 같은 큰 단위 -> 작은 단위로 정렬을 시도함으로서 효율을 높이는 것이 shell sort이다.

그렇다면 h의 값으로 어떤값을 하는 것이 좋을까? 모든 케이스에 대해서 최적화된 답은 없다.

일반적으로 3n+1의 값이면 나쁘지 않은 성능을 보인다.

그렇다면, h = 3n+1일 때 성능은 어떻게 될까?

어떤 사람은 약 몇만개의 요소를 가진 배열에 대해서 성능을 N^1.289로 어떤 사람은 2.5NlogN 으로 모델링하기도 한다.

하지만 이것은 아직 정답이 정해지지 않은 open problem이다.

중요한 점은, shell sort의 h함수를 잘 선택한다다면 특정 배열에 대해서 ~NlogN 수준까지 성능을 끌어올릴 수 있다는 점이다. 

 

4) shuffle sort

shuffle sort는 random number의 생성이 편향되지 않는다는 가정하여, random number를 카드들에 부여하고

그것의 sort함으로서 카드를 섞는 문제를 해결할 수 있다. random number의 생성은 linear time에 가능하므로,

sort알고리즘의 카드 섞기의 속도를 결정짓는 요인이 된다(최대 NlogN성능) 카드의 숫자가 많아질 수록 경우의 수가 많아지고 경우의 수가 random number의 seed의 갯수보다 많아진다면, 편향된 랜덤숫자가 생성된다.

knuth shuffle이란 것도 있는데, 이 방식은 포인터가 맨 왼쪽에서 오른쪽방향으로 진행하며, 진행단계마다 포인터의 오른쪽 중 랜덤으로 하나의 인덱스 정수를 선택(constant시간)하고 포인터가 가리키는 값과 교환시킴으로서 ~N 의 성능으로 shuffle을 구현한다. 이것은 균등한 shuffle을 보장한다.

 

5) convex hull

convex hull은 여러가지 점들이 2차원공간에 놓여있을 때, 점들을 연결하여 모든 점들을 둘러싸는 fence를 그리는 문제이다. 이 알고리즘의 해결법은 정렬을 이용하며, 그것이 성능에 결정적 영향을 미치는 요소이다.

 

이와 같이 여러 문제의 해결에 있어서 정렬이 많이 쓰이고, 이 정렬이 전체 알고리즘에 성능에 가장 큰 영향을 미치는 경우가 많기 때문에 정렬알고리즘을 이해하는 것이 중요하다.