Python 알고리즘

Python의 선택 정렬(selection sort)

이 레슨에서는 매번 가장 작은 요소를 찾아 제자리에 놓는 선택 정렬을 구현합니다.

  • 중급
  • 2분 분량
  • 실행 가능한 예제 1개

소개

어떤 문제를 해결하나요

항목 하나를 옮기는 비용이 클 때는 옮기는 횟수가 중요합니다. 그래서 어떤 정렬 알고리즘은 옮기는 횟수를 최대한 줄이려고 합니다. 선택 정렬(selection sort)은 버블 정렬과 다른 전략을 씁니다. 알맞은 항목을 먼저 찾아 놓고, 딱 한 번만 옮깁니다.

일상 속 비유

선택 정렬은 키 순서로 팀원을 뽑는 것과 같습니다. 아직 기다리고 있는 사람을 모두 훑어보고, 키가 가장 작은 사람을 불러 줄의 다음 자리에 세웁니다. 그런 다음 남은 사람들을 다시 훑어 그다음으로 작은 사람을 찾습니다. 아무도 남지 않을 때까지 이렇게 합니다.

팀원 뽑기에서 코드로
for start in range(len(result)):📍 줄에서 다음에 채울 빈자리
minimum = start🤔 일단 이 사람이 가장 작다고 가정
result[index] < result[minimum]🔎 나머지 중에 더 작은 사람이 있는지 찾기
result[start], result[minimum] = ...🔄 가장 작은 사람을 빈자리로 옮기기
정렬되지 않은 부분을 다 훑은 뒤, 자리 하나에 한 번만 바꿉니다.
한 문장으로

선택 정렬은 리스트의 정렬되지 않은 부분에서 가장 작은 항목을 찾아, 정렬된 부분의 바로 다음 자리에 있는 항목과 맞바꾸는 일을 반복합니다. 비교는 O(n²) 번 하지만 자리 바꾸기는 많아야 n - 1 번입니다.

핵심 포인트

  1. start의 왼쪽은 모두 이미 정렬되어 있고, start부터는 아직 정렬되지 않았습니다.
  2. minimum은 정렬되지 않은 부분에서 지금까지 찾은 가장 작은 값의 인덱스를 기억합니다.
  3. 안쪽 반복문 for index in range(start + 1, len(result)):은 리스트의 나머지 부분을 훑습니다.
  4. result[start], result[minimum] = result[minimum], result[start]는 자리 하나에 한 번만 값을 맞바꿉니다.

언제 사용하나요?

  • 여러 정렬 전략을 배우고 서로 비교할 때.
  • 항목을 쓰거나 옮기는 비용은 크고 비교하는 비용은 작은 경우.
  • 가장 작은 항목 k 개만 찾을 때. k 번만 훑고 멈추면 됩니다.

필요 없는 경우

  • 실제 프로그램: sorted()가 훨씬 빠릅니다.
  • 거의 정렬된 데이터: 선택 정렬은 그래도 전부 훑지만, 삽입 정렬은 금방 끝납니다.

Python의 선택 정렬(selection sort) 시각화

O(n²)

재생 또는 한 단계를 눌러 비교와 데이터 이동 과정을 확인하세요.

예제 코드

코드 실행 →
main.py
def selection_sort(values):
    result = values.copy()
    for start in range(len(result)):
        minimum = start
        for index in range(start + 1, len(result)):
            if result[index] < result[minimum]:
                minimum = index
        result[start], result[minimum] = result[minimum], result[start]
    return result

print(selection_sort([64, 25, 12, 22, 11]))
이 예제의 실행 버튼 만들기

실행 결과

[11, 12, 22, 25, 64]

코드 설명

변수 minimum은 나머지 리스트에서 가장 작은 값의 위치를 기억합니다. 한 번 훑기가 끝나면 그 값을 start 위치의 값과 맞바꿉니다. 비교 횟수가 많아 복잡도는 항상 O(n²)이지만, 교환은 많아야 n번만 합니다.

값을 변경하고 Python 설치 없이 CodeUtility 온라인 Python 컴파일러에서 실행하세요.

연습 문제

아래 제안을 따라 코드를 바꿔 보세요. 코드를 직접 고치고 결과를 확인하면 읽기만 할 때보다 레슨을 훨씬 잘 이해할 수 있습니다.

  1. 빈 리스트, 요소가 하나인 리스트, 중복이 있는 리스트로 테스트해 보세요.
  2. 단계마다 상태를 출력해서 알고리즘이 동작하는 모습을 살펴보세요.
  3. 요소 100개, 1,000개, 10,000개로 실행 시간을 재고 다른 방법과 비교해 보세요.
Python 컴파일러에서 실행 →

자주 하는 실수

안쪽 반복문 안에서 자리 바꾸기

자리를 여러 번 바꾸게 되어 더 느리고 지저분한 정렬이 됩니다.

문제
for index in range(start + 1, len(result)):
    if result[index] < result[start]:
        result[start], result[index] = result[index], result[start]
수정
for index in range(start + 1, len(result)):
    if result[index] < result[minimum]:
        minimum = index
result[start], result[minimum] = result[minimum], result[start]

이 레슨을 마쳤나요?

학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지