정렬 알고리즘(Selection sort, Insertion sort, Bubble sort)

Overview

정렬 문제는 임의의 배열이 주어졌을때, 규칙에 맞게 정렬된 배열을 만드는 문제이다. 올바른 규칙이란 오름차순 또는 내림차순을 말하는데 특별히 언급이 없다면 오름차순을 올바른 규칙으로 하겠다. 이번에 다룰 정렬 알고리즘은 순서대로 Selection Sort, Insertion Sort, Bubble Sort이다.

참조한 링크 사진의 출처를 제목에 적어두었다. 이렇게 잘 정리된 자료를 공유해주어 감사를 표한다.

선택 정렬(Selection Sort)

선택 정렬은 선택 자리를 하나 정하고 그 자리에 맞는 값을 찾아 넣는 과정을 수차례 반복한다. 선택 정렬은 제자리 정렬(in-place sorting) 알고리즘으로 정렬을 위해서 추가 메모리 공간이 필요없다.

위 그림에서 회색 화살표가 바로 선택자리이다. 즉 단계마다 선택자리에 값을 채워넣는데, 그 값은 이미 추가된 자리를 제외한 남아있는 후보값 중에서 최소값을 넣는 것이다. 즉 k번째 단계에서는 k위치 그리고 나머지 후방 위치에 있는 값들 중에서 최소값을 선택자리에 넣는다.

선택 정렬 시간복잡도

선택 정렬의 시간복잡도는 최선, 최악 모두 $n^2$이다. $Θ(n^2) = n + (n - 1) + ... + 1$

최선의 경우로 이미 정렬된 배열이 입력되어도 $n^2$의 연산을 항상 수행한다. (ex: [3,5,6,7,9])

삽입 정렬(Insertion Sort)

삽입 정렬은 이미 정렬된 배열에 값을 올바른 위치에 삽입하는 과정을 수 차례 반복하며 정렬하는 방식이다. 올바른 위치란 어떤 값이 해당 위치에 추가되어도 배열이 정렬된 상태를 유지하는 위치이다. 삽입정렬은 올바른 위치를 찾기 위해서 정렬된 배열의 가장 후방에서 순차적으로 올바른 위치를 찾는다.

배열에 값을 순차적으로 추가하는 것을 단계로 생각하면 아래와 같이 설명할 수 있다.

• 1단계: 이미 정렬된 배열이 없기 때문에 추가할 값 자체를 길이가 1인 정렬된 배열로 간주하고 넘어간다. 따라서 사실 첫 번째 순서는 생략하고 두 번째 단계부터 진행해도 무관하다.
• 2단계: 앞 단계에서 정렬된 배열의 값들과 추가할 값을 비교한 후, 올바른 위치에 추가할 값을 삽입한다.
• i 단계: 바로 전 단계(i-1)에서 정렬된 배열의 값들과 추가할 값을 비교한 후, 배열에 올바른 위치에 추가할 값을 삽입

삽입 정렬 시간복잡도

삽입 정렬은 최선의 경우 $Ω(n)$, 최악의 경우는 $O(n^2)$.

최선의 경우로 이미 정렬된 배열이 입력되면 $n$번의 연산으로 처리가 된다.

버블 정렬(Bubble Sort)

버블 정렬은 매 단계마다 인접합 배열 값을 서로 비교하고 교환하여 결과적으로 그 단계에서 최대값을 가장 뒤로 적재하는 과정을 반복한다. 이 인접한 배열값을 비교하고 교환하는 과정이 마치 거품이 일어나는 모습과 비슷하다고 하여 Bubbling이라고 한다.

• 1 단계: 첫 번째 위치에서 마지막 바로 전(n-1) 위치까지 순차적으로 Bubbling
• i 단계: 첫 번째 위치에서 i-1번째 위치까지 순차적으로 Bubbling

매 단계마다 이전 단계들에서 적재된 배열의 위치는 탐색에서 제외한다. 

버블 정렬 시간복잡도

버블 정렬의 시간복잡도는 최선, 최악 모두 $n^2$이다. 즉 $Θ(n^2)$이다. 

버블 정렬은 값 비교후 교환하는 연산이 무겁기 때문에 심지어 같은 시간복잡도를 가지는 다른 알고리즘보다도 느리다.

마치며

우리는 Selection Sort, Insertion Sort, Bubble Sort를 알아보았다. 모두 직관적인 방법의 정렬 알고리즘이었으며, 최악의 경우 $O(n^2)$의 성능을 보였다. 다음 장에서는 이보다 더 좋은 성능을 보이는 알고리즘을 정리해보겠다.

2021/01/13 - [IT/Algorithms] - 정렬 알고리즘(Merge sort, Quick sort, Heap sort)