정렬 알고리즘(Sorting Algorithms)이란 무엇인가?

 

정렬 알고리즘은 데이터를 순서대로 정렬하는 방법을 제공하여 효율적인 데이터 처리를 가능하게 합니다.

이번 포스트에서는 파이썬을 사용하여 다양한 정렬 알고리즘을 소개하고, 각 알고리즘의 코드와 함께 자세한 설명을 제공하겠습니다.

1. 정렬 알고리즘이란?

정렬 알고리즘은 배열이나 리스트와 같은 데이터 집합을 오름차순 또는 내림차순으로 정렬하는 알고리즘입니다.

이는 데이터 검색, 분석, 처리를 위한 기본 작업 중 하나입니다.

2. 정렬 알고리즘의 종류

1. 퀵 정렬 (Quick Sort)

퀵정렬은 분할 정복 알고리즘으로, 피벗을 기준으로 리스트를 나누고 각 부분을 재귀적으로 정렬합니다.

def quick_sort(arr):
    # 리스트의 길이가 1 이하인 경우 이미 정렬된 상태로 간주합니다.
    if len(arr) <= 1:
        return arr
    
    # 피벗은 리스트의 중간 요소입니다.
    pivot = arr[len(arr) // 2]
    
    # 리스트를 피벗을 기준으로 left, middle, right로 분할합니다.
    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)

• 리스트의 길이가 1 이하인 경우 이미 정렬된 상태로 간주합니다.
• 피벗을 리스트의 중간 요소로 선택하여 리스트를 피벗 기준으로 left, middle, right로 나눕니다.
• left는 피벗보다 작은 요소, middle은 피벗과 같은 요소, right는 피벗보다 큰 요소로 나누어 집니다.
• 각 부분을 재귀적으로 정렬한 후 결과를 합칩니다.

장점

• 평균적으로 빠르고, 효율적인 정렬 알고리즘입니다.

단점

• 최악의 경우 시간 복잡도가 O(n^2)일 수 있습니다.

2. 버블정렬 (Bubble Sort)

버블정렬은 인접한 두 요소를 비교하고 교환하여 가장 큰 값이 리스트의 끝으로 이동하는 방식입니다.

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

• 리스트를 반복하면서 인접한 요소를 비교하고 교환하여 가장 큰 값이 리스트의 끝으로 이동합니다.
• 매 반복마다 가장 큰 값이 정렬된 상태가 됩니다.

장점

• 구현이 간단하고 직관적입니다.

단점

• 시간 복잡도가 O(n^2)으로 큰 데이터셋에서는 비효율적입니다.

3. 합병정렬 (Merge Sort)

합병정렬은 리스트를 절반으로 나눈 후, 각각을 재귀적으로 정렬하고 정렬된 두 부분을 병합하여 최종 리스트를 만듭니다.

def merge_sort(arr):
    # 리스트의 길이가 1 이하인 경우 이미 정렬된 상태로 간주합니다.
    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

• 리스트를 두 개의 하위 리스트 L과 R으로 나누고 각각을 재귀적으로 정렬합니다.
• 정렬된 두 하위 리스트를 병합하여 하나의 정렬된 리스트를 만듭니다.
• 병합 과정에서는 두 리스트를 비교하면서 작은 값을 선택하여 결과 리스트에 추가합니다.

장점

• 시간 복잡도가 O(n log n)으로 안정적입니다.

단점

• 추가적인 메모리 사용이 필요합니다.

4. 삽입정렬 (Insertion Sort)

삽입정렬은 각 요소를 정렬된 부분에 삽입하여 전체 리스트를 정렬합니다.

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
    return arr

• 리스트의 각 요소를 하나씩 정렬된 부분에 삽입합니다.
• 삽입할 위치를 찾기 위해 정렬된 부분을 거꾸로 탐색하면서 적절한 위치를 찾습니다.

장점

• 거의 정렬된 데이터에 대해 효율적입니다.

단점

• 시간 복잡도가 O(n^2)으로 큰 데이터셋에서는 비효율적입니다.

5. 선택정렬 (Selection Sort)

선택정렬은 리스트에서 최솟값을 찾아 현재 위치와 교환하는 방식으로 정렬합니다.

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

• 리스트에서 최솟값을 찾아 현재 위치와 교환합니다.
• 매 반복마다 가장 작은 값이 정렬된 상태가 됩니다.

장점

• 구현이 간단하고, 메모리 사용이 적습니다.

단점

• 시간 복잡도가 O(n^2)으로 큰 데이터셋에서는 비효율적입니다.

6. 힙정렬 (Heap Sort)

힙정렬은 힙 자료구조를 사용하여 데이터를 정렬합니다. 최대 힙 또는 최소 힙을 구성하고, 힙에서 요소를 추출하여 정렬합니다.

import heapq

def heap_sort(arr):
    # 배열을 힙으로 변환합니다.
    heapq.heapify(arr)
    # 힙에서 요소를 추출하여 정렬된 리스트를 만듭니다.
    sorted_arr = [heapq.heappop(arr) for _ in range(len(arr))]
    return sorted_arr

• heapify를 사용하여 배열을 힙으로 변환합니다.
• 힙에서 요소를 추출하여 정렬된 리스트를 만듭니다.

장점

• 시간 복잡도가 O(n log n)으로 안정적입니다.

단점

• 구현이 다소 복잡할 수 있습니다.

7. 기수정렬 (Radix Sort)

기수정렬은 숫자의 자릿수를 기준으로 정렬하는 알고리즘입니다. 카운팅 정렬을 하위 정렬로 사용하여 자릿수별로 정렬합니다.

def counting_sort(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10
    
    # 자릿수 기준으로 요소를 카운트합니다.
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1
    
    # 카운트 배열을 누적합으로 변환합니다.
    for i in range(1, 10):
        count[i] += count[i - 1]
    
    # 카운트 배열을 사용하여 요소를 정렬합니다.
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1
    
    # 정렬된 결과를 원본 배열에 복사합니다.
    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    # 배열의 최대값을 찾습니다.
    max_num = max(arr)
    exp = 1
    # 자릿수별로 정렬합니다.
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10
    return arr

• 숫자의 각 자릿수를 기준으로 정렬합니다.
• 카운팅 정렬을 하위 정렬로 사용하여 자릿수별로 정렬합니다.

장점

• 시간 복잡도가 O(nk)로 매우 효율적입니다 (k는 자릿수).

단점

• 숫자 데이터에만 적용 가능하며, 메모리 사용이 많을 수 있습니다.

8. 버킷정렬 (Bucket Sort)

버킷정렬은 데이터를 일정 범위로 나눈 후 각 버킷을 정렬하고, 버킷을 결합하여 최종 정렬된 리스트를 만듭니다.

def bucket_sort(arr):
    if len(arr) == 0:
        return arr

    # 버킷 생성 및 초기화
    min_value, max_value = min(arr), max(arr)
    bucket_range = (max_value - min_value) / len(arr)
    buckets = [[] for _ in range(len(arr))]
    
    # 데이터를 각 버킷에 배분합니다.
    for num in arr:
        index = int((num - min_value) / bucket_range)
        if index == len(arr):
            index -= 1
        buckets[index].append(num)
    
    # 각 버킷을 정렬하고 결과를 합칩니다.
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(sorted(bucket))
    
    return sorted_arr

• 데이터를 일정 범위로 나누어 각 버킷에 배분합니다.
• 각 버킷을 정렬한 후, 정렬된 버킷들을 결합하여 최종 정렬된 리스트를 만듭니다.

장점

• 데이터가 균등하게 분포되어 있을 때 효율적입니다.

단점

• 데이터 분포에 따라 성능이 크게 달라질 수 있습니다.

다양한 상황에서 각 알고리즘이 어떻게 동작하는지 애니메이션으로 비교할 수 있게 해주는 사이트

랜덤 순서일 때(Random), 거의 정렬되어 있을 때(Nearly Sorted), 거꾸로 정렬이 되어 있을 때(Reversed), 중복된 숫자가 많을 때(Few Unique), 총 네 가지 조건에서 각 정렬 알고리즘을 비교해서 보여 줍니다.

 

파이썬에서는 list.sort() 함수가 있는데요. 이런 기본 정렬 함수에서는 어떤 알고리즘을 기본으로 사용할까요?

파이썬과 자바스크립트에서는 삽입 정렬(insertion sort)과 합병 정렬(merge sort)의 하이브리드인 팀소트(timsort)라는 알고리즘을 사용한다고 해요.

두 알고리즘의 장점을 살려 다양한 경우에서 사용할 수 있도록 최적화된 알고리즘이랍니다.

반면 자바에서는 두 개의 피봇으로 하는 퀵 정렬(dual-pivot quicksort)을 쓴다고 해요.

 

https://www.toptal.com/developers/sorting-algorithms

 

 

이제 각 정렬 알고리즘의 특징과 코드 설명을 통해 어떻게 동작하는지 이해할 수 있을 것입니다.

데이터의 특성과 요구사항에 따라 적절한 정렬 알고리즘을 선택해 사용하세요!

정렬 알고리즘의 선택은 데이터의 크기와 특성에 따라 달라집니다. 작은 데이터셋에는 버블 정렬이나 삽입 정렬이 적합할 수 있지만, 큰 데이터셋에는 퀵 정렬이나 병합 정렬이 더 효율적일 수 있습니다.

 

이 포스트가 정렬 알고리즘을 이해하는 데 도움이 되었기를 바랍니다.

각 알고리즘의 동작 원리를 이해하고, 적절한 상황에서 적절한 알고리즘을 선택할 수 있도록 연습해보세요!

공감과 댓글은 저에게 큰 힘이 됩니다.

Starting Google Play App Distribution! "Tester Share" for Recruiting 20 Testers for a Closed Test.

Tester Share [테스터쉐어] - Google Play 앱