정렬 알고리즘 정리 + Python 구현 (Bubble sort, Selection sort, Insertion sort, Merge sort, Quick sort)

$O(n^2)$ 실행시간을 갖는 정렬 알고리즘 세 가지와 $O(n\log n)$ 실행시간을 갖는 정렬 알고리즘 두 가지, 그리고 각 정렬 알고리즘의 파이썬 코드를 정리했다.

 

목차

$O(n^2)$ 정렬 알고리즘

• Bubble sort
• Selection sort
• Insertion sort

$O(n\log n)$ 정렬 알고리즘

• Merge sort
• Quick sort

 

다음 사이트에서 각 정렬 알고리즘의 시각화를 한눈에 확인할 수 있다.

Comparison Sorting Visualization

 

 

$O(n^2)$ 정렬 알고리즘

다음의 세 정렬 알고리즘은 swap 함수를 사용한다.

def swap(arr, i, j):
    temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp

 

Bubble sort

 

https://www.resultswebdev.com/bubble-sort-algorithm/

• 한 번 돌 때마다 마지막 하나가 정렬되므로 원소들이 거품이 올라오는 것처럼 보여 거품정렬이다.
• 다른 정렬 알고리즘에 비해 매우 비효율적이지만, 이미 정렬된 자료에서는 한번만 돌면 되기 때문에 최선의 성능을 보여준다 ($O(n)$).
• 정렬 알고리즘은 자료가 정렬되어 있는지 아닌지 모른 상태에서 사용되기 때문에 의미가 있음.

def bubbleSort(arr):
    for i in range(len(arr)):
        swapped = False
	
        for j in range(len(arr)-i-1): #0~N-i-1번째까지
            if arr[j] > arr[j+1]: #adjacent 원소들이 정렬되지 않은 경우 정렬해줌
                swap(arr, j, j+1)
                swapped = True
	
        if not swapped: #swap이 한 iter동안 한번도 발생하지 않은 경우
            break #정렬이 완료됨

 

Selection sort

 

• Early stopping이 불가능하기 때문에 항상 O(n^2) 시간이 걸린다.

def selectionSort(arr):
    for i in range(len(arr)):
        min_index = i
		
        #1. i번부터 끝까지 돌면서 가장 작은 원소를 찾는다
        for j in range(i+1, len(arr)): 
            if arr[i] < arr[j]:
                min_index = j

        #2. i번 자리에 찾은 가장 작은 원소를 넣는다
        swap(arr, i, min_index)

 

Insertion sort

• 배열이 작을 경우에 매우 효율적이다. 따라서 고성능 알고리즘들 중에서는 배열의 사이즈가 클때는 $O(n\log n)$ 알고리즘을 쓰다가 정렬해야 할 부분이 작을때는 삽입 정렬로 전환하는 것들도 있다.

def insertionSort(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1): #현재위치의 왼쪽의 모든 원소에 대해 오른쪽->왼쪽으로 가면서
            if arr[j] < arr[j-1]: #adjacent한 원소들을 조사해서 정렬되지 않은 경우 정렬해준다.
                swap(arr, j, j-1)
            else: #만약 adjacent 한 원소들이 정렬되어 있는 경우 나머지는 모두 정렬되어있는 것이므로 더이상 조사할 필요가 없다.
                break

 

 

$O(n\log n)$ 정렬 알고리즘

Merge sort

• Divide-and-conquer (분할정복) 알고리즘에 속한다.
• Quick sort보다 성능이 떨어지고, 추가적인 메모리가 필요하지만 Stable하다는 장점이 있다. (정렬을 해도 같은 값의 앞뒤 순서가 바뀌지 않음)

def mergeSort(arr):
    if len(arr) > 1:
        #1. Divide
        #중간지점을 기준으로 arr을 두개로 나눈다.
        r = len(arr) // 2
        L = arr[:r]
        R = arr[r:]

        #2. Conquer
        #각 subarr을 sort한다.
        mergeSort(L)
        mergeSort(M)

        i = j = k = 0

        #3. Combine
        #각 subarr의 한 원소씩 비교하면서 작은 값부터 arr에 채워나간다.
        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        #만약 둘 중 하나의 subarr의 끝까지 도달했다면, 남은 subarr로 arr을 다 채운다.
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

 

Quick sort

 

• 마찬가지로 divide-and-conquer 알고리즘이다.
• 평균적인 상황에서 최고의 성능을 나타내고, 많은 언어의 기본 정렬 알고리즘이 이 알고리즘을 바탕으로 구현되어 있다. 그러나 Python의 경우 stable 정렬을 하기 때문에 quick sort를 사용하지 않는다.
• 평균 수행시간은 $O(n\log n)$이지만 최악의 경우에는 $O(n^2)$이다. Pivot의 위치에 성능의 영향을 많이 받는다.
• 다음 구현은 pivot을 항상 배열의 첫 번째 원소로 설정하는 알고리즘인데, 이외에도 pivot을 랜덤한 위치로 설정하거나 (random quick sort), 중간 위치의 원소를 pivot으로 잡는 방법 등이 있다.

def quickSort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    L = []
    R = []

    for data in arr[1:]: #pivot을 기준으로, pivot보다 작은 원소는 L에, 큰 원소는 R에 넣는다. (divide)
        if data <= pivot:
            L.append(data)
        else:
            R.append(data)

    return quick_sort(L) + [pivot] + quick_sort(R) #L과 R을 정렬하고 pivot과 합체 (conquer + combine)

 

 

참고한 자료

• 나무위키 정렬 알고리즘
• Programiz