버블정렬
아이디어
인접한 원소들끼리 교환 * N-1번 반복 (N: 배열의 길이)
한번 반복할 때마다 한 자리씩 확정되는 정렬이기 때문에,
교환해야하는 원소 수가 하나씩 줄어들고 (j)
N-1개의 원소를 정렬하면 (i) 나머지 한자리는 자동으로 정렬된다.
구현
def bubble_sort(arr):
for i in range(len(arr)-1): # 반복 횟수
for j in range(len(arr)-1): # 교환하는 원소 수
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]선택정렬
아이디어
원소 하나씩 선택 (N-1번) * 최소값을 찾아서 교환
매번 교환할 필요 없이 인덱스만 넘겨주고, 최소원소의 인덱스를 구한 후 한번만 직접 교환하면 된다.
버블 정렬과 마찬가지로 한번 반복할 때마다 한 자리씩 확정되는 정렬이다.
구현
def selection_sort(arr):
for i in range(len(arr)-1):
min_idx=i
for j in range(i+1,len(arr)):
if arr[i] > arr[j]:
min_idx=i
arr[min_idx],arr[i]=arr[i],arr[min_idx]삽입정렬
아이디어
2번째 원소부터 앞 원소들과 비교하며 자기 자리를 찾아가는 정렬
앞 원소들 중 더 작은 값 발견시 그 자리 바로 뒤에 삽입.
그 자리를 포함한 이후 원소들은 뒤로 한칸씩 밀려나고,
제자리를 찾은 원소는 원래 위치에서 삭제.
구현
def insertion_sort(arr):
for i in range(1,len(arr)):
j=i-1
while (j>=0 and arr[i]<arr[j]):
j-=1
arr.insert((j+1),arr[i])
del arr[i+1](따라서, 삽입 삭제를 안하고 원소를 한칸씩 뒤로 밀어넣다가
더 작은 값이 나오면 밀지 않고 빈자리에 쏙 넣어도 된다)
def insertion_sort(arr):
for i in range(1, len(arr)):
elem = arr[i]
j = i
while j > 0 and arr[j - 1] > elem:
arr[j] = arr[j - 1]
j -= 1
arr[j] = elem병합정렬
아이디어
정렬된 배열을 만드는 방법은, 두 개의 정렬된 배열을 합쳐 하나의 정렬된 배열을 만드는 것이다.
(그럼 그 두개의 정렬된 배열은?)
원소 2개 이상을 가지는 배열을 쪼개다 보면 원소 1개의 배열이 나온다.
원소 1개 배열 2개를 병합 -> 원소 2개의 정렬된 배열
2개 + 1개 or 2개+2개 병합 -> 원소 3개 or 4개의 정렬된 배열
-> 확장
- 어떻게 쪼갤 것인가
- 어떻게 합칠 것인가
두가지 아이디어가 필요하다.
구현
def merge_sort(arr):
#둘로 쪼개고 하나로 합쳐라
def sort(low, high):
if high - low < 2:
return
mid = (low + high) // 2
sort(low, mid)
sort(mid, high)
merge(low, mid, high)
def merge(low, mid, high):
temp = []
l, h = low, mid
# low/high가 둘다 남아있을 때
while l < mid and h < high:
if arr[l] < arr[h]:
temp.append(arr[l])
l += 1
else:
temp.append(arr[h])
h += 1
# low 또는 high만 남아있을 때
while l < mid:
temp.append(arr[l])
l += 1
while h < high:
temp.append(arr[h])
h += 1
for i in range(low, high):
arr[i] = temp[i - low]
return sort(0, len(arr))퀵소트(퀵정렬)
아이디어
원소 하나를 선택(PIVOT)하여 작은 원소들은 왼쪽으로, 큰 원소들은 오른쪽으로 위치하게 교환
(그러면 이제 그 두 그룹을 다시...)
한번 정렬할 때마다 PIVOT으로 선택한 원소의 위치가 정해진다.
PIVOT 값에 따라 두 구간으로 나뉘기 때문에 중간값에 가까울 수록 이상적인 정렬이 된다.
- 어떻게 PIVOT을 선택할 것인가
- 어떻게 큰값/작은값 으로 분리할 것인가
두가지 아이디어가 필요하다.
구현
def quick_sort(arr):
def sort(low, high):
if high <= low:
return
mid = partition(low, high)
sort(low, mid - 1)
sort(mid, high)
def partition(low, high):
pivot = arr[(low + high) // 2]
while low <= high:
while arr[low] < pivot:
low += 1
while arr[high] > pivot:
high -= 1
if low <= high:
arr[low], arr[high] = arr[high], arr[low]
low, high = low + 1, high - 1
return low
return sort(0, len(arr) - 1)참고
https://www.daleseo.com/sort-quick/
https://www.daleseo.com/sort-merge/
