[알고리즘] 정렬 (버블, 선택, 삽입, 병합, 퀵)

1. 버블정렬 (Bubble Sort)

인접한 두 요소를 비교하여 필요에 따라 위치를 바꾸면서 리스트를 정렬하는 방법입니다. 버블 정렬은 여러 번의 패스를 통해 리스트를 정렬하며, 각 패스에서 가장 큰 요소가 리스트의 끝으로 이동합니다. 이 과정은 마치 "거품이 위로 올라가는" 모습과 비슷해서 버블 정렬이라고 불립니다.

 

최악의 경우 시간 복잡도: O(n^2) (리스트가 역순으로 정렬된 경우)
최선의 경우 시간 복잡도: O(n) (리스트가 이미 정렬된 경우, 이 경우는 최적화된 버블 정렬에서만 적용됩니다)
평균 시간 복잡도: O(n^2)

1.1. 버블 정렬의 작동 원리

1. 리스트의 첫 번째 요소부터 시작하여 인접한 두 요소를 비교합니다.
2. 두 요소가 올바른 순서(오름차순 정렬의 경우 작은 값이 앞에, 큰 값이 뒤에)라면 그대로 두고, 그렇지 않다면 서로 위치를 바꿉니다.
3. 이 과정을 리스트의 끝까지 반복합니다.
4. 첫 번째 패스가 끝나면 가장 큰 요소가 리스트의 마지막 위치에 있게 됩니다.
5. 다음 패스에서는 마지막 요소를 제외하고 나머지 요소들에 대해 같은 작업을 반복합니다.
6. 리스트가 완전히 정렬될 때까지 이 과정을 반복합니다.

1.2. 예시 코드

def bubble_sort(ls):
    n = len(ls)
    for i in range(n): # 리스트 크기만큼 반복
        swapped = False

        for j in range(0, n-i-1): # 한바퀴 돌면 제일큰게 맨뒤로가니까, 그거뺀거임
            if ls[j] > ls[j+1]:
                ls[j], ls[j+1] = ls[j+1], ls[j]
                swapped = True
        if not swapped: # 정렬이 잘되어있으면, 스왑을 안함, 종료
            break

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array is:", arr)

 

2. 선택정렬 (Selection Sort)

선택 정렬(Selection Sort)은 배열을 정렬하는 또 다른 단순한 알고리즘입니다. 이 알고리즘은 배열을 반복적으로 탐색하여 정렬되지 않은 부분에서 가장 작은(또는 가장 큰) 요소를 선택하고, 이를 정렬된 부분의 끝에 위치시키는 방식으로 작동합니다. 선택 정렬은 구현이 간단하지만, 

 

시간 복잡도가 O(n^2)로 효율적이지 않습니다. 

 

작은 데이터셋에서는 사용될 수 있지만, 큰 데이터셋에서는 비효율적입니다.

 

2.1. 작동 원리

1. 주어진 리스트에서 정렬되지 않은 부분 중 가장 작은 요소를 찾습니다.
2. 해당 요소를 리스트의 시작 부분에 있는 요소와 교환합니다.
3. 리스트의 첫 번째 요소를 제외한 나머지 리스트에 대해 위 과정을 반복합니다.
4. 리스트의 모든 요소가 정렬될 때까지 이 과정을 반복합니다.

2.2. 예시 코드

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # Find the minimum element in the remaining unsorted array
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        # Swap the found minimum element with the first element
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array is:", arr)

 

 

3. 삽입 정렬(Insert Sort)

삽입 정렬(Insertion Sort)은 정렬되어 있는 부분 배열에 새로운 요소를 하나씩 삽입하여 전체 배열을 정렬하는 알고리즘입니다. 카드를 정렬하는 방식과 비슷한 방식으로 동작합니다. 초기 부분 배열은 첫 번째 요소만 포함하고, 나머지 요소들은 하나씩 정렬된 부분 배열에 삽입됩니다.

 

최악의 경우 시간 복잡도: O(n^2) (리스트가 역순으로 정렬된 경우)
최선의 경우 시간 복잡도: O(n) (리스트가 이미 정렬된 경우)
평균 시간 복잡도: O(n^2)

 

삽입 정렬은 작은 데이터셋이나 대부분 정렬된 데이터셋에서 효율적입니다.

일반적으로 다른 효율적인 정렬 알고리즘(예: 퀵 정렬, 병합 정렬 등)보다 비효율적입니다.

3.1. 작동 원리

배열의 두 번째 요소부터 시작하여 각 요소를 정렬된 부분 배열에 삽입합니다.
현재 요소를 이전 요소들과 비교하여 적절한 위치에 삽입합니다.
이 과정을 배열의 끝까지 반복하여 배열을 정렬합니다.

 

3.2. 코드 예시

def insertion_sort(arr):
    # Traverse through 1 to len(arr)
    for i in range(1, len(arr)):
        key = arr[i]
        # Move elements of arr[0..i-1], that are greater than key,
        # to one position ahead of their current position
        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("Sorted array is:", arr)

 

 

4. 병합 정렬 (Merge Sort)

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 알고리즘의 하나로, 리스트를 반씩 나누어 각각을 정렬한 다음, 두 리스트를 다시 합쳐서 정렬된 리스트를 만드는 방식입니다. 안정적인 정렬 알고리즘으로, 최악의 경우에도 시간 복잡도가 O(n log n)으로 일정하게 유지되는 특징이 있습니다.

 

4.1. 작동 원리

1. 분할 (Divide): 리스트를 절반으로 나누어 두 개의 하위 리스트로 분할합니다.
2. 정복 (Conquer): 각 하위 리스트를 재귀적으로 병합 정렬을 이용해 정렬합니다.
3. 병합 (Combine): 두 개의 정렬된 하위 리스트를 합쳐 하나의 정렬된 리스트로 만듭니다.

4.2. 코드 예시

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # Find the middle of the array
        L = arr[:mid]        # Dividing the elements into 2 halves
        R = arr[mid:]

        merge_sort(L)        # Sorting the first half
        merge_sort(R)        # Sorting the second half

        i = j = k = 0

        # Copy data to temporary arrays L[] and R[]
        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

        # Checking if any element was left
        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("Sorted array is:", arr)

 

 

5. 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)은 분할 정복(Divide and Conquer) 알고리즘의 하나로, 리스트를 정렬하는 데 매우 효율적입니다. 퀵 정렬은 리스트에서 하나의 요소를 피벗(pivot)으로 선택하고, 피벗을 기준으로 리스트를 두 부분으로 분할하여 재귀적으로 정렬합니다. 평균적으로 O(n log n)의 시간 복잡도를 가지지만, 최악의 경우 O(n^2)까지 증가할 수 있습니다. 피벗 선택 전략에 따라 성능이 달라질 수 있습니다.

5.1. 작동 원리

1. 피벗 선택: 리스트에서 하나의 요소를 피벗으로 선택합니다.
2. 분할: 피벗을 기준으로 리스트를 두 부분으로 나눕니다. 피벗보다 작은 요소들은 피벗의 왼쪽에, 피벗보다 큰 요소들은 피벗의 오른쪽에 위치시킵니다.
3. 재귀 호출: 분할된 두 부분 리스트에 대해 퀵 정렬을 재귀적으로 호출합니다.
4. 병합: 분할과 재귀 호출을 반복하여 리스트가 정렬됩니다.

5.2. 코드 예시

def partition(arr, low, high):
    i = (low - 1)         # index of smaller element
    pivot = arr[high]     # pivot

    for j in range(low, high):
        # If current element is smaller than or equal to pivot
        if arr[j] <= pivot:
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1

def quick_sort(arr, low, high):
    if low < high:
        # pi is partitioning index, arr[pi] is now at right place
        pi = partition(arr, low, high)

        # Separately sort elements before partition and after partition
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quick_sort(arr, 0, n - 1)
print("Sorted array is:", arr)