자료구조
정렬 Sorting 정리
yolang
2024. 5. 29. 18:16
728x90
배웠으나 까먹고 또 배웠으나 헷갈리는 그래서 정리해 둬야겠다.
이미 배웠던 분들이 복기하는 용도로 사용하면 좋을 것 같다.
시간 복잡도 ⍬(n2 )
[정렬되지 않은 리스트의 크기를 n부터 시작해 하나씩 줄임]
Selection sort( 선택 정렬 ) : 제일 큰(작은) 수를 찾아서 제일 뒤(앞)로 보내기
코드보기
def selectionSort(A):
for i in range(0, len(A)-1):
min_num = i
for j in range(i + 1, len(A)):
if A[j] < A[min_num]:
min_num = j
A[i], A[min_num] = A[min_num], A[i]
print(A)
selectionSort([7, 0, 3, 5, 4, 10, 8, 9, 2, 1])
# [0, 7, 3, 5, 4, 10, 8, 9, 2, 1]
# [0, 1, 3, 5, 4, 10, 8, 9, 2, 7]
# [0, 1, 2, 5, 4, 10, 8, 9, 3, 7]
# [0, 1, 2, 3, 4, 10, 8, 9, 5, 7]
# [0, 1, 2, 3, 4, 10, 8, 9, 5, 7]
# [0, 1, 2, 3, 4, 5, 8, 9, 10, 7]
# [0, 1, 2, 3, 4, 5, 7, 9, 10, 8]
# [0, 1, 2, 3, 4, 5, 7, 8, 10, 9]
# [0, 1, 2, 3, 4, 5, 7, 8, 9, 10]Bubble sort( 버블 정렬 ) : 2개씩 비교해 가면서 큰 수가 점점 뒤로 가게 하기
코드보기
def bubbleSort(A):
for i in range(len(A), 0, -1):
for j in range(i - 1):
if A[j] > A[j + 1]:
A[j], A[j + 1] = A[j + 1], A[j]
print(A)
bubbleSort([7, 0, 3, 5, 4, 10, 8, 9, 2, 1])
# [0, 7, 3, 5, 4, 10, 8, 9, 2, 1]
# [0, 3, 7, 5, 4, 10, 8, 9, 2, 1]
# [0, 3, 5, 7, 4, 10, 8, 9, 2, 1]
# [0, 3, 5, 4, 7, 10, 8, 9, 2, 1]
# [0, 3, 5, 4, 7, 8, 10, 9, 2, 1]
# [0, 3, 5, 4, 7, 8, 9, 10, 2, 1]
# [0, 3, 5, 4, 7, 8, 9, 2, 10, 1]
# [0, 3, 5, 4, 7, 8, 9, 2, 1, 10]
# [0, 3, 4, 5, 7, 8, 9, 2, 1, 10]
# [0, 3, 4, 5, 7, 8, 2, 9, 1, 10]
# [0, 3, 4, 5, 7, 8, 2, 1, 9, 10]
# [0, 3, 4, 5, 7, 2, 8, 1, 9, 10]
# [0, 3, 4, 5, 7, 2, 1, 8, 9, 10]
# [0, 3, 4, 5, 2, 7, 1, 8, 9, 10]
# [0, 3, 4, 5, 2, 1, 7, 8, 9, 10]
# [0, 3, 4, 2, 5, 1, 7, 8, 9, 10]
# [0, 3, 4, 2, 1, 5, 7, 8, 9, 10]
# [0, 3, 2, 4, 1, 5, 7, 8, 9, 10]
# [0, 3, 2, 1, 4, 5, 7, 8, 9, 10]
# [0, 2, 3, 1, 4, 5, 7, 8, 9, 10]
# [0, 2, 1, 3, 4, 5, 7, 8, 9, 10]
# [0, 1, 2, 3, 4, 5, 7, 8, 9, 10]
[정렬된 리스트의 수를 하나씩 늘림]
Insertion sort( 삽입 정렬 ) : 원소를 정렬된 리스트 안에 넣는 행동을 반복 → 거의 정렬된 리스트가 주어지면 특히 빠름
코드보기
def insertionSort(A):
for i in range(0, len(A)):
key = A[i]
j = i - 1
while j >= 0 and A[j] > key:
A[j + 1] = A[j]
j -= 1
A[j + 1] = key
print(A)
insertionSort([7, 0, 3, 5, 4, 10, 8, 9, 2, 1])
# [7, 0, 3, 5, 4, 10, 8, 9, 2, 1]
# [0, 7, 3, 5, 4, 10, 8, 9, 2, 1] 0 자리 찾아주기
# [0, 3, 7, 5, 4, 10, 8, 9, 2, 1] 3 자리 찾아주기
# [0, 3, 5, 7, 4, 10, 8, 9, 2, 1] 5 자리 찾아주기
# [0, 3, 4, 5, 7, 10, 8, 9, 2, 1]
# [0, 3, 4, 5, 7, 10, 8, 9, 2, 1]
# [0, 3, 4, 5, 7, 8, 10, 9, 2, 1]
# [0, 3, 4, 5, 7, 8, 9, 10, 2, 1]
# [0, 2, 3, 4, 5, 7, 8, 9, 10, 1]
# [0, 1, 2, 3, 4, 5, 7, 8, 9, 10]
시간 복잡도 ⍬(n logn)
Merge sort( 병합 정렬 ) : 원래 크기를 반으로 자르고 크기를 비교해 병합 (작은 문제로 만들고 해결)
코드보기
def mergeSort(A, l, r):
if l >= r:
return
if l < r:
q = (l + r) // 2
print("mergeSort", A[l:q+1],A[q+1:r+1])
mergeSort(A, l, q)
mergeSort(A, q + 1, r)
merge(A, l, q, r)
def merge(A, l, q, r):
i = l
j = q + 1
t = 0
tmp = [0 for i in range(r - l + 1)]
print("merge")
while i <= q and j <= r:
if A[i] <= A[j]:
tmp[t] = A[i]
t += 1
i += 1
else:
tmp[t] = A[j]
t += 1
j += 1
print(tmp)
# 남은 부분이 있다면 이어 붙이기
while i <= q:
tmp[t] = A[i]
t += 1
i += 1
print(tmp)
while j <= r:
tmp[t] = A[j]
t += 1
j += 1
print(tmp)
# tmp 다시 A로 옮기기
i = l
t = 0
while i <= r:
A[i] = tmp[t]
t += 1
i += 1
print('\n')
mergeSort([7, 0, 3, 5, 4, 10, 8, 9, 2, 1], 0, 9)
mergeSort [7, 0, 3, 5, 4] [10, 8, 9, 2, 1]
# mergeSort [7, 0, 3] [5, 4]
# mergeSort [7, 0] [3]
# mergeSort [7] [0]
# merge
# [0, 0]
# [0, 7]
# [0, 7]
#
#
# merge
# [0, 0, 0]
# [0, 3, 0]
# [0, 3, 7]
# [0, 3, 7]
#
#
# mergeSort [5] [4]
# merge
# [4, 0]
# [4, 5]
# [4, 5]
#
#
# merge
# [0, 0, 0, 0, 0]
# [0, 3, 0, 0, 0]
# [0, 3, 4, 0, 0]
# [0, 3, 4, 5, 0]
# [0, 3, 4, 5, 7]
# [0, 3, 4, 5, 7]
#
#
# mergeSort [10, 8, 9] [2, 1]
# mergeSort [10, 8] [9]
# mergeSort [10] [8]
# merge
# [8, 0]
# [8, 10]
# [8, 10]
#
#
# merge
# [8, 0, 0]
# [8, 9, 0]
# [8, 9, 10]
# [8, 9, 10]
#
#
# mergeSort [2] [1]
# merge
# [1, 0]
# [1, 2]
# [1, 2]
#
#
# merge
# [1, 0, 0, 0, 0]
# [1, 2, 0, 0, 0]
# [1, 2, 8, 9, 10]
# [1, 2, 8, 9, 10]
#
#
# merge
# [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 1, 0, 0, 0, 0, 0, 0, 0, 0]
# [0, 1, 2, 0, 0, 0, 0, 0, 0, 0]
# [0, 1, 2, 3, 0, 0, 0, 0, 0, 0]
# [0, 1, 2, 3, 4, 0, 0, 0, 0, 0]
# [0, 1, 2, 3, 4, 5, 0, 0, 0, 0]
# [0, 1, 2, 3, 4, 5, 7, 0, 0, 0]
# [0, 1, 2, 3, 4, 5, 7, 0, 0, 0]
# [0, 1, 2, 3, 4, 5, 7, 8, 9, 10]
Quick sort( 퀵 정렬 ) : 기준을 잡고 그것보다 크면 오른쪽, 아니면 왼쪽 (해결해가면서 작은 문제로 만듬)
코드보기
def quickSort(A, p, r):
if p < r:
q = partition(A, p, r)
quickSort(A, p, q - 1)
quickSort(A, q + 1, r)
def partition(A, p, r):
x = A[r]
i = p - 1
for j in range(p, r):
# pivot보다 작을 경우 i와 j 같이 증가하다가 더 커지는 경우 j 만 증가함
if A[j] < x:
i += 1
A[i], A[j] = A[j], A[i]
# 피봇 자리 배치
A[i + 1], A[r] = A[r], A[i + 1]
print("pivot:",x, A[p:r])
return i + 1
A = [0, 7, 3, 5, 4, 10, 8, 9, 2, 1]
quickSort(A, 0, 9)
print(A)
# pivot: 1 [0, 1, 3, 5, 4, 10, 8, 9, 2]
# pivot: 7 [3, 5, 4, 2, 7, 9, 10]
# pivot: 2 [2, 5, 4]
# pivot: 3 [3, 4]
# pivot: 5 [4]
# pivot: 8 [8, 10]
# pivot: 9 [9]
# [0, 1, 2, 3, 4, 5, 7, 8, 9, 10]
- 최악의 상황 : 제일 크거나 작은 값을 기준으로 잡아 분류가 일어나지 않으면? → 무작위로 3개 잡아서 중간값 사용
Heap sort( 힙 정렬 ) : heap 을 이용한 정렬, heap 을 build 한 후 위의 값을 pop 하면서 정렬
- Heap의 build O(n)으로 하는 거 알고 계시나요? - leaf node가 n/2개 라 아래에서 부터하는 게 효율적임!
코드보기
import heapq
def heapSort(A):
tmp = [x for x in A]
heap_tmp = []
for i in tmp:
heapq.heappush(heap_tmp, -i)
for i in range(len(tmp)-1, -1, -1):
A[i] = -heapq.heappop(heap_tmp)
A = [0, 7, 3, 5, 4, 10, 8, 9, 2, 1]
heapSort(A)
print(A)
Shell sort( 쉘 정렬 ) : insertion sort를 더 효율적으로 하는 방법! gap 을 이용해 뭉텅이로 정렬해놔서 마지막 insertion sort 할 때 효율을 높임
시뮬레이션 : https://www.w3resource.com/ODSA/AV/Sorting/shellsortAV.html
특수 정렬 ⍬(n)
Counting sort( 계수 정렬 ): -O(n)~+O(n) 범위에 있는 정수일 경우에만 성립, 각 원소가 몇번 등장하는 지 Count 해 배열의 자리를 계산한 후 채워 나가는 방법 [영상자료 : https://www.youtube.com/watch?v=7zuGmKfUt7s]
Radix sort( 기수 정렬 ) : 모두 K 개 이하의 자릿수를 가진 자연수와 같은 경우에만 성립, 자릿수대로 정렬해 나가는 방법
Bucket sort( 버킷 정렬 ) : 원소들이 균등 분포일 때 사용가능, 0~1 사이의 값을 가진 데이터 배열일때 배열의 크기만큼 곱한 후, 각 버킷에 담기, 버킷별로 정렬 한 후 합친다 [영상자료 : https://www.youtube.com/watch?v=VuXbEb5ywrU]
["쉽게 배우는 자료구조 with 파이썬 - 문병로" 를 참고하여 작성하셨습니다.]
728x90