✏️ 서론
저번시간에는 DFS, BFS 문제들을 풀어봤다.
이번시간에는 정렬(sort)에 대해 알아보자.
✏️ 본론
정렬(sort)이란 데이터를 특정한 기준에 따라서 순서대로 나열 하는것을 말한다.
정렬 알고리즘으로 데이터를 정렬하면 다음 장에서 배울 이진 탐색(Binary Search)이 가능해진다.
정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 넘어가자. 정렬알고리즘의 종류는 많지만 삽입정렬, 선택정렬, 퀵 정렬, 계수정렬정도만 배우자.
보통 정렬부터 공부하면 알고리즘의 효율성을 쉽게 이해 할 수 있어 알고리즘 개론에서 초반에 정렬 알고리즘을 설명하는 경우가 많다.
이번에는 오름차순 정렬만 배울것인데, 내림차순 정렬은 오름차순 정렬을 수행 한 뒤에 결과를 뒤집어서(reversed)) 출력하면된다. 이떄, 리스트를 뒤집는 연산(revresed())은 O(N)의 복잡도로 간단히 수행 할 수 있다.
📍 선택정렬(selection_sort)
선택 정렬(selection_sort)은 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정이다
가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어진다.
수행과정은 다음과 같다.
- 초기 단계에서 모든 데이터가 정렬되어있지 않으므로, 전체 데이터 중 가장 작은 데이터를 선택한다.
- 첫 번째를 제외하고 이후 데이터 중 가장 작은 데이터를 선택해 처리되지 않은 데이터 중 가장 앞에있는 데이터와 바꾼다.
- 정렬된 데이터를 제외하고 정렬되지 않은 데이터 중 가장 작은 데이터를 선택하고 처리되지 않은 데이터 중 가장 앞에 있는 데이터와 바꾼다.
- 가장 작은 데이터를 앞으로 보내는 과정을 모두 반복한 상태의 마지막 데이터는 가만히 두어도 이미 정렬된 상태이다. 따라서 정렬을 마칠 수 있다.
n-1만큼 반복하면 된다.
array = [10, 1, 3, 4, 2, 9, 7, 8, 0, 5, 6]
for i in range(len(array)):
min_index = i
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array # 스와핑
[min_index], array[i]
print(array)
👉🏽 [0, 1, 2, 3, 4, 6, 7, 8, 9]중간에 스와프(swap) 개념이 등장했다.
이는 특정한 리스트가 주어졌을 때, 두 변수의 위치를 변경하는 작업을 의미한다.
다른 프로그래밍 언어와 다르게(임시 저장용 변수 생성 후 두 원소의 값 변경) 파이썬에서는 다음처럼 간단하게 리스트 내 두 원소의 위치를 변경할 수 있다.
data = [1, 2]
data[0], data[1] = data[1], data[0]
print(data)
👉🏽 [2, 1]💡 시간복잡도
선택정렬은 N-1번 만큼 가장 작은 수를 찾아 맨 앞으로 보내야 한다. 또한, 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다.
구현 방식에 따라 사소한 오차는 있을 수 있지만, 앞쪽의 순서대로 구현했을 경우 연산 횟수는 N + (N-1) + (N-2) + ... + 2로 볼 수 있다.
따라서, 근사치 N x (N + 1) / 2번의 연산을 수행한다고 했을 때, 가장 큰 수를 꺼내면 시간복잡도는 O(N^2)이 된다.
선택정렬은 정렬해야 할 데이터의 개수가 10,000개 이상이면 정렬 속도가 급격히 느려지므로 10,000개 이하일때 가급적 사용하도록 하자.
다음의 표를 참고하여 정렬 알고리즘 별 소요시간을 살펴보자.
| 데이터의 개수(N) | 선택 정렬 | 퀵 정렬 | 기본 정렬 라이브러리 |
|---|---|---|---|
| N = 100 | 0.0123초 | 0.00156초 | 0.00000753초 |
| N = 1,000 | 0.354초 | 0.00343초 | 0.0000365초 |
| N = 10,000 | 15.475초 | 0.0312초 | 0.000248초 |
📍 삽입정렬(insertion_sort)
삽입 정렬(insertion_sort)은 특정한 데이터를 적절한 위치에서 삽입하는 정렬이다.
더불어 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
삽입 정렬은 두 번째 데이터부터 시작한다. 왜냐하면 첫 번째 데이터는 그 자체로 정렬되어있다고 판단하기 때문이다.
소스코드는 다음과 같다.
array = [10, 1, 3, 4, 2, 9, 7, 8, 0, 5, 6]
for i in range(1, len(array)):
for j in range(i, 0, -1):
if array[j] <> array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
else:
break
print(array)
👉🏽 [0, 1, 2, 3, 4, 6, 7, 8, 9]여기서 range의 세번째 매개 변수를 넣었는데, range의 매개 변수는 3개(start, end, step)다. 세 번째 매개 변수인 step에 -1이 들어가면, start 인덱스부터 시작해 end+1 인덱스까지 1씩 감소한다.
앞의 코드에서는 j 변수가 i부터 1까지 1씩 감소한다.
💡 시간복잡도
삽입 정렬의 시간 복잡도는 O(N^2)인데, 선택정렬과 마찬가지로 반복문이 2번 중첩되어 사용했기때문이다. 꼭 반복문이 2중으로 사용되었다고 O(N^2)은 될 수 없지만, 이 알고리즘에서는 타 함수가 없기때문에 O(N^2)로 산출하였다.
삽입정렬의 장점은 현재 리스트의 데이터가 거의 정렬되어 있는 상태에서는 매우 빠르게 동작한다는 점이다.
따라서, 거의 정렬되어 있는 상태로 입력이 주어지는 문제라면 퀵 정렬등의 여타 정렬 알고리즘을 이용하는 것보다 삽입 정렬을 이용하는 것이 정답 확률을 높일 수 있다.
⚡️ [ 문제 ] 백준 알고리즘 2750
오늘 배웠던 삽입, 선택 정렬과 기존 python언어에 내장된 sort() 함수를 사용해 문제를 풀었다.
sort()선택정렬(selection_sort)삽입정렬(insertion_sort)
# sort()
n = int(input())
array = []
for i in range(n):
array.append(int(input()))
# 중복제거
array = sorted(set(array))
for i in array:
print(i)
👉🏽 입력
5
5
2
3
4
1
👉🏽 출력
1
2
3
4
5# 선택정렬(selection_sort)
n = int(input())
array = []
for i in range(n):
array.append(int(input()))
for i in range(len(array)):
min_index = i
for j in range(i+1, len(array)):
if array[min_index] > array[j]:
min_index = j
array[i], array[min_index] = array[min_index], array[i]
for i in array:
print(i)
👉🏽 입력
5
5
2
3
4
1
👉🏽 출력
1
2
3
4
5# 삽입정렬(insertion_sort)
n = int(input())
array = []
for i in range(n):
array.append(int(input()))
for i in range(len(array)):
for j in range(i, 0, -1):
if array[j] < array[j-1]:
array[j], array[j-1] = array[j-1], array[j]
else:
break
for i in array:
print(i)
👉🏽 입력
5
5
2
3
4
1
👉🏽 출력
1
2
3
4
5
⚡️ [ 문제 ] 백준 알고리즘 2751
문제는 2750과 유사하나 N의 범위가 (1 <= N <= 1,000,000)로 늘어났다.
이때는, input() 대신 sys.stdin.readline()을 사용하여 시간을 단축시키자.
또, 선택정렬과 삽입정렬을 사용했더니 시간초과 판정이 나서 기본 라이브러리인 sort()로 풀었다.
import sys
n = int(input())
array = []
for i in range(n):
array.append(int(sys.stdin.readline()))
array = sorted(array)
for i in array:
print(i)
✏️ 결론
이렇게해서 정렬의 기본 알고리즘인 선택, 삽입정렬을 배워보았다.
내일 배울 퀵 정렬, 계수 정렬을 이용해 오늘 풀었던 백준문제를 풀어보고 각 정렬들마다 어떤 차이점들이 있는지 확인해봐야겠다.
