시간복잡도가 O(nlogn)인 정렬
해당 정렬들은 시간복잡도가 O(n^2)인 정렬보다 대체로 구현하기 어렵습니다. 해당하는 정렬들은 퀵 정렬, 병합 정렬, 힙 정렬이 있습니다.
시간복잡도가 O(n^2)인 정렬들은 이웃하는 원소들끼리만 비교를 진행하지만 오늘 다룰 배열들은 그렇지 않습니다.
바로 이 점 때문에 속도가 더 빠르지만 또한 구현하기가 더 어려운 것 같습니다.
👉 퀵 정렬
분할 정복을 이용한 정렬입니다.
배열 중 임의로 피벗을 하나 지정하고 해당 피벗을 기준으로 배열을 2개로 나누는 것을 반복해서 정렬하는 방법입니다.
분명한 반복적인 패턴이 있기 때문에 재귀를 이용해서 구현합니다.
def quick_sort(arr):
if not arr:
return arr
num=arr.pop() #임의로 하나의 피벗 지정. 해당 경우는 배열의 마지막 원소
left=[]
right=[]
for i in range(len(arr)): #반복문을 사용해서 피벗 기준으로 배열을 2개로 나눔
if arr[i]>num:
right.append(arr[i])
else:
left.append(arr[i])
return quick_sort(left)+[num]+quick_sort(right)
#재귀를 이용하여 정렬 완성⁙불안정 정렬입니다.
👉 병합 정렬
퀵 정렬과 마찬가지로 분할 정복을 이용합니다.
먼저 주어진 배열을 더 이상 나눌 수 없을 때까지 나눕니다.
그런 다음에 병합을 하기 시작하는데 병합을 할 때마다 정렬을 동반하며 진행합니다.
구글링을 하면 병합 정렬을 이미지나 gif로 표현해 놓은 것들이 있는데 그걸 참고하시면 좋을 것 같습니다.
def merge_sort(arr):
if len(arr)>1: #더 이상 나눌 수 없을 때까지 나눠주는 반복문
n=len(arr)//2
arr1,arr2=arr[:n],arr[n:]
merge_sort(arr1)
merge_sort(arr2)
i,j,k=0,0,0 #3개의 배열을 indexing하기 위한 변수들을 설정
#이 반복문에서 이해하면 좋을 점은 arr1과 arr2는
#이미 최소단위에서 병합될 때부터 정렬되어온 배열이라는 점입니다.
while j<len(arr1) and k<len(arr2):
if arr1[j]>arr2[k]:
arr[i]=arr2[k]
k+=1
else:
arr[i]=arr1[j]
j+=1
i+=1
arr[i:]=arr1[j:] if j!=len(arr1) else arr2[k:]
#반복문의 조건에 따라서 arr1과 arr2 둘 중 하나가 끝에 다다르면 종료되므로,
#남은 배열을 뒤에 붙여주는 과정입니다.
#여기서 남은 배열은 이미 정렬되어있는 배열이기 때문에
#이렇게 붙여주어도 정렬에는 문제가 없는 것입니다.
구글링을 해서 구현해놓은 코드들을 보며 정렬을 이해하는 식으로 공부하는데, 개인적으로 병합 정렬이 퀵 정렬보다 이해하기가 어려웠습니다. 코드에 달린 주석들을 참고하시면 좋을 것 같습니다.
⁙안정 정렬입니다.
👉 힙 정렬
힙 정렬을 이해하기 위해서는 자료구조 "힙"에 대한 이해가 선행되어야 합니다.
힙은 이진트리 자료 구조를 말하는데 최대 힙과 최소 힙이 있습니다. 쉽게 말하면 부모 노드와 자식 노드간의 대소관계가 지켜지는 이진 트리입니다. 이러한 힙은 1차원 배열로 구현이 가능합니다.
다른 포스트에서 힙에 대해 자세히 다뤄보고 힙 함수에 대해서도 알아보겠습니다.
힙 정렬은 일단 주어진 리스트를 최대 힙의 자료구조 형태로 만들고 정렬을 시작하는 것입니다.
힙의 자료구조에서 배열의 첫 번째에는 배열의 가장 큰 수가 오게 됩니다.
그 후에는 배열의 첫 번째 원소를 가장 뒤로 보내고, 배열의 가장 마지막 원소를 제외한 배열을 다시 최대 힙으로 만들어 주는 것입니다.
그럼 다시 가장 첫 번째 원소가 가장 큰 수가 되고, 뒤에서 두번째로 보내주면 차근차근 오름차순 정렬을 수행할 수 있습니다.
먼저 최대 힙을 만들어주는 heapify함수에 대한 이해가 필요합니다.
def heapsort(unsorted):
n=len(unsorted)
for i in range(n//2-1,-1,-1): #n//2-1이 의미하는 바는 힙의 자료구조에서 마지막으로 오는 원소의 부모 라인의 노드 index를 말합니다.
heapify(unsorted, i, len(arr))
#이제 최대 힙을 구성하였고 아래에서 정렬이 시작됩니다.
for i in range(n-1,0,-1):
unsorted[0], unsorted[i]=unsorted[i], unsorted[0] #가장 최대인 unsorted[0]을 배열의 가장 뒤로 보내줍니다.
heapify(unsorted, 0, i) #이후 맨 마지막 원소를 빼고 다시 최대 힙을 구성합니다.
def heapify(unsorted, index, heap_size): #최대 힙을 만들어주는 함수
largest=index #부모와 자식 노드의 index간에 성립하는 식입니다.
left=index*2+1
right=index*2+2
if left<heap_size and unsorted[left]>unsorted[largest]:
largest=left
if right<heap_size and unsorted[right]>unsorted[largest]:
largest=right
if largest!=index:
unsorted[index],unsorted[largest]=unsorted[largest],unsorted[index]
heapify(unsorted, largest, heap_size)
#재귀를 이용해서 구현해줍니다.
#하지만 이렇게 하면 힙의 자료구조에서 한 줄을 따라서만 대소관계를 비교해서 위치를 바꿔주기 때문에
#반복문을 사용하여 heapify함수를 이용해서 완전하게 최대 힙을 만들 수 있습니다.
import sys
arr=[]
for i in range(int(input())):
arr.append(int(sys.stdin.readline()))
#이렇게 반복해서 입력값을 받는 경우 sys.stdin.readline함수가 running time을 절약할 수 있습니다.
heapsort(arr)
for i in arr:
print(i)⁙힙 정렬은 어느 상황에서도 시간복잡도 O(nlogn)을 만족합니다, 불안정 정렬입니다.
저 또한 힙 정렬에 대해서 완벽하게 이해할 필요를 느낍니다. ^.^
