[Python] 대표적인 정렬 알고리즘

<목차>

1. 버블정렬 (Bubble Sort)

2. 삽입정렬 (Insert Sort)

3. 선택정렬 (Selection Sort)

4. 병합정렬 (Merge Sort)

5. 퀵정렬 (Quick Sort)

6. 힙정렬 (Heap Sort)

 

자료구조와 알고리즘 공부를 다시 시작해보려고 합니다.

강의나 책을 보며 이전에 작성해뒀던 정렬 알고리즘 글들을 복습용으로 올려둡니다.

 

---

1. 버블정렬 (Bubble Sort)

리스트에서 인접한 두 수를 비교하여, 작은 숫자는 왼쪽으로, 큰 숫자는 오른쪽으로 이동합니다.

a. 기본적인 버블정렬

구현이 간단하지만, O(N^2)라는 일정한 시간복잡도가 비효율적인 것이 단점입니다.

def bubbleSort(arr):
    
    length = len(arr) - 1
    
    for i in range(length):
        for j in range(length-i):
            if(arr[j] > arr[j+1]):
                arr[j], arr[j+1] = arr[j+1], arr[j]
                
    return arr

 

b. 개선된 버블정렬

최선의 경우 시간복잡도를 O(N)으로 낮출 수 있습니다.

def bubble_modified(arr):
    
    length = len(arr) - 1
    
    for i in range(length):
        isSort = False
        
        for j in range(length-i):
            if(arr[j] > arr[j+1]):
                arr[j], arr[j+1] = arr[j+1], arr[j]
                isSort = True
                
        if isSort == False:
            break
                
    return arr

---

2. 삽입정렬 (Insert Sort)

key값 뒤에 있는 원소와 순서대로 비교합니다.

시간복잡도는 최선의 경우 O(N), 최악의 경우 O(N^2)입니다.

def insertSort(arr):
    
    for i in range(1,len(arr)):
        key = arr[i]
        j = i - 1
        
        while j >= 0 and key < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
            
        arr[j+1] = key

---

3. 선택정렬(Selction Sort)

가장 작은 값을 갖는 위치를 찾아서 교환합니다.

시간복잡도는 삽입정렬과 동일합니다.

def selectSort(arr):
    
    for i in range(len(arr)-1):
        min_index = i
        
        for j in range(i+1,len(arr)):
            if arr[min_index] > arr[j]:
                min_index = j
        
        arr[i],arr[min_index] = arr[min_index],arr[i]
        
    return arr

---

4. 병합정렬(Merge Sort)

리스트를 left, right로 절반씩 나눕니다. 이 때 리스트 원소가 1개가 될 때까지 나누는 작업을 수행합니다.

나누는 작업이 완료되면 left, right의 원소를 비교해가며 정렬합니다.

시간복잡도는 어떤 경우든 O(NlogN)으로, 안정적이고 일정한 것이 장점입니다.

다만 배열 크기가 매우 큰 경우에는 그닥 좋지 않은 듯 합니다.

def mergeSort(arr):
    
    if len(arr) > 1:
        # 쪼개는 과정
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        
        mergeSort(left)
        mergeSort(right)
        
        #합치는 과정 - 임시로 정렬
        i,j,k = 0,0,0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1
            
        #각각 남아있는 원소 합치기
        while i < len(left):
            arr[k] = left[i]
            i+=1
            k+=1
        while j < len(right):
            arr[k] = right[j]
            j+=1
            k+=1
            
    return arr

---

5. 퀵정렬(Quick Sort)

기준이 되는 pivot 값을 정한 후 pivot 기준으로 분할, 정렬합니다.

시간복잡도는 평균적으로 O(NlogN)으로 빠른 편입니다만, 병합정렬과는 다르게 최악의 경우 O(N^2)로 느려지는 것이 단점입니다.

이 단점을 피하기 위해 pivot을 중간이나 랜덤한 값으로 잡기도 합니다.

def quickSort(arr,low,high):
    
    # pivot이 알맞은 위치에 있어 퀵정렬을 실행해도 되는지 확인
    if low < high:
        #pivot 기준으로 쪼개기 위해 pivot 위치를 가져옴
        pivot_pos = split(arr,low,high)
        
        #그리고 왼쪽과 오른쪽으로 쪼갠다
        quickSort(arr,low,pivot_pos - 1)
        quickSort(arr,pivot_pos + 1,high)
        
    return arr
    
def split(arr,low,high):
    #pivot 정하기
    pivot = arr[(high-low)//2] #정하는 기준은 맘대로 (중간이나 랜덤)
    
    #pivot 기준으로 리스트를 정렬한다.
    i = low - 1
    
    for j in range(low,high):
        if arr[j] < pivot:
            i += 1
            #swap
            arr[i],arr[j] = arr[j],arr[i]
            
    #마지막으로 pivot이 들어갈 위치를 바꿔준다.
    arr[i+1], arr[high] = arr[high], arr[i+1]
    
    #pivot index를 반환한다.
    return i+1

---

6. 힙정렬(Heap Sort)

Heap이란 최댓값 및 최솟값을 찾아내기 위한 완전이진트리 형태의 자료구조입니다.

Heap 형태를 갖추도록 정렬하고 root와 찾아낸 자식 값을 바꾼 뒤 다시 정렬하는 방식입니다.

모든 경우에서 O(NlogN)의 시간복잡도를 갖습니다. (최악의 경우에서도!)

다만 데이터 분포에 따라 결과가 다르게 나올 수도 있습니다.

def heapSort(arr):
    
    n = len(arr)
     
    # heap 형태로 데이터를 정렬한다.
    for i in range(n,-1,-1):
        heapify(arr,n,i)
        
    # root와 마지막값을 바꿔 정렬하고 바뀐값을 기준으로 다시 heapify
    for i in range(n-1,0,-1):
        arr[i],arr[0] = arr[0],arr[i]
        heapify(arr,i,0)
        
    return arr
   
def heapify(arr,n,i):
    root = i
    left = 2*i + 1
    right = 2*i + 2
    
    # 왼쪽 노드가 존재하고, 루트보다 더 큰 값일 때
    if left < n and arr[root] < arr[left]:
        root = left
    
    # 오른쪽 노드가 존재하고, 루트보다 더 큰 값일 때
    if right < n and arr[root] < arr[right]:
        root = right
        
    # 왼쪽, 오른쪽 자식 노드들과 바꿔줄 위치를 찾았을 때
    if root != i:
        # 찾아낸 값과 swap
        arr[i],arr[root] = arr[root],arr[i]
        # 계속 heap 형태를 갖출 때까지 실행
        heapify(arr,n,root)