241128 CS 스터디

정렬 알고리즘

• 컴퓨터 과학이나 수학에서 원소들을 번호순이나 사전 순과 같이 순서대로 열거하는 중요한 알고리즘
• 점근 표기법, 분할 정복 알고리즘, 자료 구조, 최악/평균/최선의 경우 등 다양한 핵심 알고리즘의 개념을 설명하는 데에 적합
• 개발하면서 생기는 문제를 해결하는 아이디어를 생각하는 데에 유용함
• 데이터의 정규화나 의미있는 결과물을 생성하는 데에 유용함

이름	최악의 경우	평균의 경우	최선의 경우	안정성
삽입정렬	$n^2$	$n^2$	$n$	O
선택정렬	$n^2$	$n^2$	$n^2$	X
버블정렬	$n^2$	$n^2$	$n$	O
퀵정렬	$n^2$	$nlogn$	$nlogn$	X
병합정렬	$nlogn$	$nlogn$	$nlogn$	O
힙정렬	$nlogn$	$nlogn$	$nlogn$	X

1) 삽입 정렬

• 배열의 각 요소를 적절한 위치에 삽입하는 정렬방식
• 최선의 경우 시간복잡도가 $n$으로 작은 데이터셋에 대해 효율적임

(1) 알고리즘 수행 단계

1. 배열의 첫 번째 요소를 정렬된 부분으로 간주
2. 다음 요소를 정렬된 부분과 비교하여 적절한 위치에 삽입
3. 이 과정을 배열의 마지막 요소까지 반복해 정렬

(2) 구현 코드

def insertion_sort(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

2) 선택 정렬

• 배열에서 최솟값을 찾아 첫 번째 요소와 자리를 바꾸는 과정을 반복하는 정렬방식
• 알고리즘이 단순해 사용할 수 있는 메모리가 제한적인 경우에 효율적임

(1) 알고리즘 수행 단계

1. 배열에서 최솟값을 찾아 배열의 첫 번째 요소와 교환
2. 배열의 두 번째 요소부터 마지막 요소까지 1번을 반복해 정렬

(2) 구현 코드

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

3) 버블 정렬

• 인접한 두 요소를 비교하며 정렬의 조건에 맞게 자리를 바꾸는 과정을 반복하는 정렬방식
• 최악의 경우 시간복잡도가 $n^2$으로 느리지만 코드가 단순하기 때문에 자주 사용됨

(1) 알고리즘 수행 단계

1. 배열의 첫 번째 요소부터 인접한 요소를 비교
2. 두 요소를 비교하여 정렬의 조건에 따라 자리를 바꾸거나 바꾸지 않음
3. 배열의 끝까지 이 과정을 반복하고 정렬이 완료되지 않았을 경우 다음 패스를 시작
4. 하나의 패스에서 1~3번을 수행하며 정렬이 완료될 때까지 패스를 반복

(2) 구현 코드

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        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) 퀵 정렬

• 분할 정복 알고리즘을 사용하는 정렬방식
• 피벗(pivot)이라는 기준점을 선택하고 정렬의 조건에 따라 피벗 왼쪽, 피벗 오른쪽으로 적절한 값을 분할하여 재귀적으로 정렬
• 최악의 경우 시간복잡도가 $n^2$이지만 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계하므로 해당 경우가 거의 발생하지 않도록 알고리즘 설계가 가능함
• 매 단계에서 적어도 1개의 원소가 자리를 찾으므로 정렬을 하면 할수록 정렬할 개수가 줄어듦
• 일반적인 경우 $nlogn$의 시간복잡도를 가진 알고리즘에 비해 훨씬 빠르게 동작함

(1) 알고리즘 수행 단계

1. 배열에서 임의로 기준점이 될 피벗 요소를 선택
2. 오름차순일 경우 피벗보다 작은 요소들은 왼쪽에, 큰 요소들은 오른쪽에 배치하고 내림차순일 경우 반대로 배치
3. 피벗을 기준으로 배열을 두 부분으로 나눔
4. 각 부분을 재귀적으로 정렬

(2) 구현 코드

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

5) 병합 정렬

• 분할 정복 알고리즘을 사용한 정렬방식
• 배열을 반으로 나눠 각 부분을 정렬한 다음 그 결과를 병합

(1) 알고리즘 수행 단계

1. 배열을 절반으로 나눔
2. 각 부분을 재귀적으로 정렬
3. 정렬된 두 부분을 병합하는 것을 반복해 정렬

(2) 구현 코드

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

    return arr

6) 힙 정렬

• 힙 데이터를 이용한 정렬방식
• 오름차순 정렬 시 최대 힙, 내림차순 정렬 시 최소 힙을 구성하여 정렬

(1) 알고리즘 수행 단계

1. 배열을 힙으로 변환
2. 최대 힙의 루트 요소를 제거하고 배열의 마지막 요소와 교환
3. 힙의 크기를 줄이고 힙 속성을 유지
4. 2~3번을 반복하며 정렬

(2) 구현 코드

def heapify(arr, n, i):
    largest = i  # 루트를 최대값으로 가정
    l = 2 * i + 1  # 왼쪽 자식
    r = 2 * i + 2  # 오른쪽 자식

    # 왼쪽 자식이 루트보다 크다면
    if l < n and arr[l] > arr[largest]:
        largest = l

    # 오른쪽 자식이 현재 최대값보다 크다면
    if r < n and arr[r] > arr[largest]:
        largest = r

    # 최대값이 루트가 아니라면
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # 교환

        # 교환된 루트에 대해 다시 힙 구성
        heapify(arr, n, largest)

def heap_sort(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)

참고

• 『이것이 취업을 위한 컴퓨터 과학이다』 (한빛미디어) 깃허브
• 정렬 알고리즘 - 위키백과
• 13장 정렬 알고리즘 - 좌충우돌, 파이썬으로 자료구조 구현하기