버블 정렬(거품 정렬)
거품 정렬은 가장 단순한 정렬 알고리즘이다.
아이디어는 다음과 같다. 첫번째와 두번째 값을 비교하고, 두번째와 세번째 값을 비교하고, ... n-1번째와 n번째 값을 비교합니다. 이 과정에서 순서가 맞지 않은 값을 서로 교환해준다. 이런 절차를 정렬이 될 때 까지 반복한다.
코드를 작성하는 것은 어렵지 않지만, 상당히 비효율적인 알고리즘이기 때문에 성능이 다른 알고리즘에 비해 좋지 않다는 단점이 있다.
버블 정렬의 시간복잡도는 O(N2) 이다.
버블 정렬을 구현한 코드는 다음과 같다.
n = int(input())
m = list(map(int, input().split()))
for i in range(n):
cnt = 0
for j in range(1, n):
if m[j] >= m[j-1]:
continue
else:
m[j],m[j-1] = m[j-1], m[j]
cnt += 1
if cnt == n-1:
break
print(' '.join(str(_) for _ in m))
선택 정렬
선택 정렬은 다른 정렬 알고리즘보다 더 일상적인 방법의 알고리즘이다.
주 아이디어는 다음과 같다.
1. 전체 값 중 가장 작은 값을 찾음
2. 해당 값을 맨 첫번째에 배치함
3. 첫번째 값을 제외하고 가장 작은 값을 찾아 두번째에 배치함
4. 두번째, 세번째, ... n-1번째 값을 제외하고 가장 작은 값을 찾아 정해진 위치에 배치함.
중간에 정렬된 상태라면 종료될 수 있는 버블 정렬과는 다르게, 반드시 번의 비교 연산을 수행해야 하기 때문에 약 번의 연산을 필요로 한다.
따라서, 시간복잡도는 이다.
선택 정렬을 구현한 코드는 다음과 같다.
n = int(input())
m = list(map(int, input().split()))
for i in range(n):
min_index = i
for j in range(i+1, n):
if m[min_index] > m[j]:
min_index = j
m[min_index], m[i] = m[i], m[min_index]
print(' '.join(str(_) for _ in m))
삽입 정렬
삽입정렬은, 앞에서부터 순서대로 보면서 앞에 있는 모든 원소가 정렬이 되어 있다는 가정 하에서 현재 원소의 위치를 적절하게 집어넣는 정렬이다.
아이디어는 다음과 같다.
[2, 3, 6, 9, 5, 1, 7]
현재 4번째 원소(9)까지 정렬이 되어있고, 5번째의 원소(5)를 정렬할 차례라고 가정해보자.
1) 4번째 원소와 5번째의 원소를 비교한 후, 앞의 원소의 크기가 더 크면, 두 원소의 위치를 바꿔준다. -> [2, 3, 6, 5, 9, 1, 7]
2) 3번째 원소와 5번째 원소를 비교한 후, 앞의 원소의 크기가 더 크면, 두 원소의 위치를 바꿔준다. -> [2, 3, 5, 6, 9, 1, 7]
3) 2번째 원소와 5번째 원소를 비교한다. 뒤의 원소의 크기가 더 크므로, 더 이상 정렬을 진행하지 않는다.
4) 지금까지 진행한 곳까지의 원소들을 전부 오름차순으로 정렬한 상태를 유지하며 위 1,2, 3번과정을 반복한다.
n개의 원소에 대해 값 삽입을 수행해야 하는데, 2번째 원소의 경우엔 최대 1개의 원소를 이동해야 하고, 3번째 원소의 경우엔 최대 2개의 원소를 이동해야 하며, n번째 원소까지 삽입하는 경우엔 최대 개의 원소가 이동해야 하므로 결과적으로 최대 개의 원소가 이동해야 하기 때문에, 시간복잡도는 이다.
삽입 정렬을 구현한 코드는 다음과 같다.
n = int(input())
m = list(map(int, input().split()))
for i in range(1, n):
index = i - 1
key = m[i]
while index >= 0 and m[index] > key:
if key < m[index]:
m[index + 1] = m[index]
index -= 1
m[index + 1] = key
print(' '.join(str(_) for _ in m))기수 정렬
기수 정렬은 맨 뒤에 있는 자릿수 부터 해당 자리수를 기준으로 정렬한 뒤, 점점 앞으로 이동하며 각 자리수를 기준으로 정렬하다가 최종적으로 가장 높은 자리수를 기준으로 정렬하는 방법이다.
기수 정렬의 시간복잡도는 으로, 여기서 는 자릿수를 의미한다. 각각의 데이터에 대해서 매 자릿수마다 분류작업을 하기 때문에, 분류작업이 K번 반복된다고 볼 수 있다.
정렬 간의 속도 비교
- 거품 정렬의 경우, 일반적으로 셋 중 가장 느리다. 그러나 정렬된 배열의 경우, sorted의 값이 계속 true이기 때문에 시간이 매우 빨라진다.
- 선택 정렬의 경우 배열의 상태와 상관 없이, 1번째로 작은 원소를 찾고, 2번째로 작은 원소를 찾고, ... 하는 과정을 거치기 때문에 어떠한 상황이던 동일한 시간을 보여준다.
- 삽입 정렬의 경우 일반적으로는 가장 빠르나, 값이 반대로 정렬되어 있는 경우 성능이 많이 떨어진다는 단점이 있다. 또한, 앞 배열에 값을 삽입하는 알고리즘의 특성상 이미 정렬된 배열에 추가적으로 값을 몇개 추가하여 정렬하는 경우에 좋은 성능을 보여준다.
병합 정렬