[Python] 파이썬 정렬 알고리즘 구현 (선택정렬, 삽입정렬, 퀵정렬, 힙정렬, 버블정렬)

파이썬은 다양한 알고리즘을 구현할 수가 있습니다.

이 중에서도 가장 기본적인 알고리즘인 정렬(Sorting) 알고리즘을 알아보겠습니다.

 

정렬 알고리즘

선택 정렬(Selection Sort)

선택 정렬은 배열에서 최소값을 찾아 가장 앞에 있는 값과 교환하고, 그 다음으로 작은 값을 찾아 그 다음 위치의 값과 교환하는 방식으로 정렬하는 알고리즘입니다.

 

선택정렬의 시간 복잡도는 O(n^2)으로, 비교적 간단하지만 데이터가 많을 경우에는 느리게 작동하는 단점이 있습니다. 그러나 정렬하려는 배열 안에서 교환(Swapping)을 수행하는 특징으로 인해, 메모리를 효율적으로 사용할 수 있는 장점이 있습니다.

 

예시코드

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

 

삽입 정렬(Insertion Sort)

삽입 정렬은 두 번째 인덱스부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후 원소를 뒤로 옮기고 지정된 자리에 원소를 삽입하며 정렬하는 알고리즘입니다. 즉, 현재 원소가 이미 정렬된 앞쪽의 원소들과 비교하면서 자신이 들어갈 위치를 찾아 삽입하는 과정을 반복하며 정렬합니다.

 

삽입 정렬의 시간 복잡도는 O(n^2)으로 선택 정렬과 버블 정렬과 같이 비효율적입니다. 하지만 삽입 정렬은 데이터가 거의 정렬되어 있을 때는 빠른 속도를 보이며, 데이터의 양이 적을 때도 효율적입니다.

 

예시코드

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

 

퀵 정렬(Quick Sort)

퀵 정렬은 분할 정복(divide and conquer) 방법을 기반으로 한 정렬 알고리즘 중 하나로, 평균적으로 가장 빠른 정렬 알고리즘 중 하나로 알려져 있습니다.

퀵 정렬은 다음과 같은 과정으로 이루어집니다.

1. 리스트 중 하나의 원소를 선택합니다. 이를 pivot이라고 부릅니다.
2. pivot을 기준으로 리스트를 두 개의 부분 리스트로 나눕니다. pivot보다 작은 값은 왼쪽 부분 리스트, 큰 값은 오른쪽 부분 리스트에 위치시킵니다.
3. 각 부분 리스트에 대해 1단계부터 재귀적으로 수행합니다.
4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복합니다.

퀵 정렬은 평균적으로 O(n log n)의 시간 복잡도를 가집니다. 하지만 pivot의 선택 방법에 따라 최악의 경우 O(n^2)의 시간 복잡도를 가질 수도 있습니다. 따라서 pivot을 잘 선택하는 것이 중요합니다.

 

예시코드

def quicksort(arr):
    # 배열의 크기가 1 이하이면 정렬할 필요가 없으므로 해당 배열을 반환한다.
    if len(arr) <= 1:
        return arr
    
    # 배열의 가운데 값을 pivot으로 지정한다.
    pivot = arr[len(arr) // 2]
    
    # pivot을 기준으로 작은 값은 left 배열, 큰 값은 right 배열, 같은 값은 equal 배열에 담는다.
    left = []
    right = []
    equal = []
    for num in arr:
        if num < pivot:
            left.append(num)
        elif num > pivot:
            right.append(num)
        else:
            equal.append(num)
    
    # left, equal, right 배열을 각각 재귀적으로 정렬한 후 합쳐서 반환한다.
    return quicksort(left) + equal + quicksort(right)

 

반응형

 

힙 정렬(Heap Sort)

힙 정렬은 힙(Heap) 자료구조를 이용하여 구현하는 정렬 알고리즘입니다. 힙은 완전 이진 트리 구조를 가지며, 부모 노드와 자식 노드 간의 대소 관계가 성립하는 자료구조입니다. 힙 정렬은 주어진 배열을 힙으로 만들고, 가장 큰 값을 추출하여 배열의 뒤부터 차례대로 저장하는 방식으로 정렬을 수행합니다.

힙 정렬 알고리즘은 다음과 같습니다.

1. 주어진 배열을 힙으로 만듭니다.
2. 힙에서 가장 큰 값을 추출하여 배열의 가장 뒤에 저장합니다.
3. 추출한 값을 제외한 나머지 요소들로 다시 힙을 만듭니다.
4. 위 과정을 반복하여 모든 요소를 정렬합니다.

힙 정렬 알고리즘의 시간 복잡도는 O(n log n)입니다. 힙 정렬은 정렬할 배열의 크기가 큰 경우에 유용한 알고리즘입니다.

 

예시코드

def heapify(arr, n, i):
    """
    주어진 배열을 힙으로 만드는 함수입니다.
    """
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[largest] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)


def heap_sort(arr):
    """
    Heap Sort 알고리즘을 구현한 함수입니다.
    """
    n = len(arr)

    # 주어진 배열을 힙으로 만듭니다.
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # 추출한 값을 제외한 나머지 요소들로 다시 힙을 만들고 정렬합니다.
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)

    return arr

 

버블 정렬(Bubble Sort)

버블 정렬은 인접한 두 개의 원소를 비교하여 크기가 작은 원소를 왼쪽으로, 큰 원소를 오른쪽으로 교환하는 과정을 반복하여 정렬하는 알고리즘입니다.

버블 정렬의 알고리즘은 매우 간단합니다.

1. 리스트를 왼쪽부터 순서대로 검사하면서 인접한 두 개의 원소를 비교하여 크기가 작은 원소를 왼쪽으로 이동시킨다.
2. 큰 원소는 그대로 두고 과정을 반복합니다.
3. 1, 2 과정을 수행하면 가장 큰 원소가 리스트의 마지막으로 이동하기 때문에 나머지 원소에 대해서만 1, 2 과정을 반복합니다.
4. 점점 리스트의 크기가 줄어가면서 위의 과정을 반복하면 리스트가 정렬이 됩니다.

하지만 버블 정렬은 비효율적인 알고리즘이며, 최악의 경우 시간 복잡도가 O(n^2)이기 때문에 대부분의 상황에서는 사용하지 않습니다.

 

예시코드

def bubble_sort(arr):
    n = len(arr)
    # 반복문을 돌면서 인접한 두 원소를 비교
    for i in range(n-1):
        for j in range(n-i-1):
            # 현재 원소가 다음 원소보다 크면 두 원소의 위치를 바꿈
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr
    
/* [4, 2, 1, 3] 이라는 리스트를 정렬한다고 하면, 
   처음에는 4와 2를 비교하여 위치를 바꿔 [2, 4, 1, 3] 이 되고, 
   다음에는 4와 1을 비교하여 위치를 바꿔 [2, 1, 4, 3] 이 되는 식으로 
   반복적으로 정렬을 수행하게 됩니다. */

 

 

파이썬을 이용한 정렬 알고리즘과 알아보았습니다. 이를 이용하여 데이터를 효율적으로 처리하고 분석할 수 있으며, 정렬알고리즘은 파이썬뿐만 아니라 프로그래밍에서 핵심적인 개념이므로 알아두시는게 좋습니다.

---

 

[Python] 파이썬 자료구조 구현 (스택(stack), 큐(queue), 트리(tree))

[Python] 파이썬 자료구조 구현 (스택(stack), 큐(queue), 트리(tree))