Python에서 정렬 알고리즘 구현
프로그래밍에서 정렬은 매우 중요한 기능 중 하나입니다. 효율적인 정렬 알고리즘을 선택하는 것은 프로그램 실행 시간을 크게 단축할 수 있습니다.
이 글에서는 여러 가지 정렬 알고리즘을 살펴보고 각각의 특징과 작동 방식을 자세히 알아보겠습니다.
다양한 정렬 알고리즘의 구현 단계를 Python을 사용하여 설명합니다. 알고리즘의 원리를 이해하면 다른 프로그래밍 언어로도 쉽게 적용할 수 있습니다. 언어별 문법 차이만 고려하면 됩니다.
이 튜토리얼에서는 효율성이 낮은 알고리즘부터 효율적인 알고리즘까지 다양한 정렬 방법을 살펴보겠습니다. 각 알고리즘의 작동 방식을 이해하고 직접 구현해보는 시간을 가져보세요.
그럼 지금부터 여러 정렬 알고리즘에 대해 자세히 알아보겠습니다.
삽입 정렬
삽입 정렬은 구현이 비교적 간단한 정렬 알고리즘입니다. 하지만 배열의 크기가 커질수록 정렬 시간이 길어지는 단점이 있어, 큰 데이터셋에는 적합하지 않습니다.
삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어 처리합니다.
정렬된 부분은 초기에는 배열의 첫 번째 요소만 포함합니다. 정렬되지 않은 부분의 요소를 하나씩 가져와 정렬된 부분의 적절한 위치에 삽입하는 방식으로 정렬을 수행합니다.
삽입 정렬의 작동 방식을 단계별 예시를 통해 시각적으로 살펴보겠습니다.
삽입 정렬 구현 단계를 자세히 알아봅시다.
- 정수형 더미 데이터로 배열을 초기화합니다.
- 두 번째 요소부터 배열을 순회합니다.
- 현재 요소의 위치와 값을 변수에 저장합니다.
- 현재 요소보다 작은 요소가 배열의 앞부분에 나올 때까지 반복하는 루프를 작성합니다.
- 현재 위치의 요소를 이전 위치의 요소로 덮어씁니다.
- 현재 위치를 하나 감소시킵니다.
- 루프가 끝나면 배열의 처음 위치에 도달했거나 현재 요소보다 작은 요소를 찾은 것입니다. 현재 위치에 현재 요소를 삽입합니다.
삽입 정렬의 시간 복잡도는 O(n^2)이며, 공간 복잡도는 O(1)입니다.
이제 삽입 정렬로 배열 정렬이 완료되었습니다. 다음 코드를 실행하여 결과를 확인해봅시다. Python이 설치되어 있지 않다면 온라인 Python 컴파일러를 이용할 수도 있습니다.
def insertion_sort(arr, n): for i in range(1, n): ## 현재 위치와 요소 저장 current_position = i current_element = arr[i] ## 배열의 처음이나 현재 요소보다 작은 요소를 만날 때까지 반복 while current_position > 0 and current_element < arr[current_position - 1]: ## 현재 위치 요소 업데이트 arr[current_position] = arr[current_position - 1] ## 이전 위치로 이동 current_position -= 1 ## 현재 위치 요소 업데이트 arr[current_position] = current_element if __name__ == '__main__': ## 배열 초기화 arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] insertion_sort(arr, 9) ## 정렬된 배열 출력 print(str(arr))
선택 정렬
선택 정렬은 삽입 정렬과 유사하지만, 약간 다른 방식으로 작동합니다. 이 알고리즘 역시 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눕니다. 각 반복 단계에서 정렬되지 않은 부분에서 가장 작은 요소를 찾아 정렬된 부분의 마지막 위치에 추가합니다.
선택 정렬의 작동 방식을 시각적으로 살펴보면 더 쉽게 이해할 수 있습니다.
선택 정렬 구현 단계를 자세히 알아봅시다.
- 정수형 더미 데이터로 배열을 초기화합니다.
- 배열을 순회합니다.
- 가장 작은 요소의 인덱스를 저장할 변수를 초기화합니다.
- 현재 요소부터 배열의 마지막 요소까지 순회하는 루프를 작성합니다.
- 현재 요소가 가장 작은 요소보다 작은지 확인합니다.
- 현재 요소가 가장 작은 요소보다 작으면 인덱스를 업데이트합니다.
- 가장 작은 요소의 인덱스를 찾았으면 현재 요소와 해당 인덱스의 요소를 교체합니다.
선택 정렬의 시간 복잡도는 O(n^2)이고, 공간 복잡도는 O(1)입니다.
삽입 정렬과 마찬가지로 선택 정렬도 직접 구현해 보세요. 아래 코드에서 구현 예시를 확인할 수 있습니다.
def selection_sort(arr, n): for i in range(n): ## 최소 요소의 인덱스 저장 min_element_index = i for j in range(i + 1, n): ## 최소 요소 인덱스 확인 및 업데이트 if arr[j] < arr[min_element_index]: min_element_index = j ## 현재 요소와 최소 요소 교환 arr[i], arr[min_element_index] = arr[min_element_index], arr[i] if __name__ == '__main__': ## 배열 초기화 arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] selection_sort(arr, 9) ## 정렬된 배열 출력 print(str(arr))
버블 정렬
버블 정렬은 구현이 매우 간단한 알고리즘입니다. 배열을 순회하면서 인접한 요소를 비교하여 순서가 맞지 않으면 교환하는 작업을 반복합니다.
배열의 처음부터 순회하면서 현재 요소가 다음 요소보다 작은지 확인하고, 필요에 따라 위치를 교환하는 방식으로 정렬합니다.
다음 그림들을 통해 버블 정렬의 동작 방식을 시각적으로 이해해 보세요.
버블 정렬 구현 단계를 자세히 알아봅시다.
버블 정렬의 시간 복잡도는 O(n^2)이고, 공간 복잡도는 O(1)입니다.
이제 버블 정렬을 직접 구현해 볼 수 있습니다. 아래 코드를 참고하세요.
def bubble_sort(arr, n): for i in range(n): ## 0부터 n-i-1까지 반복 (마지막 i개 요소는 이미 정렬됨) for j in range(n - i - 1): ## 다음 요소 확인 if arr[j] > arr[j + 1]: ## 인접한 요소 교환 arr[j], arr[j + 1] = arr[j + 1], arr[j] if __name__ == '__main__': ## 배열 초기화 arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] bubble_sort(arr, 9) ## 정렬된 배열 출력 print(str(arr))
병합 정렬
병합 정렬은 재귀적으로 작동하는 정렬 알고리즘입니다. 이전에 살펴본 알고리즘들보다 시간 복잡도 측면에서 효율적이며, 분할 정복 방식을 사용합니다.
병합 정렬 알고리즘은 배열을 반으로 나누고 각 부분을 재귀적으로 정렬합니다. 정렬된 하위 배열들을 병합하여 하나의 정렬된 배열을 만듭니다.
재귀 알고리즘이기 때문에, 배열이 더 이상 나눌 수 없을 때 (즉, 하나의 요소만 남을 때) 까지 분할 과정을 반복합니다.
다음 그림들을 보면서 병합 정렬의 동작 방식을 이해해 보세요.
병합 정렬 구현 단계를 자세히 알아봅시다.
- 정수형 더미 데이터로 배열을 초기화합니다.
- 하위 배열을 정렬된 하나의 배열로 병합하는 'merge' 함수를 작성합니다. 이 함수는 배열, 왼쪽 인덱스, 중간 인덱스, 오른쪽 인덱스를 인수로 받습니다.
- 주어진 인덱스를 사용하여 왼쪽 및 오른쪽 하위 배열의 길이를 구합니다.
- 원래 배열의 요소들을 각각 왼쪽 및 오른쪽 하위 배열로 복사합니다.
- 두 개의 하위 배열을 순회합니다.
- 두 하위 배열의 요소를 비교합니다.
- 정렬을 위해 두 하위 배열에서 더 작은 요소를 원래 배열에 복사합니다.
- 두 하위 배열에 아직 처리하지 않은 요소가 있는지 확인합니다.
- 남은 요소를 배열에 추가합니다.
- 배열, 왼쪽 인덱스, 오른쪽 인덱스를 인수로 받는 'merge_sort' 함수를 작성합니다.
- 왼쪽 인덱스가 오른쪽 인덱스보다 크거나 같으면 함수를 종료합니다.
- 배열의 중간 지점을 찾아 배열을 두 부분으로 나눕니다.
- 왼쪽, 오른쪽, 중간 인덱스를 사용하여 'merge_sort' 함수를 재귀적으로 호출합니다.
- 재귀 호출이 끝난 후 'merge' 함수를 사용하여 배열을 병합합니다.
병합 정렬의 시간 복잡도는 O(n log n)이고, 공간 복잡도는 O(n)입니다.
병합 정렬 알고리즘 구현은 다음과 같습니다. 아래 코드를 참고하세요.
def merge(arr, left_index, mid_index, right_index): ## 왼쪽 및 오른쪽 하위 배열 생성 left_array = arr[left_index:mid_index+1] right_array = arr[mid_index+1:right_index+1] ## 왼쪽 및 오른쪽 하위 배열 길이 계산 left_array_length = mid_index - left_index + 1 right_array_length = right_index - mid_index ## 두 배열 병합을 위한 인덱스 초기화 i = j = 0 ## 배열 요소 교체를 위한 인덱스 초기화 k = left_index ## 두 하위 배열 순회 while i < left_array_length and j < right_array_length: ## 왼쪽 및 오른쪽 배열의 요소 비교 if left_array[i] < right_array[j]: arr[k] = left_array[i] i += 1 else: arr[k] = right_array[j] j += 1 k += 1 ## 왼쪽 및 오른쪽 배열의 남은 요소 추가 while i < left_array_length: arr[k] = left_array[i] i += 1 k += 1 while j < right_array_length: j += 1 k += 1 def merge_sort(arr, left_index, right_index): ## 재귀 함수 종료 조건 if left_index >= right_index: return ## 중간 인덱스 찾기 mid_index = (left_index + right_index) // 2 ## 재귀 호출 merge_sort(arr, left_index, mid_index) merge_sort(arr, mid_index + 1, right_index) ## 두 하위 배열 병합 merge(arr, left_index, mid_index, right_index) if __name__ == '__main__': ## 배열 초기화 arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] merge_sort(arr, 0, 8) ## 정렬된 배열 출력 print(str(arr))
결론
여기에서 소개한 정렬 알고리즘 외에도 다양한 정렬 알고리즘이 존재합니다. 이 글을 통해 정렬 알고리즘에 대한 이해가 깊어지셨기를 바랍니다.
다음에는 검색 알고리즘에 대해 알아보겠습니다.
즐거운 코딩하세요! 🙂 👨💻