선택정렬
- 한 사이클당 가장 작은 값을 찾아 첫 번째 자리와 바꾸고 그 다음 작은 값을 찾아 두 번째 자리와 바꾸고 이를 반복한다.
- 시간 복잡도: O(n**2)
# 두 수를 바꾸는 함수
def swap(n1, n2):
temp = n1
n1 = n2
n2 = temp
return n1, n2
lst = [1, 3, 5, 7, 4, 2, 6]
def select_sort(lst):
# 기준 위치 i
for i in range(len(lst)):
# i 뒤에 위치한 숫자들의 위치 j
for j in range(i, len(lst)):
# 기준 숫자가 그 뒤에 숫자들보다 크다면
if lst[i] > lst[j]:
# 스왑 함수 실행
lst[i], lst[j] = swap(lst[i], lst[j])
return lst삽입정렬
- key 값과 원소들을 비교하여 삽입할 위치를 지정하고 큰 값은 뒤로 보내서 지정한 위치에 삽입한다.
- 시간 복잡도: O(n**2)
lst = [1, 3, 5, 7, 4, 2, 6]
def insertion_sort(lst):
# 기준 위치 i
for i in range(1, len(lst)):
# i부터 0번째 위치까지 역순으로 진행
for j in range(i, 0, -1):
# i번째 숫자가 i-1번째 숫자보다 작다면
if lst[i-1] > lst[i]:
# swap
lst[i-1], lst[i] = lst[i], lst[i-1]
return lst버블정렬
- 인접한 두 개의 원소를 비교하여 작은 원소는 왼쪽으로, 큰 원소는 오른쪽으로 이동시킨다.
- 배열을 왼쪽부터 순서대로 검사하면서 작은 원소를 왼쪽으로 이동시킨다.
- 이를 반복한다.
- 시간 복잡도: O(n**2)
lst = [1, 3, 5, 7, 4, 2, 6]
def bubble_sort(lst):
# 기준 위치 i
for i in range(len(lst)):
for j in range(len(lst)-1-i):
# j번째가 j+1번째보다 크다면
if lst[j] > lst[j+1]:
# swap
lst[j], lst[j+1] = lst[j+1], lst[j]
return lst합병정렬
- 분할 정복을 기반으로 한 정렬 알고리즘이다.
- 배열을 크기가 1이 될 때까지 나누고 배열을 차례대로 크기에 따라 정렬하고 병합하는 과정을 반복한다.
lst = [1, 3, 5, 7, 4, 2, 6]
def merge_sort(lst):
# 더이상 분할을 진행할 수 없을 때
if len(lst) <= 1:
return lst
# 중앙값 설정
mid = len(lst) // 2
# 왼쪽 공간 설정
left = lst[:mid]
# 오른쪽 공간 설정
right = lst[mid:]
# 왼쪽 공간 정렬
left = merge_sort(left)
# 오른쪽 공간 정렬
right = merge_sort(right)
return merge(left, right)
def merge(left, right):
result = []
# 왼쪽 위치
i = 0
# 오른쪽 위치
j = 0
# left 안에 i가 있고, right 안에 j가 있는 동안 반복
while i < len(left) and j < len(right):
# 왼쪽 값이 오른쪽 값보다 작을 때
if left[i] < right[j]:
# 왼쪽값 추가
result.append(left[i])
# 오른쪽으로 한 칸 이동
i += 1
else:
# 오른쪽값 추가
result.append(right[j])
# 오른쪽으로 한 칸 이동
j += 1
# left 안에 i가 있는 동안
while i < len(left):
# 왼쪽값 추가
result.append(left[i])
# 오른쪽으로 한 칸 이동
i += 1
# right 안에 j가 있는 동안
while j < len(right):
# 오른쪽값 추가
result.append(right[j])
# 오른쪽으로 한 칸 이동
j += 1
return result퀵정렬
- 분할 정복을 기반으로 한 정렬 알고리즘이다.
- 리스트 중 하나의 원소를 pivot으로 택한다.
pivot을 기준으로 두 개로 나누고 pivot보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동시킨다. - 더 이상 나눌 수 없을 때까지 반복한다.
- 시간 복잡도: 평균 = O(n*log(n)), 최악 = O(n**2)
lst = [1, 3, 5, 7, 4, 2, 6]
def quick_sort(lst):
# 더이상 분할을 진행할 수 없을 때
if len(lst) <= 1:
return lst
# 기준값 설정
pivot = lst[len(lst)//2]
# 왼쪽 공간, 오른쪽 공간, 중앙 공간 생성
left = []
right = []
equal = []
# lst 안의 숫자를 꺼냄
for num in lst:
# 기준값보다 작다면
if num < pivot:
# 왼쪽 공간에 추가
left.append(num)
# 기준값보다 크다면
elif num > pivot:
# 오른쪽 공간에 추가
right.append(num)
# 기준값과 같다면
else:
# 중앙 공간에 추가
equal.append(num)
return quick_sort(left) + equal + quick_sort(right)Python에서 sort 함수는 어떤 알고리즘을 사용했을까?
Tim Sort 알고리즘
insertion sort와 merge sort을 결합하여 만든 정렬이다. 이 알고리즘의 최선의 시간 복잡도는 O(n), 평균 시간 복잡도는 O(n*log(n)), 최악의 경우의 시간 복잡도는 O(n*log(n))이다.
두 안정적인 정렬 알고리즘을 결합하였기에 안정적이며, 기존 merge sort에 비해 추가 메모리 사용이 적어서 다른 O(n*log(n)) 알고리즘의 단점을 극복했다.
insertion sort는 인접한 메모리와의 비교를 반복하기에 참조 지역성의 원리를 매우 잘 만족하고 있다. 작은 n에 대하여 정렬 속도가 빠르다. 이것을 이용하여 전체를 작은 덩어리로 잘라 insertion sort로 정렬한 뒤 병합한다.
.