Sort
기본적으로 작은순서에서 큰순서로 정렬함을 의미한다. 많은 정형화된 정렬 알고리즘들이 있고 이번 포스트에서는 정렬알고리즘들에대해서 정리해보려고한다.
기본적으로 널리알려진 정렬 알고리즘들에 대해 정리해보자면 다음과 같다.
- 삽입 정렬
- 선택 정렬
- 버블 정렬
- 셸 정렬
- 퀵 정렬
- 힙 정렬
- 병합 정렬
시간복잡도 정리
|종류|Best|Average|Worst| |:—:|:—:|:—:|:—:| |삽입 정렬 |n |n^2|n^2| |선택 정렬 |n^2 |n^2|n^2| |버블 정렬 |n^2 |n^2|n^2| |셸 정렬 |n |n^2|n^2| |퀵 정렬 |nlogn |nlogn|n^2| |힙 정렬 |nlogn |nlogn|nlogn| |병합 정렬 |nlogn |nlogn|nlogn|
삽입 정렬
- 기본개념
저장된 값을 차례로 뽑아 올바른 위치에 삽입시키며 정렬 진행
- 정렬 진행순서
[8,5,4,3,9,2,7,6,1]
1회 : index(1), 5을뽑아 내어, 8앞으로 삽입
[5,8,4,3,9,2,7,6,1]
2회 : index(2) 4을뽑아 내어, 5앞으로 삽입
[4,5,8,3,9,2,7,6,1]
3회 : index(3) 3을뽑아 내어, 4앞으로 삽입
[3,4,5,8,9,2,7,6,1]
4회 : index(4) 9을뽑아 내어, 8뒤으로 삽입
[3,4,5,8,9,2,7,6,1]
5회 : index(5) 2을뽑아 내어, 3앞으로 삽입
[3,4,5,8,9,2,7,6,1]
6회 : index(6) 2을뽑아 내어, 3앞으로 삽입
[2,3,4,5,8,9,7,6,1]
7회 : index(7) 7을뽑아 내어, 8앞으로 삽입
[2,3,4,5,7,8,9,6,1]
8회 : index(8) 6을뽑아 내어, 7앞으로 삽입
[2,3,4,5,6,7,8,9,1]
9회 : index(9) 1을뽑아 내어, 2앞으로 삽입
[1,2,3,4,5,6,7,8,9]
n^2의 시간복잡도로 정렬 완료.
선택 정렬
-
기본개념 현재 자리에 맞는 값을 탐색해 스왑하여 정렬
-
정렬 진행순서
[8,5,4,3,9,2,7,6,1]
1회 : index(0), 8 <> 1 스왑
[1,5,4,3,9,2,7,6,8]
2회 : index(1), 5 <> 2 스왑
[1,2,4,3,9,5,7,6,8]
3회 : index(2), 4 <> 3 스왑
[1,2,3,4,9,5,7,6,8]
4회 : index(4), 4 유지
[1,2,3,4,9,5,7,6,8]
5회 : index(5), 9 <> 5 스왑
[1,2,3,4,5,9,7,6,8]
6회 : index(6), 9 <> 6 스왑
[1,2,3,4,5,6,7,9,8]
7회 : index(7), 7 유지
[1,2,3,4,5,6,7,9,8]
8회 : index(8), 9 <> 8 스왑
[1,2,3,4,5,6,7,8,9]
n^2의 시간복잡도로 정렬 완료.
버블 정렬
-
기본개념 N크기의 Array를 정렬한다고 하면, 바로뒤 값과 비교를 통해 swap 하는방식으로, N-1 회 실행하여 전체 정렬을 진행한다.
-
정렬 진행순서
[8,5,4,3]
1-1회 : index(0), 8 <> 5 스왑
[5,8,4,3]
1-2회 : index(1), 8 <> 4 스왑
[5,4,8,3]
1-3회 : index(2), 8 <> 3 스왑
[5,4,3,8]
2-1회 : index(0), 5 <> 4 스왑
[4,5,3,8]
2-2회 : index(1), 5 <> 3 스왑
[4,3,5,8]
2-3회 : index(2), 5 유지
[4,3,5,8]
3-1회 : index(0), 3 <> 4 스왑
[3,4,5,8]
3-2회 : index(1), 4 유지
[3,4,5,8]
3-2회 : index(2), 5 유지
[3,4,5,8]
n^2의 시간복잡도로 정렬 완료.
셸 정렬
-
기본개념 삽입정렬을 보완한 알고리즘으로, 어느정도 정렬된 상태에서의 삽입정렬의 속도가 대단히 빠른것에서 착안한 알고리즘이다. 일정 간격(gap) 설정을 통한 작은 단위로 쪼개어 어느정도 정렬한뒤 마지막에 삽입정렬을 통해 방법이다.
-
정렬 진행순서
[8,5,4,3,9,2,7,6,1]
1회 : gap(5)
[8,5,4,3,9,2,7,6,1]
[8, , , ,9, , , ,1] > [1, , , ,8, , , ,9]
[ ,5, , , ,2, , , ] > [ ,2, , , ,5, , , ]
[ , ,4, , , ,7, , ] > [ , ,4, , , ,7, , ]
[ , , ,3, , , ,6, ] > [ , , ,3, , , ,6, ]
2회 : gap(3)
[1,2,4,3,8,5,7,6,9]
[1, , ,3, , ,7, , ] > [1, , ,3, , ,7, , ]
[ ,2, , ,8, , ,6, ] > [ ,2, , ,6, , ,8, ]
[ , ,4, , ,5, , ,9] > [ , ,4, , ,5, , ,9]
3회 : gap(1)
[1,2,4,3,6,5,7,8,9] > 삽입정렬
[1,2,3,4,5,6,7,8,9]
n^1.5의 시간복잡도로 정렬 완료.