정렬이란?
→ 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.
→ 프로그램에서 데이터를 가공할 때 정렬을 해서 사용하는 경우 많음. (이진탐색 가능)
선택 정렬(selection sort)
→ 가장 작은 데이터를 선태개 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복한다. '매번 가장 작은 것을 선택한다.'
# selection sort
a = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(a)):
min_i = i
for j in range(i, len(a)):
if a[j] <= a[min_i]:
min_i = j
a[i], a[min_i] = a[min_i], a[i]
print(a)파이썬의 swap
a, b = b, a다른 언어에 비해서 훨씬 간편하게 객체를 바꿀 수 있다.
선택 정렬의 시간 복잡도 - O(N^2)
삽입 정렬(Insertion Sort)
→ 데이터를 하나씩 확인하며, 각 데이터를 적절한 위치에 삽입한다.
# Insertion Sort
a = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(1, len(a)): # 뒤
for j in range(0, i): # 앞
if a[j] > a[i]:
a[j], a[i] = a[i], a[j]
print(a)시간 복잡도 - O(N^2) , best case - O(N)
이미 어느 정도 정렬되어 있다면 여타 정렬 알고리즘보다 삽입 정렬을 이용하는 것이 정답 확률을 높이는 것.
퀵 정렬
→ 지금까지 배운 정렬 알고리즘 중에 가장 많이 사용되는 알고리즘이다. 프로그래밍 언어에서의 정렬 모듈의 근간이되는 알고리즘이다.
- 퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 이해하기 어려움.
- 피벗이 사용된다. 큰 숫자와 작은 숫자를 교환할 때, 교환하기 위한 '기준'을 바로 피벗이라고 표현한다.
# 퀵 정렬
# 1
a = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array, start, end):
if start >= end:
return
pivot = start
left, right = start + 1, end
while left <= right:
while left <= end and array[left] <= array[pivot]:
left += 1
while right > start and array[right] >= array[pivot]:
right -= 1
if left > right:
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(a, 0, len(a)-1)
print(a)
#2
a = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
def quick_sort(array):
if len(array) < 1:
return array
pivot = array[0]
tail = array[1:]
left_side = [x for x in tail if x <= pivot]
right_side = [x for x in tail if x > pivot]
return quick_sort(left_side) + [pivot] + quick_sort(right_side)
print(quick_sort(a))계수 정렬
→ 알고리즘은 특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘이다.
- 데이터의 개수가 N, 데이터 중 최대값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(N+K)를 보장한다. 계수 정렬은 이처럼 매우 빠르게 동작할 뿐만 아니라 원리 또한 매우 간단하다. 다만, 계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다.
Grind