0. 정렬
7 5 9 0 3 1 6 2 4 8
0 1 2 3 4 5 6 7 8 9
1. 선택정렬
- 왼쪽에서부터 하나씩(처리되지 않은 데이터) 가장 작은 데이터를 선택해서 맨 앞에 있는 데이터와 바꾸는 것을 반복한다.
- 가장 비효율적인 알고리즘이다.
7 5 9 0 3 1 6 2 4 8
0 5 9 7 3 1 6 2 4 8
0 5 9 7 3 1 6 2 4 8
0 1 9 7 3 5 6 2 4 8
...
for i in range():
print("Selection sort")시간복잡도
- 선택정렬의 시간복잡도는 O(N^2)이며, 반복문이 두 번 중첩되어 사용된다.
2. 삽입 정렬
- 왼쪽에서부터 하나씩(처리되지 않은 테이터) 좌측에 있는 데이터와 대소비교를 하여 적절한 위치에 삽입한다.
- 선택 정렬에 비해 구현 난이도가 높지만, 어느정도 정렬이 되어있는 상태라면 더 효율적이다.
7 5 9 0 3 1 6 2 4 8 # 5는 7보다 작기에 7의 왼쪽에 삽입
5 7 9 0 3 1 6 2 4 8 # 9는 7보다 크기에 7의 오른쪽에 삽입
5 7 9 0 3 1 6 2 4 8 # 0은 9보다 작고, 7보다 작고, 5보다 작기에 5의 왼쪽에 삽입
0 5 7 9 3 1 6 2 4 8 # 3은 ...
...
for i in range():
print("Insertion sort")시간복잡도
- 삽입정렬의 시간복잡도는 O(N^2)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다.
- 최선의 경우(데이터가 이미 정렬되어있는 상태) O(N)의 시간복잡도를 가진다.
3. 퀵 정렬
- 기준 데이터(Pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
- 일반적으로 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
- 병합 정렬과 더불어 대부분의 정렬 라이브러리의 근간이 되는 알고리즘이다.
- 기본적인 퀵정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.
⑤ 7 9 0 3 1 6 2 4 8 # Pivot은 5, 왼쪽에서부터 5보다 큰 숫자를 만날 때까지, 오른쪽에서부터는 5보다 작은 수를 만날때까지 이동한다.
⑤ 4 9 0 3 1 6 2 7 8 # 선택된 두 수를 비교하여 오름차순이 되도록 swap 한다.
⑤ 4 9 0 3 1 6 2 7 8
⑤ 4 2 0 3 1 6 9 7 8
⑤ 4 2 0 3 1 6 9 7 8 # 왼쪽에서부터 5보다 큰 6, 오른쪽에서부터 5보다 작은 1이 선택될 때 위치가 엇갈렸다.
1 4 2 0 3 ⑤ 6 9 7 8 # 위치가 엇갈리는 경우 '피벗'과 '작은 데이터'의 위치를 swap 한다.
1 4 2 0 3 < 5 < 6 9 7 8 # 이제 pivot(5)의 왼쪽은 모두 5보다 작고, 오른쪽은 모두 5보다 크다. 이렇게 pivot을 기준으로 데이터를 나누는 작업을 분할이라고 한다.
① 4 2 0 3 # 왼쪽 데이터 묶음안에서 동일한 방식으로 정렬을 수행한다.
⑥ 9 7 8 # 오른쪽도 동일하게 한다.
시간복잡도
- 이상적인 경우 분할이 절반씩 일어나면 전체 연산 횟수로 O(N log N)입니다.
- 너비 X 높이 = N x log N
- 하지만 최악의 경우 O(N^2)의 시간 복잡도를 가집니다.
- 첫 번째 원소를 피벗으로 삼을 때, 이미 정렬된 배열에 퀵 정렬을 수행 하면 어떻게 될까 ?
0 1 2 3 4 5 6 7 8 9
4. 계수 정렬
- 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다.
- 계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능하다.
- 데이터의 개수가 N, 데이터(양수) 중 최댓값이 K일 때, 최악의 경우에도 수행 시간 O(N+K)를 보장한다.
- 가장 작은 데이터부터 가장 큰 데이터까지의 범위가 모두 담길 수 있도록 리스트를 생성한다.
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
index 0 1 2 3 4 5 6 7 8 9
count 0 0 0 0 0 0 0 0 0 0
- 정렬할 리스트의 데이터를 확인하면서 해당 데이터가 등장하는 index의 count를 1씩 증가시킨다.
- 즉, 각각의 데이터가 총 몇 번 등장했는지를 세는 것이다.
- 기본적으로 배열에서 특정한 인덱스에 접근할 때, 알고리즘 상 상수시간의 접근이 되기 때문에 가능하다.
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
index 0 1 2 3 4 5 6 7 8 9
count 0 0 0 0 0 0 0 1 0 0
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
index 0 1 2 3 4 5 6 7 8 9
count 0 0 0 0 0 1 0 1 0 0
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
index 0 1 2 3 4 5 6 7 8 9
count 2 2 2 1 1 2 1 1 1 2
output : 0 0 1 1 2 2 3 4 5 5 6 7 8 9
5. 정리
- 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN)을 보장하도록 설계되어 있다.
