[알고리즘] Python으로 알아보기 : Sort

bubble sort

인접한 두 원소를 비교하는 가장 간단한 알고리즘

• 배열을 처음부터 끝까지 순회하면서 인접한 두 원소를 비교
• 비교 후 조건에 따라 Swap을 진행
  • 조건이란 오름차순일경우 뒤에 있는 원소가 현재 원소보다 작을 경우 Swap
• 한번 순회시 가장 큰 원소가 가장 뒤에 위치함
• 두번 순회시 두번째로 큰 원소가 마지막에서 두번째 위치에 위치
• 점진적으로 정렬하는 속도는 빨라짐
• 시간 복잡도 : O(n²)
  • 배열이 역순으로 정렬된 경우
  • 평균과 최선 또한 동일
  • 추가적으로 한번도 swap이 일어나지않은경우 조건을 걸어 종료시 정렬된 배열에 한해서 n의 시간복잡도 가짐
    • 크게 의미 없는 경우
• 공간 복잡도 : 1
  • 정렬을 위해 추가적인 배열 사용 안하며
  • 주어진 배열내에서 원소들만 교환
• 간단하고 안전하며 추가적인 메모리 사용량이 없음
• 속도가 오래 걸리기 때문에 사용을 안하는 경우도 있음

구현 예시

def bubble_sort(arr):
    n = len(arr)

    for i in range(n-1):
        for j in range(n-1-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

---

Heap sort

힙을 사용하는 정렬 알고리즘 방식

• 불안정한 특징을 가짐
• 시간복잡도 : O(n log n)
• 공간 복잡도 : 1
  • 추가 메모리 사용하지 않음 

과정

1. 정렬되지 않은 배열을 최대 힙으로 구성 : 시간복잡도 O(n)
2. 루트의 최댓값을 마지막 원소와 교환하고 힙 크기 줄임

def heapify(arr, heapSize, rootIndex):
    large = rootIndex
    left = 2 * rootIndex + 1
    right = 2 * rootIndex + 2

    if left < heapSize and arr[left] > arr[rootIndex]:
        large = left

    if right < heapSize and arr[right] > arr[rootIndex]:
        large = right

    if large != rootIndex:
        arr[rootIndex], arr[large] = arr[large], arr[rootIndex]
        heapify(arr, heapSize, large)

def heapSort(arr):
    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

---

Merge sort

분할 정복 방식을 사용

• 배열을 계속 절반으로 나누고 각 부위를 재귀적으로 정렬 후 정렬된 두 부분을 합침
• 안정적인 특징을 가짐
• 시간복잡도 : O(n log n)
• 공간 복잡도 : n
  • 각 원소를 담을 추가적인 배열이 필요함 

def mergeSort(arr):
    if len(arr) == 1: return arr

    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    return merge(mergeSort(left), mergeSort(right))

def merge(left, right):
    result = []
    leftIndex = 0
    rightIndex = 0
    while leftIndex < len(left) and rightIndex < len(right):
        if left[leftIndex] <= right[rightIndex]:
            result.append(left[leftIndex])
            leftIndex += 1
        else:
            result.append(right[rightIndex])
            rightIndex += 1
    return result + left[leftIndex:] + right[rightIndex:]

---

Quick sort

분할 정복 방식을 사용

• 효율적인 정렬 알고리즘
• 피벗이라는 기준 원소를 선택
  • 피벗보다 작은 원소들은 왼쪽
  • 피벗보다 큰 원소들은 오른쪽
• 분할이 끝나면 각 부분을 재귀적으로 정렬
• 병합 정렬과의 차이
  • 병합 정렬
    • 추가적인 메모리 사용
    • 병합 과정이 시간이 걸림
  • 퀵 정렬
    • 추가적인 메모리 사용 안함
    • 분할과정이 시간이 걸림

구현 예시

def quickSort(arr, left = 0, right = None):
    if right is None:
        right = len(arr)-1
    if left < right:
        pivotIndex = partition(arr, left, right)

        quickSort(arr, left, pivotIndex-1)
        quickSort(arr, pivotIndex+1, right)
    
    return arr

def partition(arr, left, right):
    pivot = arr[right]
    i = left -1

    for j in range(left, right):
        if arr[j] < pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[right] = arr[right], arr[i+1]
    return i + 1 #피벗의 최종 위치 반환