Python 코딩테스트 09: 정렬

1. 정렬의 기본 개념

정렬(Sorting)이란 데이터를 특정한 기준에 따라 순서대로 나열하는 과정을 말합니다.

정렬된 데이터는 탐색, 검색, 최적화 문제 등에서 빠르고 효율적인 처리의 기초가 됩니다.

 

정렬 알고리즘은 크게 비교 기반 정렬(Comparison-based Sorting)과 비교 기반이 아닌 정렬(Non-comparison-based Sorting)로 나눌 수 있습니다.

• 비교 기반 정렬: 데이터 간의 비교를 통해 정렬을 수행합니다. 예를 들어, 버블 정렬, 퀵 정렬, 병합 정렬 등이 이에 해당합니다.
• 비교 기반이 아닌 정렬: 데이터를 비교하지 않고 정렬을 수행합니다. 예를 들어, 카운팅 정렬, 기수 정렬 등이 이에 해당합니다.

---

2. Python에서의 기본 정렬 함수

Python에서는 sorted() 함수와 list.sort() 메서드를 사용하여 리스트를 간단히 정렬할 수 있습니다.

두 함수 모두 Timsort라는 알고리즘을 사용합니다.

 

이는 합병 정렬(Merge Sort)와 삽입 정렬(Insertion Sort)의 장점을 결합한 하이브리드 알고리즘입니다.

# sorted() 함수 예시
numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5]
sorted_numbers = sorted(numbers)
print(sorted_numbers)  # 출력: [1, 1, 2, 3, 4, 5, 5, 6, 9]

# list.sort() 메서드 예시
numbers.sort()
print(numbers)  # 출력: [1, 1, 2, 3, 4, 5, 5, 6, 9]

 

 

sorted()는 원본 리스트를 변경하지 않고 정렬된 새로운 리스트를 반환하는 반면, list.sort()는 원본 리스트 자체를 정렬합니다.

---

3. 다양한 정렬 알고리즘과 활용 사례

3.1. 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여 정렬하는 가장 단순한 정렬 알고리즘 중 하나입니다.

시간 복잡도가 O(n^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]

# 사용 예시
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr)  # 출력: [11, 12, 22, 25, 34, 64, 90]

 

3.2. 선택 정렬 (Selection Sort)

선택 정렬은 리스트에서 가장 작은 요소를 찾아서 맨 앞에 위치시키는 과정을 반복합니다.

이 역시 시간 복잡도가 O(n^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]

# 사용 예시
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print(arr)  # 출력: [11, 12, 22, 25, 64]

 

3.3. 삽입 정렬 (Insertion Sort)

삽입 정렬은 정렬된 부분에 새로운 요소를 적절한 위치에 삽입하는 방식으로 동작합니다.

작은 데이터 세트에 대해선 매우 효율적이며, 평균적으로 O(n^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

# 사용 예시
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr)  # 출력: [5, 6, 11, 12, 13]

 

3.4. 병합 정렬 (Merge Sort)

병합 정렬은 리스트를 반으로 나누어 각각을 재귀적으로 정렬한 후, 다시 합병하여 전체를 정렬하는 알고리즘입니다.

시간 복잡도는 O(n log n)으로, 큰 데이터를 정렬하는 데 적합합니다.

 

예시 코드:

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

# 사용 예시
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print(arr)  # 출력: [5, 6, 7, 11, 12, 13]

 

3.5. 퀵 정렬 (Quick Sort)

퀵 정렬은 피벗(pivot)을 기준으로 리스트를 두 개의 부분 리스트로 나누고, 각각을 재귀적으로 정렬하는 방식입니다.

평균적인 시간 복잡도는 O(n log n)이지만, 최악의 경우 O(n^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)

# 사용 예시
arr = [3, 6, 8, 10, 1, 2, 1]
print(quick_sort(arr))  # 출력: [1, 1, 2, 3, 6, 8, 10]

 

3.6. 힙 정렬 (Heap Sort)

힙 정렬은 이진 힙(Binary Heap) 자료구조를 사용하여 정렬하는 알고리즘입니다.

평균 및 최악의 시간 복잡도는 O(n log n)입니다.

 

예시 코드:

import heapq

def heap_sort(arr):
    heapq.heapify(arr)
    sorted_arr = []
    while arr:
        sorted_arr.append(heapq.heappop(arr))
    return sorted_arr

# 사용 예시
arr = [3, 2, 1, 5, 6, 4]
print(heap_sort(arr))  # 출력: [1, 2, 3, 4, 5, 6]

---

4. 정렬 알고리즘 선택의 기준

정렬 알고리즘을 선택할 때는 데이터의 특성과 문제의 요구사항을 고려해야 합니다.

• 데이터 크기가 작은 경우: 삽입 정렬이나 선택 정렬처럼 단순한 알고리즘도 효율적으로 작동할 수 있습니다.
• 데이터 크기가 크고 정렬이 필요: 병합 정렬이나 퀵 정렬처럼 시간 복잡도가 O(n log n)인 알고리즘을 사용하는 것이 좋습니다.
• 메모리가 제한된 환경: 퀵 정렬과 같은 in-place 정렬이 적합합니다.

---

5. 코딩 테스트에서 자주 나오는 정렬 문제 유형

• 정렬된 배열에서 특정 조건을 만족하는 원소 찾기: 정렬 후 이진 탐색을 사용하는 문제
• 두 배열 합치기: 두 정렬된 배열을 합쳐서 새로운 정렬된 배열을 만드는 문제

• 가장 큰 수, 작은 수 찾기: 특정 기준에 따라 데이터를 정렬한 후 최댓값이나 최솟값을 찾는 문제

• ---

  정렬 알고리즘은 코딩 테스트에서 매우 중요하며, 다양한 문제에서 활용됩니다.
• 각 정렬 알고리즘의 특성과 장단점을 이해하고, 문제에 맞게 올바른 알고리즘을 선택하는 것이 중요합니다.

---