파이썬 선택 정렬은 하나의 리스트를 두 개의 부분 리스트로 나누는 방식으로 작동합니다. 하나는 정렬된 요소들을 담은 리스트이고, 다른 하나는 아직 정렬되지 않은 요소들을 담은 리스트입니다. 선택 정렬은 매 반복마다 가장 작은 값(또는 가장 큰 값)을 찾아 정렬된 리스트 쪽으로 옮깁니다.
리스트 정렬은 다양한 프로그램에서 자주 사용되는 기본적인 연산입니다.
예를 들어 보겠습니다. 어떤 선생님이 학생들의 최근 시험 성적을 분석하고 싶어 한다고 가정해 봅시다. 선생님은 학생들의 점수를 오름차순 또는 내림차순으로 정렬하면 최고 점수와 최저 점수를 손쉽게 파악할 수 있습니다.
바로 이럴 때 선택 정렬(selection sort)이 유용합니다. 선택 정렬은 리스트를 오름차순이나 내림차순으로 정렬할 수 있는 알고리즘입니다.
이 글에서는 파이썬으로 선택 정렬 프로그램을 작성하는 방법을 단계별로 살펴봅니다. 전체 과정을 예제와 함께 진행하므로, 글을 끝까지 읽으면 선택 정렬의 모든 동작 원리를 이해할 수 있을 것입니다.
파이썬 선택 정렬이란?
파이썬 선택 정렬은 리스트에서 최솟값을 반복적으로 찾아 리스트의 특정 끝부분으로 이동시키는 알고리즘입니다. 배열 전체가 정렬될 때까지 이 과정을 계속합니다. 필요에 따라 최댓값을 찾도록 설정할 수도 있으며, 두 방식 모두 리스트를 정렬하는 결과를 가져옵니다.
선택 정렬은 처음에 리스트의 첫 번째 요소가 가장 작은 값이라고 가정합니다. 그다음 이 값을 두 번째 요소와 비교하는데, 만약 두 번째 요소가 더 작다면 해당 요소가 새로운 최솟값이 됩니다.
이 과정을 리스트의 마지막 요소까지 반복합니다. 마지막 요소에 도달하면 찾은 최솟값을 정렬되지 않은 리스트의 맨 앞으로 이동시킵니다.
선택 정렬 예제로 배우기
선택 정렬을 익히는 가장 좋은 방법은 직접 예제를 따라 해보는 것입니다. 학생 성적 리스트를 오름차순으로 정렬해 보겠습니다. 다음은 정렬되지 않은 초기 리스트입니다:
| 73 | 62 | 61 | 69 |
먼저 리스트의 첫 번째 값을 최솟값(minimum)으로 지정합니다. 선택 정렬의 각 반복 단계에서는 가장 작은 요소를 찾아 정렬된 부분 배열로 옮기게 됩니다.
최솟값을 기준으로 정렬하는 것은 여러 방법 중 하나일 뿐입니다. 최댓값을 기준으로 정렬해도 선택 정렬은 잘 작동하지만, 이 예제에서는 최솟값 방식을 사용하겠습니다.
다음으로 최솟값을 두 번째 요소와 비교합니다. 만약 두 번째 요소가 현재 최솟값보다 작다면, 그 요소가 새로운 최솟값이 됩니다.
73과 62를 비교해 봅시다. 73이 62보다 크므로 새로운 최솟값은 62입니다. 이제 리스트의 나머지 숫자들도 차례대로 확인합니다:
- 61이 62(현재 최솟값)보다 작은가? 네, 그러므로 최솟값을 61로 변경합니다.
- 69가 61(현재 최솟값)보다 작은가? 아니요, 아무 작업도 하지 않습니다. 최솟값은 61로 유지됩니다.
아직 리스트의 순서는 그대로입니다:
| 73 | 62 | 61 | 69 |
리스트의 끝에 도달하면 최솟값을 리스트의 맨 앞으로 이동시킵니다:
| 61 | 73 | 62 | 69 |
61(최솟값)이 리스트 맨 앞으로 이동했고, 나머지 값들은 각각 한 칸씩 밀려났습니다. 이 과정을 모든 요소가 정렬될 때까지 반복합니다.
각 반복 단계마다 리스트는 다음과 같이 변화합니다:
- 73, 62, 61, 69
- 61, 73, 62, 69
- 61, 62, 73, 69
- 61, 62, 69, 73
선택 정렬이 리스트의 모든 요소를 확인하면 정렬이 종료됩니다.
여기서 흥미로운 점은, 정렬된 부분 배열과 정렬되지 않은 부분 배열이 눈에 보이지 않는다는 것입니다. 알고리즘이 내부적으로 배열을 정렬하면서 정렬되지 않은 영역을 스스로 관리하기 때문입니다.
파이썬으로 선택 정렬 구현하기
이제 이론은 충분히 익혔습니다! 이제 본격적으로 파이썬으로 선택 정렬 알고리즘을 구현해 보겠습니다. 파이썬 배열을 입력받아 오름차순으로 정렬하는 프로그램을 작성해 보겠습니다.
1단계: 정렬 함수 정의하기
먼저 선택 정렬을 수행하는 파이썬 함수를 정의합니다:
def sortList(array): length = len(array) for item in range(length): minimum = item for i in range(item + 1, length): if array[i] < array[minimum]: minimum = i (array[item], array[minimum]) = (array[minimum], array[item])
먼저 파이썬의 len() 메서드를 사용해 리스트의 길이를 구했습니다. 그런 다음 이 값을 활용해 리스트의 모든 항목을 순회하는 for 반복문을 시작합니다.
반복문의 각 단계에서는 minimum 변수를 현재 위치의 첫 번째 항목으로 설정합니다. 앞서 예제에서 살펴본 것과 동일한 과정입니다. 최솟값을 지정한 후에는 또 다른 for 반복문이 시작되어 리스트의 모든 항목을 훑으며 검사합니다.
리스트의 각 항목에 대해 알고리즘은 현재 최솟값이 해당 항목보다 큰지 확인합니다. 최솟값이 더 크면 아무 일도 일어나지 않고, 그렇지 않으면 minimum 값이 현재 읽고 있는 항목의 인덱스로 갱신됩니다.
내부 반복문이 리스트의 모든 항목을 순회하면, 알고리즘은 최솟값을 리스트의 맨 앞으로 이동시킵니다. 그런 다음 바깥쪽 for 반복문이 종료될 때까지 이 과정을 계속합니다. 선택 정렬은 리스트의 길이만큼 반복 실행되기 때문입니다.
2단계: 정렬 함수 호출하기
프로그램을 지금 상태로 실행하면 아무 결과도 출력되지 않습니다. 아직 코드에 어떤 값을 정렬해야 하는지 알려주지 않았기 때문입니다. 프로그램 마지막에, 즉 sortList 함수 외부에 다음 코드를 추가하세요:
numbers = [73, 62, 61, 69]
sortList(numbers)
print("Sorted list:", numbers)
프로그램을 실행하면 다음과 같은 결과가 출력됩니다:
[61, 62, 69, 73]
리스트가 성공적으로 정렬되었습니다. 직접 해내셨으니 스스로에게 박수를 보내도 좋습니다!
선택 정렬은 내림차순 정렬에도 활용할 수 있습니다. 내림차순으로 정렬하고 싶다면 선택 정렬 코드의 "if" 조건문을 다음과 같이 변경하면 됩니다:
if array[i] > array[minimum]:
작-than 부호(<)를 큰-than 부호(>)로 바꿨습니다. 이렇게 하면 '최솟값'이 사실상 리스트에서 가장 큰 값으로 설정되므로 리스트가 내림차순으로 정렬됩니다. 엄밀히 말하면 minimum 변수가 maximum 역할을 하게 되는 것입니다.
선택 정렬은 언제 사용해야 할까?
선택 정렬은 버블 정렬과 마찬가지로 규모가 작은 리스트에 적합합니다. 리스트가 클 경우 삽입 정렬 같은 다른 알고리즘만큼 효율적이지 않기 때문입니다.
반면, 정렬 알고리즘을 처음 배우는 단계라면 선택 정렬은 훌륭한 출발점입니다. 다른 정렬 알고리즘은 익히기 어려울 수 있지만, 선택 정렬을 확실히 이해하면 다양한 유형의 리스트 정렬 방식을 이해하는 데 큰 도움이 됩니다.
선택 정렬의 시간 복잡도는?
선택 정렬의 시간 복잡도는 O(n²)입니다. 이는 알고리즘의 복잡도가 리스트에 포함된 요소 수에 따라 기하급수적으로 증가한다는 의미입니다.
O(n²)는 이 알고리즘의 최악의 경우, 평균, 최선의 경우 모두에 해당하는 복잡도입니다. 정렬 알고리즘의 복잡도에 대해 더 깊이 알고 싶다면 빅오 표기법(Big O Notation) 관련 자료를 참고해 보세요.
마무리
선택 정렬은 데이터를 정렬하는 중요한 방법 중 하나입니다. 선택 정렬은 리스트의 모든 항목을 읽으면서, 각 반복마다 가장 작은 항목을 리스트의 맨 앞으로 이동시킵니다. 이 과정은 리스트의 모든 항목을 읽을 때까지 계속됩니다.
선택 정렬은 더 효율적인 알고리즘이 존재하기 때문에 교육 목적 외에는 널리 사용되지 않습니다. 그럼에도 불구하고 선택 정렬은 삽입 정렬이나 병합 정렬 같은 다른 정렬 알고리즘을 학습하기 위한 훌륭한 디딤돌이 됩니다.
파이썬 학습에 더 관심이 있으신가요? 체계적으로 실력을 향상시키는 데 도움이 되는 파이썬 학습 로드맵 가이드도 함께 확인해 보세요.