정렬(Sorting)
데이터를 특정한 기준에 따라서 순서대로 나열하는 것
선택 정렬(Selection Sort)
가장 작은 데이터를 선택 -> 맨 앞에 있는 데이터와 교환 -> 그 다음 작은 데이터를 선택 -> 앞에서 두 번째 데이터와 교환
예시)
가장 작은 데이터인 '0'와 맨 앞 데이터인 '7'을 교환한다.
그 다음 작은 데이터인 '1'과 두 번째 데이터인 '5'를 교환한다.
위의 과정을 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'가 어떤 위치로 들어갈지 판단한다.
'7'의 왼쪽 또는 오른쪽 중에서 결정하는데 왼쪽에 삽입한다.
(본 위치에서 왼쪽으로 차례차례 확인하는 것)
다음 '9'가 어느 위치에 들어갈지 판단한다. 들어갈 수 있는 위치는 총 3가지이다.
'5'의 왼쪽, 오른쪽, 그리고 '7'의 오른쪽이다.
적절한 위치는 '7'의 오른쪽이므로 그대로 둔다.
'0'은 총 4가지의 위치 중 '5'의 왼쪽에 해당하므로 해당 위치에 삽입한다.
'3'은 '0'과 '5'사이에 삽입한다.
위의 과정을 N-1번 반복하면 다음과 같이 정렬이 완료된다.
삽입 정렬의 특징으로는 정렬이 이루어진 원소는 항상 오름차순이다.(내림차순으로 정렬했다면 내림차순!)
예시의 파란색 숫자를 보면 이해하기 편하다.
따라서 삽입 위치를 선정할 때, 삽입될 데이터보다 작은 데이터를 만나면, 그 위치에 멈추면 된다.
삽입 정렬 소스코드)
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)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 정렬
가장 많이 사용하는 정렬!
예시)
처음 pivot을 설정할 땐 맨 처음 데이터로 설정한다.
2번째 데이터부터 차례로 오른쪽으로 가면서 pivot보다 작은 수를 찾는다.
맨 끝 데이터부터 차례로 왼쪽으로 가면서 pivot보다 큰 수를 찾는다.
찾은 후에는 데이터를 교환한다.
이를 pivot보다 작은 수와 pivot보다 큰 수의 위치가 엇갈릴 때까지 반복한다.
엇갈릴 때 pivot과 pivot보다 작은 수를 교환한다!
즉, 위의 예시에서는 1과 5를 교환한다.
그렇다면 pivot인 5를 기준으로 왼쪽은 pivot보다 작은 수, 오른쪽은 pivot보다 큰 수로 구성된다.
이 상태에서, 왼쪽과 오른쪽을 각각 또 정렬한다!
이 과정을 반복하면 전체 정렬이 완료된다.
위의 예시에 해당하는 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)
계수 정렬은 데이터의 크기가 한정되어 있고, 데이터의 크기가 많이 중복되어 있을수록 적합하다!
