1. 선택 정렬 (Selection Sort)
for (last : n-1 --> 1) 내려가면서 반복
A[0~last] 중 가장 큰 수 A[k]를 찾는다.
A[k]와 A[last]를 교환한다.
# 선택 정렬(selectionSort)
def selectionSort(A):
for last in range(len(A)-1, 0, -1):
max = 0; index = -12345
for k in range(last+1):
if A[k] > max:
max = A[k]
index = k
A[index], A[last] = A[last], A[index]2. 버블 정렬 (Bubble Sort)
for (last : n-1 --> 1) 내려가면서 반복한다.
for (i : 0 --> last-1) 올라가면서 반복한다.
if (A[i] > A[i+1] )
A[i] <--> A[i+1]
# 버블 정렬(bubbleSort)
def bubbleSort(A):
for last in range(len(A)-1, 0, -1):
for k in range(last):
if A[k] > A[k+1]:
A[k], A[k+1] = A[k+1], A[k]
3. 삽입 정렬 (Insertion Sort)
for (i : 1 --> n-1) 올라가면서 반복
newItem = A[i]
j = i - 1
# 이 지점에서 A[0 ~ i-1]은 이미 정렬된 상태
while (0 <= j and newItem < A[j])
A[i] 값을 j+1 자리에 넣는다.
j 값을 1 줄인다.
j+1 자리에 newItem 값을 넣는다.
# j가 -1이 되는 경우는 newItem이 가장 작은 값인 경우
# newItem이 들어갈 자리를 만드려면 A[j] 값이 들어가는 자리가 오른쪽으로 한 칸씩 밀려야 한다.
# 삽입 정렬(insertionSort)
def insertionSort(A):
for i in range(1, len(A)):
newItem = A[i]
j = i - 1
# 이 지점에서 A[0~i-1]은 이미 정렬된 상태다
while 0 <= j and newItem < A[j]:
# 여기서 j가 음수가 될 수 있으므로, 0 <= j 조건이 있어야 한다(j는 인덱스 번호이다)
# j가 -1이 되는 경우는 newItem이 가장 작은 값인 경우이다 -> 이 경우 j+1(0)에 newItem을 넣으면 됨
A[j+1] = A[j]
j -= 1
A[j+1] = newItem4. 병합 정렬 (Merge Sort)
if p < r:
인자로 A, p, r을 받는 정렬의 경우 이 조건을 반드시 넣어 주어야 오류가 발생하지 않음
병합 알고리즘 (A, p, q, r)에서 A[p ~ q]와 A[q+1 ~ r]은 이미 정렬되어 있는 상태이다.
# 병합 정렬(mergeSort)
def mergeSort(A,p,r):
if p < r: # 인자로 A,p,r을 받는 정렬의 경우, 이 조건을 반드시 넣어 주어야 오류가 발생하지 않음!!
q = (p + r) // 2
mergeSort(A, p, q)
mergeSort(A, q+1, r)
merge(A, p, q, r)
def merge(A, p, q, r):
i = p; j = q+1; t = 0; temp = [0 for _ in range(len(A))]
while i <= q and j <= r:
if A[i] <= A[j]:
temp[t] = A[i]; i += 1; t += 1
else:
temp[t] = A[j]; j += 1; t += 1
while i <= q: # 왼쪽 부분만 남은 경우
temp[t] = A[i]; i += 1; t += 1
while j <= r: # 오른쪽 부분만 남은 경우
temp[t] = A[j]; j += 1; t += 1
i = p; t = 0
while i <= r:
A[i] = temp[t]; i += 1; t += 15. 퀵 정렬 (Quick Sort)
if p < r:
인자로 A, p, r을 받는 정렬의 경우 이 조건을 반드시 넣어 주어야 오류가 발생하지 않음
기준보다 작은 수는 왼쪽에 나머지는 오른쪽에 오도록 배치하고 각각을 독립적으로 정렬한다.
1구역 : 15보다 작은 원소들 (i는 1구역의 끝)
2구역 : 15보다 크거나 같은 원소들
3구역 : 아직 정해지지 않은 원소들 (j는 3구역의 시작)
4구역 : 15 자신
for 루프가 한 바퀴 돌 때마다 3구역이 한 칸씩 줄어든다. (j가 1 증가)
for 루프가 한 바퀴 돌 때마다 1구역 또는 2구역 중 하나가 한 칸 늘어난다.
1구역이 늘어날 때는 i와 j가 동시에 1 증가한다.
2구역이 늘어날 때는 j만 1 증가한다. for 루프가 한 바퀴 돌 때마다 자동으로 j는 1 증가하므로, 2구역을 늘리기 위해서는 아무 일도 할 필요가 없다.
j만 증가할 경우 : 2구역 (가만히 있으면 2구역에 추가됨)
i와 j 모두 증가할 경우 : 1구역 (i와 j의 자리를 바꾸어 주어야 함)
# 퀵 정렬 1(Quick Sort 1)
def quickSort(A, p, r): # 인자로 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):
if A[j] < x: # 1구역에 추가되어야 하는 경우, j는 3구역의 첫번째 원소를 가리키는 인덱스
i += 1
A[i], A[j] = A[j], A[i]
A[i+1], A[r] = A[r], A[i+1]
return i + 1
다른 방법 1
# 퀵 정렬 2(Quick Sort 2)
def quickSort(a, p, r):
if p < r:
left = p + 1
right = r
while (left <= right):
while left <= r and a[left] <= a[p]: left += 1
while right > p and a[p] <= a[right]: right -= 1
if (left > right): a[right], a[p] = a[p], a[right]
else: a[left], a[right] = a[right], a[left]
quickSort(a, p, right-1)
quickSort(a, right+1, r)
다른 방법 2
# 퀵 정렬 3(Quick Sort 3)
def quickSort(a):
if len(a) <= 1: return a
head = a[0]; tail = a[1:]
left = [x for x in tail if x <= head]
right = [x for x in tail if x > head]
return quickSort(left) + [head] + quickSort(right)6. 힙 정렬 (Heap Sort)
# 힙 정렬(heapSort)
def heapSort(A):
buildHeap(A)
for last in range(len(A)-1, 0, -1):
A[0], A[last] = A[last], A[0]
percolateDown(A, 0, last-1)
def percolateDown(A, i, end):
left = 2 * i + 1
right = 2 * i + 2
if left <= end:
child = left
if right <= end and A[left] < A[right]:
child = right
if A[i] < A[child]:
A[i], A[child] = A[child], A[i]
percolateDown(A, child, end)
def buildHeap(A):
for i in range((len(A)-2)//2, -1, -1):
percolateDown(A, i, len(A)-1)7. 셸 정렬 (Shell Sort)
셸 정렬은 마지막 삽입 정렬을 하기 전에 각 원소가 있어야 할 자리에서 멀리 떨어져 있을 가능성을 현저히 줄이는 작업을 통해 삽입 정렬의 효율성을 높인다.
갭 수열 H = {h0, h1, ..., 1}
for (h : h0, h1, ..., 1) h칸 떨어진 원소들 끼리 삽입 정렬
A[0, h, 2h, ... ]을 정렬
A[1, 1+h, 1+2h, ... ]을 정렬
...
A[h-1, 2h-1, ... ]을 정렬
# 간격을 h로 하는 삽입 정렬 알고리즘 !
# 셸 정렬(shellSort)
def shellSort(A):
H = gapSequence(A)
for h in H:
for k in range(h):
stepInsertionSort(A, k, h)
# for 루프를 마지막으로 수행할 때 stepInsertionSort(A,0,1)이 호출되는데, 이는 삽입정렬과 동일하다.
def gapSequence(A):
H = [1]; gap = 1
while gap < len(A) / 5:
gap = 3 * gap + 1
H.append(gap)
H.reverse()
return H
def stepInsertionSort(A, k, h): # A[k, k+h, k+2h ...]를 정렬
for i in range(k+h, len(A), h):
newItem = A[i]
j = i - h
while j >= 0 and A[j] > newItem:
A[j+h] = A[j]
j -= h
A[j+h] = newItem8. 계수 정렬 (Counting Sort)
# 계수 정렬(countingSort)
def countingSort(A):
k = max(A)
C = [0 for _ in range(k+1)] # C[0, 1, 2 ... k-1]; C[0]->0, C[1]->1 ... C[k]->k
B = [0 for _ in range(len(A))]
for i in range(len(A)): # A의 원소별 등장 횟수를 카운터에 기록
C[A[i]] += 1
for j in range(1, k+1): # C(카운터)를 수선
C[j] = C[j] + C[j-1]
for i in range(len(A)): # B를 채우기
B[C[A[i]]-1] = A[i]
C[A[i]] -= 1
return B9. 기수 정렬 (Radix Sort)
# 기수 정렬(radixSort)
def radixSort(A):
buckets = [[] for _ in range(10)]
k = max(A)
numberDigits = math.ceil(math.log10(k))
for i in range(numberDigits):
for x in A:
y = (x // 10**i) % 10
buckets[y].append(x)
A.clear()
for j in range(10):
A.extend(buckets[j])
buckets[j].clear()10. 버킷 정렬 (Bucket Sort)
정렬하고자 하는 원소들이 균등 분포할 때를 가정한 정렬 알고리즘
균등분포 : 데이터가 전 영역에 걸쳐 고루 존재하는 분포
A[0 ... 14] 각각에 15를 곱하여 정수부만 취함
* 균등 분포이기만 하면 [a, b] 사이의 값들을 [0, 1] 범위의 실수 값으로 매핑할 수 있기 때문에 정렬할 원소들이 반드시 [0, 1] 사이의 값일 필요는 없다.
# 버킷 정렬(bucketSort)
def bucketSort(A):
n = len(A)
buckets = [[] for _ in range(n)]
for i in range(n):
buckets[math.floor(n*A[i])].append(A[i])
A.clear()
for i in range(n):
insertionSort(buckets[i])
A.extend(buckets[i])