[TIL] Python으로 sort 구현 (파이썬 정렬 알고리즘 정리)

안녕하세요 ~ !

오늘은 각종 정렬 기법들을 공부할 겸 파이썬으로 구현한 것을 정리할려고 합니다.

정렬 기법에는 버블 정렬, 퀵 정렬,  삽입 정렬,  머지 정렬,기수 정렬, 힙 정렬이 있습니다. (쉘 정렬도 있습니다. )

1. 거품 정렬 (bubble sort)

버블 정렬은 굉장히 단순하지만 O(N^2)의 상대적으로 느린 시간 복잡도를 가지고 있습니다.

인접한 두 원소를 비교하여 스왑하는 것을 반복하여 정렬합니다.

<코드>

def bubbleSort(x):

for i in range(len(x)-1):

for j in range(len(x) - i):

if x[j] > x[j+1]:

x[j], x[j+1] = x[j+1], x[j] # swap

return x

이중 for 문을 통해 인접한 두 원소를 비교한 후, 왼쪽이 더 큰 값을 갖는다면 스왑을 해주어 정렬해줍니다.

최악의 경우 O(N^2)의 시간 복잡도를 가집니다.

2. 퀵 정렬 (quick sort)

퀵 정렬은 현재 사용되고 있는 정렬 알고리즘 중 가장 빠르다고 알려져 있습니다. 퀵 정렬은 빠른 것 뿐만 아니라 구현하기도 용이하고 메모리 사용량도 적어 정렬 알고리즘을 사용하면 보통 퀵 정렬 알고리즘을 사용한다고 보시면 됩니다.

동작 방식

퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬합니다.

전체에서  기준(pivot)이 되는 원소를 하나 정합니다.

이 기준을 중심으로 기준 왼쪽으로는 기준 보다 작은 값이 오게 정렬하고, 기준 오른쪽으로는 값이 큰 원소들이 오게 배치합니다.

기준을 중심으로 나누어진 왼쪽, 오른쪽 집단에서 각각 다시 기준이 되는 원소를 정해 위 과정을 반복해줍니다.

<코드>

def quickSort(x):

if len(x) <= 1:

return x

pivot = x[len(x)//2]

left,right,equal =[],[],[]

for a in x:

if a < pivot:

left.append(a)

elif a > pivot:

more.append(a)

else:

equal.append(a)

return quickSort(left) + equal + quicksort(right)

분할 정복은 재귀적으로 수행되기 때문에 퀵 정렬 구현 역시 재귀를 이용해 주었습니다.

pivtot을 하나 정해 pivot 보다 작은 값은 left 리스트에, 큰 값은 right 리스트에 넣어주고 만약 pivot과 같은 값이 있다면 equal 리스트에 넣어줍니다. 다시 재귀적으로 이 과정을 반복하여 원소가 하나 남을 때까지 반복해 줍니다.

퀵 정렬은 일반적으로 O(NlogN)의 시간 복잡도를 가지지만 최악의 경우, pivot 선택을 최악으로 했을 경우 O(N^2)의 시간 복잡도를 가집니다.

3. 삽입 정렬 (insertion sort)

삽입 정렬은 배열의 각각의 원소들을 앞에서부터 차례대로 이미 정렬된 부분 배열과 비교하여 자신보다 큰 값과 작은 값 사이에 적당한 위치를 찾아 삽입하여 정렬하는 알고리즘입니다. 

<코드>

def insertionSort(x):

for i in range(1,len(x)):

j, key = i -1, x[i]

while x[j] > key and j >= 0:

x[j+1] = x[j]

j = j - 1

x[j+1] = key

return x

삽입 정렬의 시간복잡도는 O(N^2) 입니다.

4. 병합(합병) 정렬 (merge sort)

그 유명한 폰 노이만이 1945년에 개발한 알고리즘입니다. O(NlogN)의 빠른 시간 복잡도를 가지는 비교 기반 정렬 알고리즘입니다.

병합 정렬의 알고리즘 순서는 다음과 같습니다.

리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 보고 그렇지 않으면 리스트를 절반으로 나눠 두 리스트로 분할합니다. 각 부분 리스트를 재귀적으로 다시 위의 과정을 반복하여 정렬하고 정렬된 두 부분 리스트를 합쳐 다시 정렬된 리스트로 합병하게 됩니다.

<코드>

def mergetSort(x):

if len(x) <= 1:

return x

left = mergetSort(x[:len(x)//2])

right = mergetSort(x[len(x)//2: ])

i,j,k = 0,0,0

while i<len(left) and j<len(right):

if left[i] < right[j]:

x[k] = left[i]

i += 1

else:

x[k] = right[j]

j += 1

k += 1

if i == len(left):

while j < len(right):

x[k] = right[j]

j += 1

k += 1

elif j == len(right):

while i < len(left):

x[k] = left[i]

i += 1

k += 1

return x

5. 기수 정렬 (radix sort)

기수 정렬은 낮은 자리수부터 비교하여 정렬해 가는 정렬 알고리즘입니다.

예를 들어 3자리이하수 (1 ~999)라면 먼저 1의 자리수를 기준으로 정렬하고 다음 10의 자리수를 기준으로 정렬,  그리고 100의 자리에 대해 정렬하는 알고리즘이 기수 정렬 알고리즘입니다.

6. 힙 정렬 (heap sort)

힙 정렬은 최대 힙, 최소 힙 트리를 구성하여 정렬을 하는 방법입니다. 내림차순 정렬을 하려면 최대 힙을 사용하고 오름차순 정렬을 하려면 최소 힙을 알아야합니다. 

힙 정렬은 우선 n 개의 노드에 대해서 완전 이진 트리를 구성해야 합니다. 그 다음 최대 힙을 만들어야 합니다. 최대 힙은 부모노드에 값이 자식 노드에 값보다 큰 트리를 말합니다. 단말 노드(자식이 없는 노드)를 자식 노드로 가지고 있는 부모 노드부터 구성을 하면서 아래부터 루트까지 올라오며 순차적으로 만들어 갑니다. 가장 큰 수(루트)를 가장 작은 수와 교환 합니다. 이를 반복하여 최대 힙을 구성하게 됩니다.

이상으로 정렬 정리를 마치도록 하겠습니다 !!