정렬(Sorting)
데이터를 특정한 기준에 따라서 순서대로 나열하는 것
선택 정렬(Selection Sort)
가장 작은 데이터를 선택 -> 맨 앞에 있는 데이터와 교환 -> 그 다음 작은 데이터를 선택 -> 앞에서 두 번째 데이터와 교환
예시)
| 7 | 5 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
가장 작은 데이터인 '0'와 맨 앞 데이터인 '7'을 교환한다.
| 0 | 5 | 9 | 7 | 3 | 1 | 6 | 2 | 4 | 8 |
그 다음 작은 데이터인 '1'과 두 번째 데이터인 '5'를 교환한다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 8 |
위의 과정을 9번 반복하면 다음과 같이 정렬이 완료된다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
선택 정렬은 데이터 교환 과정을 N-1번 반복하면 완료된다.
선택 정렬 소스코드)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
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)시간 복잡도: O(N^2)으로 느린 편이다.
하지만 코테에서는 가장 작은 인덱스를 찾는 과정이 있으므로 위의 과정은 익숙해지는 것이 좋다.
삽입 정렬(Insertion Sort)
특정한 데이터를 적절한 위치에 삽입하는 정렬. 이때 삽입되기 이전, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다.
예시)
| 7 | 5 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
첫 번째 데이터인 '7'은 그 자체로 정렬되어 있다고 판단하고, 두 번째 데이터인 '5'가 어떤 위치로 들어갈지 판단한다.
'7'의 왼쪽 또는 오른쪽 중에서 결정하는데 왼쪽에 삽입한다.
(본 위치에서 왼쪽으로 차례차례 확인하는 것)
| 5 | 7 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
다음 '9'가 어느 위치에 들어갈지 판단한다. 들어갈 수 있는 위치는 총 3가지이다.
'5'의 왼쪽, 오른쪽, 그리고 '7'의 오른쪽이다.
적절한 위치는 '7'의 오른쪽이므로 그대로 둔다.
| 5 | 7 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
'0'은 총 4가지의 위치 중 '5'의 왼쪽에 해당하므로 해당 위치에 삽입한다.
| 0 | 5 | 7 | 9 | 3 | 1 | 6 | 2 | 4 | 8 |
'3'은 '0'과 '5'사이에 삽입한다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 8 |
위의 과정을 N-1번 반복하면 다음과 같이 정렬이 완료된다.
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
삽입 정렬의 특징으로는 정렬이 이루어진 원소는 항상 오름차순이다.(내림차순으로 정렬했다면 내림차순!)
예시의 파란색 숫자를 보면 이해하기 편하다.
따라서 삽입 위치를 선정할 때, 삽입될 데이터보다 작은 데이터를 만나면, 그 위치에 멈추면 된다.
삽입 정렬 소스코드)
array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
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)시간 복잡도: O(N^2)
단, 최선의 경우(현재 리스트의 데이터가 거의 정렬되어 있는 상태) 시간 복잡도: O(N)
퀵 정렬(Quick Sort)
기준 데이터(pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬
가장 많이 사용하는 정렬!
예시)
| 5 | 7 | 9 | 0 | 3 | 1 | 6 | 2 | 4 | 8 |
처음 pivot을 설정할 땐 맨 처음 데이터로 설정한다.
2번째 데이터부터 차례로 오른쪽으로 가면서 pivot보다 작은 수를 찾는다.
맨 끝 데이터부터 차례로 왼쪽으로 가면서 pivot보다 큰 수를 찾는다.
| 5 | 4 | 9 | 0 | 3 | 1 | 6 | 2 | 7 | 8 |
찾은 후에는 데이터를 교환한다.
이를 pivot보다 작은 수와 pivot보다 큰 수의 위치가 엇갈릴 때까지 반복한다.
| 5 | 4 | 2 | 0 | 3 | 1 | 6 | 9 | 7 | 8 |
엇갈릴 때 pivot과 pivot보다 작은 수를 교환한다!
즉, 위의 예시에서는 1과 5를 교환한다.
| 1 | 4 | 2 | 0 | 3 | 5 | 6 | 9 | 7 | 8 |
그렇다면 pivot인 5를 기준으로 왼쪽은 pivot보다 작은 수, 오른쪽은 pivot보다 큰 수로 구성된다.
이 상태에서, 왼쪽과 오른쪽을 각각 또 정렬한다!
이 과정을 반복하면 전체 정렬이 완료된다.
| 0 | 1 | 2 | 4 | 3 | 5 | 6 | 9 | 7 | 8 |
| 0 | 1 | 2 | 4 | 3 | 5 | 6 | 8 | 7 | 9 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
위의 예시에 해당하는 quick sort를 실행한 결과를 보여준 것이다.
각 과정에서 pivot을 표시했다.
퀵 정렬 소스코드)
array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end: # 원소가 1개인 경우 종료
return
pivot = start # pivot은 첫 번째 원소
left = start + 1
right = end
while left <= right:
# pivot보다 큰 데이터 찾을때까지 반복
while left <= end and array[left] <= array[pivot]:
left += 1
# pivot보다 작은 데이터 찾을때까지 반복
while right >= start and array[right] >= array[pivot]:
right -= 1
if left > right: # 엇갈린다면 작은 데이터와 pivot 교체
array[right], array[pivot] = array[pivot], array[right]
else:
array[left], array[right] = array[right], array[left]
# 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quick_sort(array, start, right - 1)
quick_sort(array, right+1, end)
quick_sort(array, 0, len(array) - 1)
print(array)
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
시간 복잡도:
평균 시간 복잡도: O(NlogN)
최악 시간 복잡도: O(N^2) => 데이터가 이미 정렬되어 있을 경우!
계수 정렬(Count Sort)
특정한 조건이 부합할 때만 사용할 수 있는 알고리즘. 매우 빠르다!
최악의 경우에도 O(N + K)를 보장한다.(K: 데이터 중 최댓값)
하지만, 데이터의 크기 범위가 제한되어 정수 형태로 표현 가능할 경우에만 사용할 수 있다.
일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 사용 가능하다.
위에 해당하는 이유는 모든 범위를 담을 수 있는 크기의 배열을 선언해야 하기 때문이다.
방법:
가장 큰 데이터와 가장 작은 데이터의 범위가 모두 담긴 하나의 리스트 생성 -> 리스트의 모든 데이터를 0으로 초기화 -> 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증가
예시)
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
데이터 7에 해당하는 인덱스의 값을 1 늘려준다.
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
데이터 5에 해당하는 인덱스의 값을 1 늘려준다.
이를 반복하면 다음과 같다.
7 5 9 0 3 1 6 2 9 1 4 8 0 5 2
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 2 | 2 | 2 | 1 | 1 | 2 | 1 | 1 | 1 | 2 |
결과적으로 리스트에는 각 데이터가 몇 번 등장했는지 횟수가 기록된다.
이것 자체가 정렬된 형태라고 볼 수 있다!
출력만 하면 완료됨!!
계수 정렬 소스코드)
# 모든 원소의 값이 0보다 크거나 같다고 가정
array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
# 모든 범위를 포함하는 리스트 선언(모든 값 0으로 초기화)
count = [0] * (max(array) + 1)
for i in range(len(array)):
count[array[i]] += 1 # 각 데이터에 해당하는 인덱스의 값 증가
for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인
for j in range(count[i]):
print(i, end = ' ')
# 0 0 1 1 2 2 3 4 5 5 6 7 8 9 9
시간 복잡도: O(N + K)
공간 복잡도: O(N + K)
계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 적합하다!