15 Jan 2020

Sanjoy Dasgupta가 저술한 책인 Algorithms과 이기창님의 블로그, Heee님의 블로그를 참고하였다.

그 밖의 정렬 알고리즘

다른 정렬 알고리즘을 간단하게 살펴보자.

1-1. Insertion Sort(삽입 정렬)

배열의 모든 요소를 앞에서부터 차례대로, 이미 정렬된 (앞의) 배열부분과 비교하여 자신의 위치를 찾아 삽입하며 정렬을 완성하는 알고리즘

방법은 다음과 같다. 데이터의 요소가 $n$개일 때,

1. 두번째 요소와 앞의 배열부분(첫번째 요소)을 비교해 정렬
2. 세번째 요소와 앞의 배열부분(첫번째, 두번째 요소)을 비교해 정렬
3. 위 과정을 반복해 최종적으로 $n$번째 요소와 앞의 배열부분을 비교해 정렬하며 마무리

다음 데이터의 배열로 예를 들어보자

5, 2, 4, 6, 1, 3

2를 꺼내서 앞에 이미 정렬된 배열부분(5)과 비교한다. 5>2 이므로 자리를 바꿔준다

2, 5, 4, 6, 1, 3

4를 꺼내서 앞의 이미 정렬된 배열부분(2, 5)과 비교한다. 먼저 5와 비교하고, 5>4 이므로 자리를 바꿔준다. 그 뒤, 2와 비교하고, 4>2 이므로 그대로 둔다. 이 과정을 쭉 반복하면 다음과 같이 정렬을 완성할 수 있다.

2, 4, 5, 6, 1, 3　…　2, 4, 5, 6, 1, 3　…　1, 2, 4, 5, 6, 3　…　1, 2, 3, 4, 5, 6

1-2. Insertion Sort(삽입 정렬)의 특징

• Stable 하다.

  앞의 배열부분과 비교할 때 배열부분 중 같은 값이 있으면 swap하지 않기 때문이다.

• In-place 하다.

1-3. Insertion Sort(삽입 정렬)의 장단점

• 장점

  (1) 안정적이다.

  (2) 알고리즘 자체가 매우 간단하므로 레코드 수가 적을 경우 다른 정렬방법보다 유리할 수 있다.

  (3) 데이터 요소 대부분이 이미 정렬되어 있는 경우 매우 효율적이다.

• 단점

  (1) 비교적 많은 요소들이 이동할 수 있다.

  (2) 레코드 수가 많은 경우 적합하지 않다.

1-4. Insertion Sort(삽입 정렬)의 시간복잡도

• Best Case

  요소를 선택해 앞의 배열부분과 비교할 때 이동 없이 1번만 비교하면 되는 경우

  이 경우 비교하는 시간이 $O(1)$, 요소가 $n$개 이므로 시간복잡도는 $O(n)$

• Average, Worst Case

  요소를 선택해 앞의 배열부분과 비교할 때 앞의 모든 배열부분과 비교해야 하는 경우

  ex) 8, 7, 6, 5, 4, 3, 2, 1 —> 두번째 요소 7부터 앞의 8과 비교해 바꿔주고, 그 다음 요소 6을 앞의 7, 8과 비교해 바꿔주고, 그 다음 요소 5를 앞의 8, 7, 6과 비교해 바꿔주고… 끔찍

  따라서 비교하는 시간은 $O(1)$ 이지만, 요소가 $n$개 일 때 하나의 요소가 앞의 모든 배열부분과 비교를 하게 되면, 두번째 인덱스 요소는 1번, 세번째 인덱스 요소는 2번 … $n$번째 인덱스 요소는 $n-1$번 비교하므로 $(1 + 2 + 3 + … + n-1) = \frac {n(n-1)} 2 = O(n^2)$

2-1. Bubble Sort(버블 정렬)

서로 인접한 두 원소를 비교하여 크기 순서대로 정렬하는 알고리즘. 여러 번의 회전을 통해 정렬이 이루어진다.

방법은 다음과 같다. 데이터의 요소가 $n$개일 때,

1. 첫번째 요소와 두번째 요소를 비교해 정렬
2. 두번째 요소와 세번째 요소를 비교해 정렬
3. 위 과정을 반복해 $n - 1$번째 요소와 $n$번째 요소를 비교해 정렬
4. 이렇게 되면 가장 큰 값이 $n$번째 인덱스에 위치하게 됨. 지금까지가 1회전이다. 그리고 2회전을 시작한다. 1회전을 통해 구한 가장 큰 값을 제외하고 다시 1~3과정을 반복한다. 이를 $(n-1)$회전 시행하면 정렬을 완성할 수 있다.

cf) 선택 정렬이 두번째 요소와 첫번째 요소, 세번째 요소와 첫, 두번째 요소… 순으로(거꾸로 한꺼번에) 비교하는 거라면, 버블 정렬은 첫번째 요소와 두번째 요소, 두번째 요소와 세번째 요소…순으로(순차적으로 하나씩) 비교한다.

다음 데이터의 배열로 예를 들어보자.

7, 4, 5, 1, 3

7과 4를 비교한다. 7 > 4 이므로 바꿔준다.

4, 7, 5, 1, 3

5와 7을 비교한다. 7 > 5 이므로 그대로 바꿔준다.

4, 5, 7, 1, 3

위 과정을 반복하면 최종적으로 4, 5, 1, 3, 7을 얻을 수 있다. 가장 큰 값인 7이 맨 뒤로 오게 되었다. 이것으로 1회전을 마치고 이제는 가장 큰 값인 7을 제외한 나머지 값들로 2회전을 시작한다. 과정은 다음과 같다. 다시 한번 말하지만 7은 이미 가장 큰 값이므로 시간적 효율을 위해 가만히 냅둬야한다.

4, 5, 1, 3, (7)　…　4, 1, 5, 3, (7)　…　4, 1, 3, 5, (7)

2회전 결과 두번째로 큰 값인 5를 얻게 되었다. 이제 5와 7을 제외한 나머지 값들로 3회전을 시작한다. 다 하면 또 4회전을 시작한다. 총 (요소 개수 - 1)번만큼 위 과정을 반복해주는 것이다. 최종 결과는 다음과 같다.

1, 3, 4, 5, 7

2-2. Bubble Sort(버블 정렬)의 특징

• Stable 하다.

  만약 세번째 값과 네번째 값을 비교하는데 두 값이 같으면 swap하지 않기 때문이다.

• In-place 하다.

2-3. Bubble Sort(버블 정렬)의 장단점

• 장점

  구현이 간단함

• 단점

  (1) 순서를 고려하지 않고 인접한 요소끼리 교환한다. 따라서 하나의 요소가 가장 왼쪽에서 오른쪽으로 이동하기 위해서는 배열의 모든 요소와 비교&교환되어야 한다.

  (2) 어떤 요소가 최종 정렬되었을 때 인덱스가 $n$이라고 하자. 그런데 이미 그 요소가 정렬 전에 인덱스 $n$에 있음에도 불구하고, 인접한 요소끼리 막 바꿔주다보니 쓸데없이 여기저기 옮겨다닐 수 있다. 이 점은 매우 치명적인 단점이기 때문에 버블정렬은 거의 쓰이지 않는다.

2-4. Bubble Sort(버블 정렬)의 시간복잡도

• Best, Average, Worse Case

  버블정렬의 시간복잡도는 비교 횟수와 교환 횟수의 합 비례한다.

  먼저 비교 횟수를 보자.

  요소의 개수가 $n$개일 때, 1회전의 경우 첫번째 요소와 두번째 요소, 두번째 요소와 세번째 요소…순으로 비교한다. 따라서 총 $n-1$회만큼 비교한다. 마찬가지로 2회전일 때는 마지막 값을 제외하므로 $n-2$회 비교한다. 따라서 전체 비교 횟수는 $n-1 + n-2 + … + 1 = \frac {n(n-1)}2$이다.

  교환 횟수는 마찬가지로, 저렇게 비교될 때마다 교환된다고 하면 똑같이 $\frac {n(n-1)} 2$이다.

  따라서 총 시간복잡도는 $2 \times \frac {n(n-1)} 2 = O(n^2)$이다.

3-1. Selection Sort(선택 정렬)

최대값(혹은 최소값)을 찾은 뒤 맨 뒤(혹은 맨 앞)의 값과 교환하며 정렬하는 알고리즘. 여러 번의 회전을 통해 정렬이 이루어진다.

cf) 비교 횟수 측면에서는 하나의 요소가 나머지 모든 요소와 비교되므로 버블정렬과 같지만, 교환 횟수 측면에서는 하나의 요소가 최대값이랑만 교환되기 때문에 선택정렬이 더욱 효율적이다.

방법은 다음과 같다. 데이터 요소의 개수가 $n$개일 때,

1. 요소 중, 최대값과 맨 끝의 값의 위치를 변경
2. 맨 끝의 값 제외하고, 나머지 요소 중 최대값과 맨 끝의 값의 위치를 변경
3. 위 과정을 $n - 1$번 반복

사진으로 예를 들면 다음과 같다.

3-2. Selection Sort(선택 정렬)의 특징

• UnStable 하다.

  예를 들어보자. 괄호 안 숫자는 n번째 숫자라는 뜻이다.

  5(1), 4, 5(2), 2, 3

  최소값을 기준으로 정렬하면 2가 최소값이므로 맨 앞의 값과 위치를 변경하면 다음과 같다.

  2, 4, 5(2), 5(1), 3

  5의 index가 서로 swap된 것을 알 수 있다.

• In-place 하다.

3-3. Selection Sort(선택 정렬)의 장단점

• 장점

  자료 이동 횟수가 미리 결정된다

• 단점

  안정적이지 않다.

3-4. Selection Sort(선택 정렬)의 시간복잡도

• Best, Average, Worst Case

  버블 정렬과 마찬가지로 비교 횟수와 교환 횟수의 합에 비례한다

  요소의 개수가 $n$개일 때, 1회전에서 최대값을 찾는 시간이 최대 $n-1$이고, 2회전에서는 $n-2$. 쭉 가다보면 마지막에는 1. 그리고 끝의 값과 비교하는 시간은 $O(1)$이므로 비교 횟수의 시간복잡도는 $n-1 + n-2 + … + 1 = \frac {n(n-1)}2$

  교환 횟수는 마찬가지로, 저렇게 비교될 때마다 교환된다고 하면 똑같이 $\frac {n(n-1)} 2$이다.

  따라서 총 시간복잡도는 $2 \times \frac {n(n-1)} 2 = O(n^2)$이다.