정렬 알고리즘

조민수·2024년 2월 5일

알고리즘

자료구조, 알고리즘

목록 보기

2/3

Sorting Algorithm?

n개의 data를 지정한 순서(오름/내림차순...)으로 정렬
수행시간 기준으로 분류할 수 있다.
O(N²)
- Selection Sort : 선택 정렬
- Insertion Sort : 삽입 정렬
- Bubble Sort : 버블 정렬
O(N logN)
- Merge Sort : 병합 정렬
- Heap Sort : 힙 정렬
- Quick Sort : 퀵 정렬

1. Selection Sort

데이터 중 가장 작은 값을 선택해 앞으로 보내는 방법

def selection_sort(arr):
    n = len(arr)
    for idx in range(n):
        # 현재 인덱스를 최솟값으로 가정
        min_index = idx
        # 나머지 부분에서 최솟값 탐색
        for j in range(idx+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        # 찾은 최솟값을 현재 인덱스의 값과 교환
        arr[idx], arr[min_index] = arr[min_index], arr[idx]
    return arr

2. Insertion Sort

데이터를 순서대로 뽑아 해당 값의 적절한 위치로 삽입

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        # 현재 원소보다 큰 원소들을 한 위치씩 뒤로 이동
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        # 현재 원소를 적절한 위치에 삽입
        arr[j + 1] = key
    return arr

3. Bubble Sort

바로 옆(idx, idx + 1) 데이터와 비교해 더 큰 값을 뒤로
Insertion, Selection과 동일한 시간복잡도를 가지나, 연산 수가 많다.
→ 가장 느리다.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        # 마지막 i개의 원소는 이미 정렬된 상태이므로 n-i-1까지만 반복
        for j in range(0, n-i-1):
            # 현재 원소와 다음 원소를 비교하여 순서가 잘못되었으면 교환
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

4. Merge Sort

분할 → 정렬 → 결합 순으로 이루어진다.
Data Array를 부분 배열로 분할하고 해당 부분 배열을 정렬한 뒤 다시 결합
재귀적으로 동작하는 형식
항상 일정한 시간복잡도를 유지할 수 있으나, 메모리가 추가로 필요하다.

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2 
        L = arr[:mid]
        R = arr[mid:] 
        # 각 절반을 재귀적으로 정렬
        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        # 임시 배열에 정렬된 요소들을 병합
        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

        # 남은 요소들을 배열에 복사
        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

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

5. Heap Sort

이진트리 기반 트리형 자료구조
최소 힙 기준 부모는 자식보다 늘 작다.
오름차순 정렬 : 최소 힙 / 내림차순 정렬 : 최대 힙
python에서 기본으로 제공하는 heapq는 최소힙
내림차순 정렬 구현을 위해선 heapq의 원소를 (-) 붙여 정렬 후, (-) 붙여 꺼내면 된다.
가장 크거나 작은 값을 찾는데 O(1) 의 시간복잡도가 소요.

with heapq ( import heapq )

def heap_sort_with_heapq(arr):
	# 최소 힙 구현
    q = []
    for value in arr:
        heapq.heappush(q, value)
    return [heapq.heappop(q) for i in range(len(q))]

without heapq

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

    # 최댓값이 현재의 i가 아니라면 swap
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        # swap 후에 하위 트리 재정렬
        heapify(arr, n, largest)

def heap_sort_without_heapq(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[i], arr[0] = arr[0], arr[i]  # 가장 큰 요소를 끝으로
        heapify(arr, i, 0)

6. Quick Sort

Data들 중 임의의 값을 PIVOT 이라는 기준으로 잡아
PIVOT 보다 작은 값을 앞으로, 큰 값을 뒤로 보낸다.
해당 과정을 재귀적으로 수행
가장 빠른 알고리즘
이미 정렬된 데이터들에 대해 수행할 경우, O(N²) 의 시간복잡도를 가져올 수 있으니 유의해야 한다.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        # 맨 처음 값을 PIVOT으로 설정
        left = [x for x in arr[1:] if x < pivot]
        right = [x for x in arr[1:] if x >= pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)