1. 삽입정렬과 병합정렬
* 삽입 정렬(Insetion Sort)
- 선택정렬과 버블정렬과 마찬가지로 제자리 정렬(in-place sorting) 알고리즘이다.
- 삽입 정렬은 마치 카드게임에서 손 안의 패를 정렬하는 것과 같다. 카드를 새로 받으면 기존에 정렬시켜둔 카드 사이에 삽입시켜 정렬시킨다. 이에 따라 동일한 값에 대해 순서가 유지되는 안정정렬방식을 보장한다.
- 삽입 정렬을 알아보기 위해 10 5 7 1 3 이라는 5개의 숫자를 오름차순으로 정렬시켜보자.
- 삽입 정렬은 두 번째 값부터 정렬을 시작하며, 해당 값과 그 앞의 값들과만 비교한다.
- 먼저 5와 10을 비교한다. 5가 더 작으므로 10을 뒤로 이동시키고 5를 그자리에 삽입한다.
5
> 10 7 1 3
5 10 7 1 3
- 다음은 7과 10을비교한다. 7이 더 작으므로 10을 뒤로 이동시킨다. 그리고 5와 비교한다. 7이 더 크므로 두 번째자리에 삽입한다.
7
5 > 10 1 3
5 7 10 1 3
- 다음은 1과 10을 비교하여 10이 뒤로이동한다. 그리고 1과 7을 비교하여 7이 뒤로 이동하며, 5도 마찬가지로 뒤로 이동한다.
1
5 7 > 10 3
5 > 7 10 3
> 5 7 10 3
1 5 7 10 3
- 마지막으로 3도 같은방식으로 진행하고나면 아래와 같이 정렬이 끝나게 된다.
1 3 5 7 10
* 병합 정렬(Merge Sort)
- 병합 정렬은 데이터를 계속 반으로 쪼개고 원소들을 다시 합치며 정렬을 하는 방식이다. 비슷한 과정이 반복되는데 이는 재귀적인 과정이다. 이 과정에서 안정정렬을 보장한다.
- 예로 1 9 8 4 3 5 2 7 이라는 8개의 숫자를 오름차순으로 정렬시켜보자.
- 먼저 절반으로 나눈다.
1 9 8 4 | 3 5 2 7
- 아직 더 나눌 수 있으므로 다시 반씩 나눈다.
1 9 | 8 4 | 3 5 | 2 7
- 여기서 마지막으로 한 번 더 나누면 원소가 하나씩이 된다.
1 | 9 | 8 | 4 | 3 | 5 | 2 | 7
- 더 이상 나눌 수 없으므로 병합을 시작한다. 먼저 1과 9를 보자. 1이 9보다 작으므로 그대로 병합된다. 이 때 추가적인 메모리를 추가하여 거기에 병합하며 담기 시작한다.
1 9 |
- 8 과 4를 병합하면 4가 앞으로 오며 병합될 것이다.
1 9 | 4 8
- 이제 위 두 그룹을 병합한다. 가장 먼저 각 그룹의 첫 번째를 비교한다. 1이 작으므로 앞에 위치 한다.
1 O O O
- 이제 9와 4를 비교하여 4를 다음에 위치시킨다.
1 4 O O
- 마찬가지로 9와 8을 비교하여 8과 9 순서로 위치시켜 병합시킨다.
1 4 8 9
- 남은 오른쪽 네 개의 숫자도 동일한 과정을 거친다.
1 4 8 9 | 2 3 5 7
- 이제 구해진 각4개의 숫자들을 비교하여 병합한다. 다른 메모리 공간에 1과 2를 비교하여 1을 앞에 위치시키고, 4와 2를 비교하여 2를 위치시키고, 4와 3을 비교하고.. 이런 식으로 반복하고 나면 다음과 같이 정렬이 완료된다.
1 2 3 4 5 7 8 9
- 전체 과정을 요약하여 보면 다음과 같다.
1 | 9 | 8 | 4 | 3 | 5 | 2 | 7 : 가장 작은 단위로 나눠짐.
1 9 | 4 8 | 3 5 | 2 7 : 한 개씩이 정렬되어 병합됨.
1 4 8 9 | 2 3 5 7 : 두 개씩이 정렬되어 병합됨.
1 2 3 4 5 7 8 9 : 네 개씩이 정렬되어 병합됨.
- 위와 같은 재귀의 과정이 병합정렬이다.
2. 시간 복잡도
* 선택 정렬(Selection Sort)
- 선택 정렬은 최선의 경우 이동 없이 1번씩만 비교하게되므로 N 의 하한시간을 갖는다.
- 그러나 최악의 경우 루프마다 n번의 비교와 교환이 일어난다. 따라서 시간 복잡도는 O(N^2) 이다.
* 병합 정렬(Merge Sort)
- 위에서 봤었던 예시처럼 길이가 8인 경우에 최대로 나눈 크기 1부터 연산 횟수를 비교해보자.
- 크기 1인 부분 배열 2개를 병합하는 데 걸리는 연산 횟수는 최대 2번 이다. 총 4 쌍이므로 2 * 4 = 8 이라는 연산 횟수가 도출된다. 다음으로 크기 2인 부분 배열 2개를 병합하게 된다. 이 때 걸리는 연산 횟수는 최대 4번이다. 총 2쌍이므로 4 * 2 = 8 이라는 연산 횟수가 도출 된다. 마지막으로 크기 4인 부분 배열 2개를 병합하면 최대 8번의 연산횟수가 도출된다. 즉 각 단계별로 걸리는 연산횟수는 최대 n 번이다.
- 순환 깊이는 2씩 나눠지므로 logN 이다. 총 연산횟수는 NlogN 이다.
- 다음으로 이동할 때 드는 연산이 존재한다. 임시 배열에 하나씩 이동시키므로 크기 1인 경우 2번, 크기 2인 경우 4번... 총 이동은 2n 번 발생한다. 이 또한 깊이만큼 곱하면 2NlogN 이라는 연산횟수가 도출된다.
- 결과적으로 병합정렬의 연산횟수는 3NlogN 이다. 따라서 복잡도의 상한은 O(n log n)이며 하한시간도 마찬가지로 Ω(n log n) 이다. 왜냐하면 숫자들이 이미 정렬되어 있더라도 나누고 병합하는 과정이 동작하기 때문이다.
- 병합정렬은 실행시간은 빠를 수 있으나 메모리를 다른 정렬에 비해서 많이 필요로 한다는 단점이 있다.
참고
CS50
Introduction to the intellectual enterprises of computer science and the art of programming. This course teaches students how to think algorithmically and solve problems efficiently. Topics include abstraction, algorithms, data structures, encapsulation, r
cs50.harvard.edu
다 함께 배우고 성장하는 부스트코스
부스트코스(boostcourse)는 모두 함께 배우고 성장하는 비영리 SW 온라인 플랫폼입니다.
www.boostcourse.org
삽입 정렬 - 위키백과, 우리 모두의 백과사전
삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. k번째
ko.wikipedia.org
[알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
[알고리즘] 합병 정렬(merge sort)이란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
'Computer Science > Algorithm' 카테고리의 다른 글
| <알고리즘> 퀵정렬은 병합정렬보다 항상 좋은 선택인가 (0) | 2022.10.30 |
|---|---|
| <알고리즘> 퀵 소트 & 힙 소트 (0) | 2021.12.24 |
| <알고리즘> 버블정렬과 선택정렬 (0) | 2021.02.03 |
| <알고리즘> 재귀 알고리즘 (1) (0) | 2020.11.29 |
| <알고리즘> 검색 알고리즘(2) (0) | 2020.11.08 |
