정렬 알고리즘 정리(1) - 거품정렬, 선택정렬, 삽입정렬, 퀵정렬, 합병정렬

코난·2025년 5월 13일

CS 면접 정리

목록 보기

73/76

1. 거품 정렬 (버블 정렬)

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

버블 정렬은 인접한 두 수를 비교해서 더 큰 수를 뒤로 보내는 간단한 정렬 알고리즘으로 다음 반복에서는 값이 정해진 마지막 원소를 제외하고 진행합니다.

정렬 대상 데이터 외에 추가 데이터 공간이 필요하지 않기에 제자리 정렬이며 최선, 평균, 최악의 경우 모두 O(n^2)의 시간 복잡도를 가집니다.

구현이 간단하고 직관적인 코드 작성이 가능하나 시간복잡도가 비효율적이고 swap이 빈번하게 일어난다는 단점도 있습니다.

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]

선택 정렬은 데이터에서 최솟값을 찾은 후 해당 값을 가장 앞으로 이동시키고 자리를 고정한 뒤, 이를 제외한 데이터에서 해당 행위를 반복하는 알고리즘입니다.

정렬 대상 데이터 외에 추가 데이터 공간이 필요하지 않기에 제자리 정렬이며 최선, 평균, 최악의 경우 모두 O(n^2)의 시간 복잡도를 가집니다.

구현이 간단하고 직관적인 코드 작성이 가능하나 안정성을 만족하지 않는다는 단점이 있습니다. (같은 값의 요소가 있을 때, 서로의 위치가 바뀔 가능성)

3. 삽입 정렬

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

삽입 정렬은 두번째 데이터부터 시작해 특정한 데이터를 적절한 위치에 삽입하는 알고리즘입니다.

정렬 대상 데이터 외에 추가 데이터 공간이 필요하지 않기에 제자리 정렬이며 평균, 최악의 경우 O(n^2)의 시간 복잡도를 가지나 최선의 경우(모든 데이터 정렬시) O(n)의 시간복잡도를 가집니다.

따라서 삽입 정렬은 알고리즘이 단순하며 많은 데이터가 정렬되어 있을 때 효율적이지만 많은 데이터 이동을 내포하기에 데이터가 많고 클 경우 알맞지 않습니다.

4. 퀵 정렬

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

퀵 정렬은 재귀를 사용하여 이루어지며 피벗(기준점)을 정한 후 피벗보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 이동하며 피벗을 기준으로 나누어진 양쪽 리스트를 대상으로 재귀를 호출하여 정렬하는 알고리즘입니다.

정렬 대상 데이터 외에 추가 데이터 공간이 필요하지 않기에 제자리 정렬이며 평균, 최선의 경우 O(n log n)의 시간 복잡도를 가지나 최악의 경우(모든 데이터 정렬시) O(n^2)의 시간복잡도를 가집니다.

다른 n log n 시간복잡도를 갖는 알고리즘에 비해서도 속도가 매우 빠른편이나 재귀를 사용하지 못하는 상황이거나 이미 정렬된 데이터를 정렬할 경우 성능이 급격하게 낮아진다는 단점이 있습니다.

5. 합병 정렬

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    merged = []
    l = r = 0
    while l < len(left) and r < len(right):
        if left[l] < right[r]:
            merged.append(left[l])
            l += 1
        else:
            merged.append(right[r])
            r += 1
    merged += left[l:]
    merged += right[r:]
    return merged