이것이 코딩테스트다에 있는 정렬은 다음과 같다.
- 선택정렬
- 삽입정렬
- 퀵정렬
- 계수정렬
1. 선택정렬
선택정렬은 가장 작은 값을 선택해 앞으로 보내는 과정을 반복하여 배열을 정렬해준다.
예를 들어 [3, 2, 5, 1, 4]라는 배열이 있다면, 이 배열에서 가장 작은 값인 1을 맨 앞의 3이랑 위치를 바꿔준다.
[1, 2, 5, 3, 4]에서는 이미 정렬된 1을 제외한 [2, 5, 3, 4] 중 가장 작은 데이터인 2를 맨 앞으로 보낸다. (2가 이미 맨 앞의 숫자라 달라진 점은 없다.)
그 다음엔 [1, 2, 5, 3, 4]에서 이미 정렬된 1, 2를 제외한 [5, 3, 4] 중 가장 작은 데이터인 3을 맨 앞의 5랑 바꾼다.
[1, 2, 3, 5, 4]에서 같은 방식으로 남은 5, 4의 위치를 바꿔주면 완전히 정렬되어 [1, 2, 3, 4, 5]가 된다.
코드를 직접 작성해보았다.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
for target in range(len(array) - 1):
# 가장 작은 값의 인덱스 저장하는 변수. (target으로 초기화시킴)
minIdx = target
for i in range(target + 1, len(array)):
# 더 작은 값이 나타난다면 업데이트
if array[i] < array[minIdx]:
minIdx = i
# 가장 작은 값을 맨 앞의 원소와 swap
array[target], array[minIdx] = array[minIdx], array[target]
# swap 1번 할 때마다 출력
print(array)코드 실행 결과는 다음과 같다. 앞부터 하나씩 작은 순서대로 채워지는 것을 알 수 있다.
선택 정렬은 총 N - 1번 작은 수를 앞으로 위치시킨다. 그리고 한 번 앞으로 위치시킬 때 처음엔 N - 1번, 두 번째엔 N - 2번, ... 마지막엔 1번으로 총 N(N - 1)/2번의 연산이 필요하다. 따라서 시간복잡도는 O(N^2)이다.
2. 삽입정렬
삽입정렬은 맨 앞에서부터 각 원소를 제 위치에 삽입해주는 정렬방식이다. 즉, 삽입정렬은 맨 앞에서부터 차례로 정렬해준다.
예를 들어 [3, 2, 5, 1, 4]라는 배열을 삽입정렬로 정렬해보자.
1번 인덱스의 2를 [3]의 앞, 뒤 중 알맞은 위치에 삽입한다. 따라서 [2, 3]이 된다.
2번 인덱스 5를 [2, 3] 알맞은 위치에 삽입한다. 따라서 [2, 3, 5]가 된다.
3번 인덱스의 1을 [2, 3, 5]의 알맞은 위치에 삽입한다. 따라서 [1, 2, 3, 5]가 된다.
4번 인덱스의 4를 [1, 2, 3, 5]의 알맞은 위치에 삽입한다. 따라서 [1, 2, 3, 4, 5]로 완벽하게 정렬된다.
코드를 직접 작성해보았다.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
for target in range(1, len(array)):
# target부터 1까지 도는 for문
for i in range(target, 0, -1):
# 앞번호 인덱스와 비교하여 역순이라면 swap
if array[i] < array[i - 1]:
array[i - 1], array[i] = array[i], array[i - 1]
# 순서가 올바르다면 더이상 swap 안함.
else:
break
print(array)위 코드의 실행 결과는 다음과 같다. 앞의 것들끼리 순서가 점점 맞춰지는 것을 볼 수 있다.
첫째줄 : 5, 7이 정렬됨 (원래 정렬되어있었음.)
둘째줄 : 5, 7, 9가 정렬됨. (원래 정렬되어있었음.)
셋째줄 : 5, 7, 9, 0이 0, 5, 7 ,9로 정렬됨.
넷째줄 : 0, 5, 7, 9, 3이 0, 3, 5, 7, 9로 정렬됨. 3이 0과 5 사이에 삽입됨.
다섯째 줄: 0, 3, 5, 7, 9, 1이 0, 1, 3, 5, 7, 9로 정렬됨. 1이 0과 3 사이에 삽입됨.
...
반복실행하여 0~9가 모두 정렬됨.
삽입 정렬은 1번 인덱스부터 N - 1번 인덱스까지 총 N - 1번의 위치 설정이 실행되고, 각 위치 설정마다 연산 횟수가 1번, 2번, 3번, ... N - 1번 실행됨. 즉 1 + 2 + ... + N - 1 = N(N - 1)/2번 연산이 실행되고 따라서 시간복잡도는 O(N^2)이다.
하지만 이것은 최악의 경우에서의 시간복잡도이다.
예를 들어 [4, 3, 2, 1, 0] 처럼 역순으로 정렬되어있는 배열을 삽입정렬을 이용해 정렬시킨다고 생각해보자.
먼저 3의 위치가 4 앞으로 이동하게 되어 1번 연산이 실행된다. [3, 4, 2, 1, 0]
2의 위치가 3 앞으로 이동할 때 까지 총 2칸 움직여야하므로 2번의 연산이 실행된다. [2, 3, 4, 1, 0]
(2가 4랑 swap된 후에 다시 3이랑 swap되므로 2번의 연산이라고 한 것이다.)
같은 방식으로 1도 3번의 연산 후에 정렬되어 [1, 2, 3, 4, 0]이 되고,
0은 4번의 연산 후에 정렬되어 [0, 1, 2, 3, 4]가 된다.
위와 같이 역순일 때 시간복잡도가 O(N^2)인 것이다.
그렇다면 최고의 상황에서는 어떨까?
이미 정렬되어있는 배열 [0, 1, 2, 3, 4]를 생각해보자.
먼저 1은 0 바로 뒤의 위치가 맞으므로, 원래 상태 유지한다.(크기 비교 한 번 하므로 연산 1회) [0, 1, 2, 3, 4]
2도 마찬가지로 1 뒤의 위치가 맞으므로 원래 상태 유지.(연산 1회) [0, 1, 2, 3, 4]
3도 마찬가지로 2 뒤의 위치가 맞으므로 원래 상태 유지.(연산 1회) [0, 1, 2, 3, 4]
4도 마찬가지로 3 뒤의 위치가 맞으므로 원래 상태 유지.(연산 1회) [0, 1, 2, 3, 4]
따라서 총 N - 1번의 연산만 하기 때문에 시간복잡도는 O(N)이다.
이에 따라 보통의 경우에는 O(N)보단 크지만 O(N^2)보다는 작은 시간복잡도를 가진다는 것을 알 수 있다.
3. 퀵정렬
퀵정렬은 한 개를 pivot(피벗)으로 정하고 피벗보다 작은 것은 피벗의 왼쪽으로, 피벗보다 큰 것은 피벗의 오른쪽으로 위치시킨다. 그 후 양 옆의 배열을 또 같은 방식으로 반복하여 정렬하는 방식이다.
[3, 2, 5, 1, 4]라는 배열이 있다고 가정해보자.
피벗은 배열의 첫 번째 원소라고 규칙을 정하면, 피벗은 3이 되고, 피벗보다 작은 2와 1은 3의 왼쪽에, 피벗보다 큰 5와 4는 3의 오른쪽에 배치되어 [2, 1, 3, 5, 4]가 된다.
재귀적으로 3의 왼쪽 배열과 오른쪽 배열도 같은 방식으로 정렬한다.
[2, 1]에서는 피벗이 2이고, 피벗보다 작은 1은 2의 왼쪽에 위치하게 된다. [1, 2, 3, 5, 4]
또한, [5, 4]에서의 피벗은 5이고 피벗보다 작은 4는 5의 왼쪽에 위치하게 된다. [1, 2, 3, 4, 5]
코드 관련 알고리즘은 이것이 코딩테스트다 강의를 보고 배웠다.
https://www.youtube.com/watch?v=EuJSDghD4z8&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=25
아래는 내가 직접 구현한 코드이지만, 깔끔하지 못하게 구현하였다.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
# 퀵정렬 : 시간복잡도 O(NlogN)
# 최악의 상황의 시간복잡도 : O(N^2)
def oneSort(start, end):
print(array, start, end)
# 재귀의 종료조건
if start == end:
return
# 피벗은 배열의 첫 번째 원소
pivot = array[start]
# left는 배열의 1번 인덱스부터 시작
left = start + 1
# right는 마지막 인덱스부터 시작
right = end
while True:
# left에 있는 원소가 피벗보다 클 때까지 left += 1
while array[left] < pivot:
left += 1
# 끝에 도달하면 예외처리
if left > end:
# swap 한번 해주고
array[end], array[start] = array[start], array[end]
# start ~ end - 1을 정렬하는 함수 호출
oneSort(start, end - 1)
return
# right에 있는 원소가 피벗보다 작을 때 까지 right -= 1
while array[right] > pivot:
right -= 1
if right <= start:
# start + 1 ~ end을 정렬하는 함수 호출
oneSort(start + 1, end)
return
# left와 right가 교차되지 않았다면 swap해주고
if left < right:
array[left], array[right] = array[right], array[left]
# 교차되었다면 피벗과 right의 원소를 swap해줌
else :
array[right], array[start] = array[start], array[right]
# 그리고 양 옆의 배열에 대해 정렬해주는 함수 재귀적으로 호출
oneSort(start, right - 1)
oneSort(right + 1, end)
break
oneSort(0, len(array) - 1)위의 코드의 결과는 다음과 같다.
첫번째 줄 : 피벗인 5보다 작은 1, 4, 2, 0, 3을 5의 왼쪽으로, 6, 9, 7, 8을 5의 오른쪽으로 이동시킴.
두 번째 줄 : 0~4 사이의 인덱스를 정렬시킴. 피벗인 1보다 작은 0은 왼쪽으로, 1보다 큰 4, 2, 3은 오른쪽으로 이동시킨다.
...
계속하여 재귀적으로 정렬하게 되고 결국 0~9까지 모두 정렬된다.
나동빈님의 코드를 보고 다시 깔끔하게 구현해보았다.
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quickSort(start, end):
# 종료 조건 (start가 end보다 크게 되어도 종료시킴)
if start >= end:
return
print(array, start, end)
pivot = array[start]
left = start + 1
right = end
# left가 right보다 크거나 같다면 반복
while left <= right:
# left가 end보다 작거나 같을 때까지만 반복
while left <= end and array[left] < pivot:
left += 1
# right가 start보다 크거나 같을 때까지만 반복
while right >= start and array[right] > pivot:
right -= 1
# left와 right가 엇갈리지 않았다면 둘이 swap
if left <= right:
array[left], array[right] = array[right], array[left]
# 엇갈렸다면 피벗과 right swap
else :
array[start], array[right] = array[right], array[start]
# 양 옆의 배열을 정렬하는 함수 재귀적으로 호출
quickSort(start, right - 1)
quickSort(right + 1, end)
quickSort(0, len(array) - 1)
print(array)left와 right를 증가/감소시키는 while문에서 범위 밖으로 넘어갈 때를 따로 구현하는 것 보다 while문의 종료 조건에 넣으니 훨씬 깔끔하게 바뀌었다. 재귀함수도 각각의 while문에서 호출하는 것이 아니라 마지막에만 두 번 호출하였다.
우리가 구현한 퀵정렬의 시간복잡도는 이상적인 상황에서(계속해서 절반씩 나뉘어진다는 가정 하에) 시간복잡도가 O(NlogN)이다. 간단히 설명하자면
위의 그림처럼 길이가 N인 배열의 연산을 logN번 하기 때문에 O(NlogN)이다. 하지만, 이는 절반씩 계속해서 나뉘었을 때의 이야기이다.
만약 이미 정렬되어있는 배열 [0, 1, 2, 3, 4]를 퀵정렬을 이용해 정렬시킨다고 가정해보자.
먼저 피벗이 0일 때는 0보다 큰 1, 2, 3, 4를 오른쪽에 둔다. 이 때 총 N번의 연산을 한다. [0, 1, 2, 3, 4]
0의 오른쪽 원소들에서도 마찬가지로 N - 1번의 연산을 하게 되고, 피벗이 2, 3, 4일때 모두 마찬가지로 N - k번 연산을 하게 된다.
따라서 총 N번의 정렬을 N개의 연산으로 하기 때문에 O(N^2)이 된다.
강의를 보면 더 쉽게 이해할 수 있을 것이다.
이건 우리가 직접 구현한 코드에서 최악의 경우 O(N^2)인 것이고, 파이썬 내장함수의 sort는 최악의 경우에도 O(NlogN)을 보장하는 퀵정렬을 사용한다고 하였다.
4. 계수정렬
계수정렬은 특정 경우에만 가능하지만, 조건만 충족된다면 굉장히 빠르게 실행될 수 있는 방법이다. 배열안에 있는 원소의 최댓값이 K라고 할 때 길이가 K + 1인 카운팅배열을 하나 만들어준다. 배열에 들어있는 수를 인덱스삼아 카운팅배열에 +1을 해 준다.
예를 들어 [0,0,2,3,5]라는 배열이 있다고 가정하면 0이 2개, 2가 1개, 3이 1개, 5가 1개이므로 이의 카운팅배열은 [2, 0, 1, 1, 0, 1]이 되는 것이다. 즉, 카운팅배열에는 각자의 인덱스에 해당하는 수가 총 몇 개 있는지를 저장하는 것이다.
모두 저장했으면 카운팅배열을 하나하나 돌면서 차례로 인덱스를 '안에 저장된 수만큼' 출력해주면 된다.
아래는 내가 직접 구현한 코드이다.
array = [2, 0, 0, 5, 3]
maximum = max(array)
countArray = [0 for _ in range(maximum + 1)]
# array에 있는 수를 인덱스삼아 카운팅해줌.
for num in array:
countArray[num] += 1
sortedArray = []
# 카운팅 배열을 모두 돌면서
for i in range(maximum + 1):
# 그 안에 저장된 수만큼 sortedArray에 저장함.
for j in range(countArray[i]):
sortedArray.append(i)
print("카운팅 배열 :", countArray)
print("정렬된 배열 :", sortedArray)
원소의 개수가 총 N개이고, 그 원소 중 최댓값이 K라고 하자.
계수정렬은 카운팅 해주는 부분인 아래 코드에서는 시간복잡도가 O(N)이다. array의 N개의 원소 당 한 번씩 연산을 하기 때문이다.
for num in array:
countArray[num] += 1그리고, 코드의 그 아래 부분인 카운팅 배열을 이용해 정렬하는 부분을 보면 첫 번째 포문은 위와 같은 이유로 O(K)이다. 그 아래 for문으로 인해서는 모두 합쳐서 시행되는 총 횟수가 N번 이다. 어쨌든 N개의 원소를 sortedArray에 저장하는 것이기 때문이다.
따라서 이 이중 for문의 시간복잡도는 O(N + K)이다.
공간복잡도도 마찬가지로 크기가 N인 배열과 K인 배열 두 개가 있으므로 O(N + K)이다.
sortedArray = []
# 카운팅 배열을 모두 돌면서
for i in range(maximum + 1):
# 그 안에 저장된 수만큼 sortedArray에 저장함.
for j in range(countArray[i]):
sortedArray.append(i)
print("카운팅 배열 :", countArray)
print("정렬된 배열 :", sortedArray)카운팅 배열을 만들어야 하고 접근할 수 있어야 하기 때문에, 모든 원소가 0 이상일 때만 가능하다. 또한 수가 너무 크면 공간복잡도가 매우 커지는 위험도 있다. 최대값이 99만 9999라고 한다면 배열의 크기는 100만이 되고 4(정수) * 100만 byte = 4Mb이다. 정렬 한 번 하는데 4Mb나 사용하는 것이다. 따라서 원소의 크기가 너무 크지 않을 때 효율적이다.
원소가 0과 10만 두 개라고 가정하자. 다른 정렬 방식이라면 한 번만 비교해줘도 되는 것을 계수정렬은 크기가 10만인 배열을 만들고 하나하나 접근해보아야 한다. 따라서 너무 차이가 큰 수가 있을 때는 비효율적이고 같은 수가 많을 때 효율적이다.
조건이 너무너무 많지만 그만큼 훨씬 빠르기 때문에 사용되는 정렬인 것 같다.
'공부 > 이것이 코딩테스트다' 카테고리의 다른 글
| 이진 탐색 - 떡볶이 떡 만들기 (0) | 2023.02.14 |
|---|---|
| 이진 탐색 이론 (0) | 2023.02.13 |
| BFS - 미로 탈출 (0) | 2023.01.19 |
| DFS - 음료수 얼려 먹기 (0) | 2023.01.18 |
| BFS 이론 (0) | 2023.01.18 |
