파이썬 정렬 알고리즘 Sort Algorithms

데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 일을 말합니다.

정렬알고리즘은 시간 복잡도에 따라 성능이 평가되고 성능이 좋을 수록 구현이 어려워집니다.

 

대표적인 정렬알고리즘입니다.

• simple sort
  • Bubble sort (버블 정렬)
  • Selection sort (선택 정렬)
  • Insertion sort (삽입 정렬)
• complex sort
  • Merge sort (병합 정렬)
  • Quick sort (퀵 정렬)

정렬알고리즘의 time complexity를 비교해면 다음과 같습니다.

time complexity는 n개의 입력에대해 알고리즘이 문제를 해결하는데 얼만큼의 시간이 걸리는지를 나타내는 것입니다. 

simple sort가 complex sort보다 time complexity가 높은것을 알수 있습니다. 

 

그럼 정렬알고리즘을 하나씩 살펴보도록 합시다.

 

I. 버블 정렬 (Bubble Sort)

• 인접한 두 숫자를 비교하며 정렬하는 방법으로 O(n²)의 느린 성능을 가지고 있습니다
• 맨 끝 인접한 두 숫자를 비교하기 시작하여 연속적으로 인접한 두 숫자를 비교합니다. 비교한 두 숫자의 정렬순서가 맞지 않을 경우에는 교환합니다. 

Improved bubble sort algorithm

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]
            print(arr)


# 정렬하고자 하는 리스트를 만듭니다.
numbers = [3, 1, 4, 5, 9, 2]

# 버블 정렬 함수를 호출하여 리스트를 정렬합니다.
bubble_sort(numbers)

# 정렬된 결과를 출력합니다.
print("정렬된 리스트:", numbers)

 

단점

 

 - 토끼 데이터 (rabbit data)

 : 왼쪽에 있는 큰 데이터들을 빠르게 자신의 위치로 이동함

- 거북이 데이터 (turtle data)

: 오른쪽에 있는 작은 데이터들은 매우 느리게 자신의 위치로 이동함 

 

➞ Bubble sort의 단점을 개선한 sort 알고리즘

 

1. Cocktail Shaker Sort

• 거북이 데이터를 빠르게 제 위치로 이동시킴
• time complexity : O(n²)
• 한번은 왼쪽 한번은 오른쪽 번갈아가면서 진행

2. Comb Sort

• bubble sort에서 거북이 데이터를 줄이고자 함
• 비교하는 두 데이터의 거리(gap)를 조정하여 sort를 진행 
• gap의 크기에 따라 comb sort의 효율성이 달라짐

 

 

II. 선택 정렬 (Selection Sort) 

• 정렬 중간 과정에 데이터를 두 부분으로 나누어서 왼쪽에는 정렬된 데이터, 오른쪽에는 정렬이 되지 않은 데이터로 나누어 점차 정렬된 데이터를 늘려가는 방식으로 정렬하는 방법으로 O(n²)의 느린 성능을 가지고 있습니다
• 정렬되지 않은 오른쪽 데이터에서 제일 작은 데이터를 검색하여 선택하고 오른쪽 데이터의 제일 앞 숫자와 교환합니다. 

Improved bubble selection algorithm

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        # i를 기준으로 최소값을 찾아서 i 위치와 교환
        min_index = i
        for j in range(i+1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        
        arr[i], arr[min_index] = arr[min_index], arr[i]
        print(arr[:i+1])
            

# 정렬하고자 하는 리스트를 만듭니다.
numbers = [3, 1, 4, 5, 9, 2]

# 선택 정렬 함수를 호출하여 리스트를 정렬합니다.
selection_sort(numbers)

# 정렬된 결과를 출력합니다.
print("정렬된 리스트:", numbers)

 

단점

 

데이터의 이동횟수가 많고 값이 같은 요소들의 상대적인 순서를 유지하지 못 할 수도있어 불안정한 정렬입니다(not stable). 또한 이미 정렬된 데이터와 정렬되지 않은 데이터에 대해서 동일한 수행시간을 가지기 때문에 초기데이터의 순서에 상관없이 항상 비효율적인 시간복잡도를 가지게 됩니다.

 

III. 삽입 정렬 (Insertion Sort)

• 리스트를 순회하며 각 요소를 적절한 위치에 삽입하여 정렬하는 방법으로 O(n²)의 느린 성능을 가지고 있습니다.
• 정렬된 데이터를 점차 늘려가며 추가되는 데이터를 알맞은 자리에 삽입하는 방식으로 정렬합니다. 왼쪽에 정렬된 데이터 ,오른쪽에 정렬되지 않은 데이터를 놓고 오른쪽 데이터의 제일 앞 숫자를 왼쪽의 정렬된 데이터의 제 위치에 삽입합니다. 

Improved insertion sort algorithm

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # key를 정렬된 부분으로 삽입
        while j >= 0 and key < arr[j]:   
            arr[j + 1] = arr[j]
            j -= 1   
        arr[j + 1] = key
        print(arr)

# 정렬하고자 하는 리스트를 만듭니다.
numbers = [3, 1, 4, 5, 9, 2]

# 삽입 정렬 함수를 호출하여 리스트를 정렬합니다.
insertion_sort(numbers)

# 정렬된 결과를 출력합니다.
print("정렬된 리스트:", numbers)

 

단점 

• Insertion sort는 요소를 삽일 할 때마다 비료를 수행하기 때문에 비교횟수가 많습니다. 그래서 이미 배열이 정렬된 경우에도 여전히 비교가 많이 발생하므로 비효율적입니다. 
• 따라서 삽입 정렬은 작은 크기의 데이터나 이미 거의 정렬된 데이터에 대해서는 꽤 효율적이지만, 대부분의 경우 성능이 좋지 않습니다. 

➞ Insertion sort의 단점을 개선한 sort 알고리즘

 

1. Shell Sort

• Insertion sort가 어느정도 정렬도니 배열에 대해서는 대단히 빠른것에 착안한 알고리즘입니다. 
• 두 숫자들 사이의 gap을 좁혀서 서로 멀리 떨어져있는 숫자들을 정렬하기 위해 사용합니다. 
• gap은 정렬할 원소들이 떨어져있는 거리를 나타냅니다. 처음에는 큰 gap을 사용하여 시작하지만, 점점 gap을 작게 만들어 최종적으로는 1이 됩니다. gap이 1이면 기본 insertion sort와 동일합니다. 

➞  Shell sort에 대한 자세한 설명

[알고리즘] 셸 정렬(shell sort)이란 - Heee's Development Blog

 

IV.  병합 정렬 (Merge Sort) 



• 재귀와 분할정복을 사용한 분할 정복 알고리즘의 하나로 O(n log n)의 시간 복잡도를 가지고 있습니다. 
• 분할 정복 방법은 문제를 작은 문제로 분리하여 각각을 해결한 다음, 정복한 결과를 통합하여 원래 문제를 해결하는 전략입니다. 

Improved merge sort algorithm

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 중간 지점을 찾아 리스트를 두 개로 나눕니다.
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # 재귀적으로 두 개의 하위 리스트를 정렬합니다.
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # 두 개의 정렬된 리스트를 병합합니다.
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0

    # 두 개의 리스트를 비교하면서 작은 값을 결과에 추가합니다.
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # 남은 요소들을 결과에 추가합니다.
    result.extend(left[i:])
    result.extend(right[j:])
    return result

# 정렬하고자 하는 리스트를 만듭니다.
numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

# 병합 정렬 함수를 호출하여 리스트를 정렬합니다.
sorted_numbers = merge_sort(numbers)

# 정렬된 결과를 출력합니다.
print("정렬된 리스트:", sorted_numbers)

 

V.  퀵 정렬 (Quick Sort) 

• merge sort와 마찬가지로 분할 정복 알고리즘을 사용한 정렬알고리즘으로  O(n log n)의 시간 복잡도를 가지고 있습니다. 
• merge sort는 데이터를 균등하게 분할하였다면 Quick Sort는 pivot(기준원소)을 설정하고 그 기준으로 정렬합니다. 
• pivot을 중심으로 pivot보다 작은 원소는 왼쪽 큰 값은 오른쪽으로 옮겨진다. pivot을 제외한 왼쪽 데이터와 오른쪽 데이터를 다시 정렬합니다. 분활된 리스트에 대하여 이 과정을 반복합니다. 
• Quick Sort는 불안정 정렬에 속하고 매우 빠른 수행속도와 추가 메모리 공간을 필요로 하지 않기 때문에 많은 언어의 정렬 내장 함수로 Quick Sort를 수행합니다. 

Improved Quick sort algorithm

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)

# 정렬하고자 하는 리스트를 만듭니다.
numbers = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

# 퀵 정렬 함수를 호출하여 리스트를 정렬합니다.
sorted_numbers = quick_sort(numbers)

# 정렬된 결과를 출력합니다.
print("정렬된 리스트:", sorted_numbers)

단점

• 정렬된 리스트에 대해서는 Quick Sort의 불균형 분할때문에 오히려 수행시간이 더 많이 걸린다.
• pivot을 선택할때 불균형 분할을 방지하기 위하여 적절한 pivot을 선택해야한다.

 

참고) 

• https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html
• https://velog.io/@jguuun/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98