[Python] 파이썬 정렬 알고리즘 구현

파이썬에서는 다양한 정렬 알고리즘을 사용할 수 있으며, 각각의 알고리즘은 특정 상황에 더 효율적일 수 있다. 오늘은 몇 가지 주요 정렬 알고리즘에 대한 간단한 개념과 코드로 알아보는 시간을 가져보자.

 

 

1. 버블 정렬(Bubble Sort)

---

버블 정렬(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]

# 정렬할 리스트
arr = [6,3,0,5,1]

# 버블 정렬 수행
bubble_sort(arr)

# 정렬된 리스트 출력
print("정렬된 리스트:", arr)

버블 정렬

 

버블 정렬의 주요 특징

1. 비교적 간단한 알고리즘

버블 정렬은 구현이 간단하며 이해하기 쉽지만 큰 데이터 세트에 대해서는 비효율적일 수 있다.

 

2. 안정적인 정렬

안정적인 정렬 알고리즘으로, 동일한 값에 대한 상대적인 순서가 변경되지 않는다.

 

3. 시간 복잡도

최선의 경우 시간 복잡도는 O(n)이다. 하지만 평균 및 최악의 경우에는 O(n^2)이다.

 

 

버블 정렬의 동작 과정

1. 리스트의 첫 번째 원소부터 시작한다.

 

2. 현재 원소와 다음 원소를 비교한다.

 

3. 만약 현재 원소가 다음 원소보다 크다면, 두 원소를 교환한다.

 

4. 리스트의 끝까지 이동하면서 위 과정을 반복한다.

 

5. 한 번의 반복이 끝나면, 가장 큰 원소가 리스트의 마지막에 위치하게 된다.

 

6. 위의 과정을 리스트의 길이만큼 반복하면서 정렬이 완료된다.

 

 

2. 삽입 정렬(Insertion Sort)

---

삽입 정렬(Insertion Sort)은 간단하면서도 효율적인 정렬 알고리즘 중 하나로, 원소들을 하나씩 비교하면서 이미 정렬된 부분 리스트(앞부분)에 적절한 위치에 삽입해 나가는 방식으로 정렬을 수행한다. 이 알고리즘은 정렬되지 않은 부분 리스트를 하나씩 처리하면서 정렬을 완성하는 방식으로 동작한다.

 

예시 코드

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 = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

# 삽입 정렬 수행
insertion_sort(arr)

# 정렬된 리스트 출력
print("정렬된 리스트:", arr)

삽입 정렬

 

삽입 정렬의 주요 특징

1. 안정적인 정렬

삽입 정렬은 안정적인 정렬 알고리즘이다. 동일한 값에 대한 상대적인 순서가 변경되지 않는다.

 

2. 제자리 정렬

입력 리스트 안에서 정렬을 수행하므로 추가 메모리 공간이 필요하지 않다.

 

3. 시간 복잡도

최선의 경우 시간 복잡도는 O(n)이며, 평균 및 최악의 경우에는 O(n^2)이다. 따라서 대량의 데이터에 대해서는 비효율적일 수 있다.

 

 

삽입 정렬의 동작 과정

1. 정렬되지 않은 부분 리스트의 첫 번째 원소를 선택한다. 이 원소는 정렬된 부분 리스트와 비교 대상이 된다.

 

2. 선택한 원소를 이미 정렬된 부분 리스트의 적절한 위치에 삽입한다. 이를 위해 정렬된 부분 리스트를 오른쪽으로 이동하면서 삽입할 위치를 찾는다.

 

3. 나머지 정렬되지 않은 부분 리스트에서 다음 원소를 선택하고 정렬된 부분 리스트에 삽입한다.

 

4. 위 과정을 나머지 원소가 없을 때까지 반복한다.

 

 

3. 선택 정렬(Selection Sort)

---

선택 정렬(Selection Sort)은 간단하면서도 비효율적인 정렬 알고리즘 중 하나이다. 이 알고리즘은 리스트에서 가장 작은(또는 가장 큰) 원소를 찾아서 정렬된 부분 리스트의 맨 앞에 배치하는 방식으로 동작한다. 선택 정렬은 매번 최솟값(또는 최댓값)을 찾아야 하기 때문에 비교 횟수가 많아 대규모 데이터에는 적합하지 않다.

 

예시 코드

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        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]

# 정렬할 리스트
arr = [6,8,3,5,9,10,7,2,4,1]

# 선택 정렬 수행
selection_sort(arr)

# 정렬된 리스트 출력
print("정렬된 리스트:", arr)

=선택 정렬

선택 정렬의 주요 특징

1. 제자리 정렬(In-Place Sorting)

입력 리스트 안에서 정렬을 수행하므로 추가 메모리 공간이 필요하지 않다.

 

2. 비교 횟수

모든 원소를 비교하여 최솟값을 찾는 방식이므로 원소 수가 많을수록 비교 횟수가 증가하며 시간 복잡도가 증가한다.

 

3. 안정성

원소의 상대적인 순서가 변경될 수 있으므로 안정적인 정렬 알고리즘이 아니다.

 

 

선택 정렬의 동작 과정

1. 리스트에서 가장 작은(또는 가장 큰) 원소를 찾는다.

 

2. 이 원소를 정렬된 부분 리스트의 맨 앞에 배치한다. 정렬된 부분 리스트는 초기에는 비어있는 상태이다.

 

3. 나머지 정렬되지 않은 부분 리스트에서 가장 작은(또는 가장 큰) 원소를 찾아 정렬된 부분 리스트의 다음 위치에 배치한다.

 

4. 위 과정을 나머지 원소가 없을 때까지 반복한다.

 

 

4. 병합 정렬(Merge Sort)

---

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 방법을 기반으로 하는 안정적인 정렬 알고리즘 중 하나이다. 이 알고리즘은 입력 리스트를 반으로 나누고, 각각의 부분 리스트를 재귀적으로 정렬한 다음, 정렬된 부분 리스트를 합병하여 최종적으로 정렬된 리스트를 생성한다.

 

예시 코드

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2  # 리스트를 반으로 나누는 중간 인덱스 계산
        left_half = arr[:mid]  # 중간을 기준으로 왼쪽 부분 리스트 생성
        right_half = arr[mid:]  # 중간을 기준으로 오른쪽 부분 리스트 생성

        # 왼쪽과 오른쪽 부분 리스트를 재귀적으로 정렬
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0

        # 두 부분 리스트를 합병
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        # 남은 원소들을 복사
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

# 정렬할 리스트
arr = [2,11,23,13,51]

# 병합 정렬 수행
merge_sort(arr)

# 정렬된 리스트 출력
print("정렬된 리스트:", arr)

병합 정렬

병합 정렬의 주요 특징

1. 안정적인 정렬

병합 정렬은 안정적인 정렬 알고리즘이다. 동일한 값에 대한 상대적인 순서가 변경되지 않는다.

 

2. 효율적인 정렬

병합 정렬은 평균 및 최악의 경우에도 항상 O(n log n)의 시간 복잡도를 가지므로 대규모 데이터에도 효율적으로 작동한다.

 

3. 외부 정렬 

병합 정렬은 내부 정렬뿐만 아니라 대용량 외부 데이터를 정렬하는 데에도 적합한 알고리즘이다.

 

병합 정렬의 동작 과정

1. 주어진 리스트를 반으로 나눈다. 이 과정을 재귀적으로 수행하여 각각의 부분 리스트를 정렬한다. 이때, 리스트가 더 이상 나눠질 수 없을 때까지 분할 작업을 수행한다.

 

2. 분할된 부분 리스트를 두 개씩 합병(Merge)한다. 이때, 두 부분 리스트는 이미 정렬된 상태여야 한다.

 

3. 합병 과정에서 두 부분 리스트의 원소를 비교하여 작은(또는 큰) 값을 새로운 정렬된 리스트에 추가한다. 이 과정을 반복하면서 정렬된 리스트를 생성한다.

 

4. 모든 부분 리스트가 합병되고 정렬된 리스트가 생성될 때까지 위 과정을 반복한다.

 

 

5. 퀵 정렬(Quick Sort)

---

퀵 정렬(Quick Sort)은 효율적이고 널리 사용되는 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 전략을 기반으로 동작한다. 이 알고리즘은 입력 리스트를 두 개의 하위 배열로 분할하고, 각 하위 배열을 독립적으로 정렬한 다음 합병하여 최종적으로 정렬된 리스트를 얻는다. 퀵 정렬은 평균적으로 매우 빠른 속도를 가지며, 많은 정렬 알고리즘 중에서도 가장 효율적인 것 중 하나이다.

 

예시 코드

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

    pivot = arr[-1]
    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 = [35,33,42,10,14,19,27,44,26,31]

# 퀵 정렬 수행
sorted_arr = quick_sort(arr)

# 정렬된 리스트 출력
print("정렬된 리스트:", sorted_arr)

퀵 정렬

 

퀵 정렬의 주요 특징

1. 빠른 속도

평균적으로 O(n log n)의 시간 복잡도를 가지며, 최악의 경우에도 O(n^2)의 시간 복잡도를 가진다. 하지만 빠른 평균 실행 시간을 가지므로 대부분의 상황에서 효율적으로 동작한다.

 

2. 제자리 정렬(In-Place Sorting)

입력 리스트 안에서 정렬을 수행하므로 추가 메모리 공간이 필요하지 않다.

 

3. 불안정 정렬(Unstable Sorting)

동일한 값에 대한 상대적인 순서가 변경될 수 있다.

 

퀵 정렬의 동작 과정

1. 피벗(Pivot) 원소를 선택한다. 피벗은 리스트의 원소 중 하나로, 보통 첫 번째 원소, 마지막 원소 또는 중간 원소를 선택한다.

 

2. 리스트를 피벗을 기준으로 두 개의 하위 배열로 분할한다. 이때, 피벗보다 작은 원소는 왼쪽 배열에, 큰 원소는 오른쪽 배열에 위치하도록 분할한다. 분할은 피벗을 중심으로 왼쪽 배열과 오른쪽 배열을 나누는 것이다.

 

3. 각 하위 배열에 대해 재귀적으로 퀵 정렬을 수행한다. 이를 통해 각 하위 배열이 정렬된다.

 

4. 재귀적인 정렬이 완료되면, 정렬된 하위 배열들을 합병하여 정렬된 리스트를 생성한다.

 

5. 위 과정을 반복하면서 정렬이 완료된다.