제로베이스 데이터사이언스 스쿨 - Part 05. 자료구조&알고리즘 with Python -27

Chapter 03. 알고리즘

선택 정렬(Selection Sort)

개념 정리

선택 정렬은 리스트에서 가장 작은(또는 가장 큰) 값을 찾아 현재 위치의 값과 교환하는 방식의 정렬 알고리즘이다. 전체 데이터 중에서 기준이 되는 위치를 하나씩 확정해 나가며, 그 위치에 들어가야 할 최솟값을 선택한다는 점에서 선택 정렬이라는 이름이 붙었다.

정렬 과정은 다음과 같은 흐름으로 반복된다.

1. 전체 데이터 중에서 최솟값을 찾는다.
2. 해당 값을 맨 앞의 값과 교환한다.
3. 정렬이 완료된 첫 번째 값을 제외한 나머지 데이터에서 다시 최솟값을 찾는다.
4. 이 과정을 리스트의 끝까지 반복한다.

이 방식은 비교 횟수는 많지만 교환 횟수는 적은 편이라는 특징을 가진다.

---

알고리즘 동작 방식

예를 들어 점수 리스트가 다음과 같다고 가정해보자.

[70, 85, 60, 90, 75]

1단계에서는 전체에서 가장 작은 값인 60을 찾아 첫 번째 위치의 70과 교환한다.

[60, 85, 70, 90, 75]

2단계에서는 두 번째 위치부터 다시 최솟값을 찾는다. 70이 선택되어 85와 교환된다.

[60, 70, 85, 90, 75]

이 과정을 반복하면 최종적으로 오름차순 정렬이 완성된다.

---

파이썬 구현 예시

def selection_sort(scores, reverse=False):
    n = len(scores)
    for i in range(n - 1):
        idx = i
        for j in range(i + 1, n):
            if (scores[j] < scores[idx] and not reverse) or \
               (scores[j] > scores[idx] and reverse):
                idx = j
        scores[i], scores[idx] = scores[idx], scores[i]
    return scores

scores = [70, 85, 60, 90, 75]
print(selection_sort(scores))
print(selection_sort(scores, reverse=True))

위 코드에서는 reverse 옵션을 통해 오름차순과 내림차순 정렬을 모두 처리할 수 있도록 구성했다.

---

시간 복잡도 특징

선택 정렬은 데이터의 상태와 무관하게 항상 동일한 비교 횟수를 수행한다.

• 시간 복잡도: O(n²)
• 공간 복잡도: O(1) (제자리 정렬)

데이터 개수가 많아질수록 성능이 급격히 저하되기 때문에, 실무에서 대규모 데이터 정렬에는 잘 사용되지 않는다.

 

 

* 이 글은 제로베이스 데이터사이언스 파트타임 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다.

---

 

💡 생각 정리

선택 정렬은 구현 자체는 단순하지만, 실제로 손으로 과정을 따라가 보지 않으면 동작 원리를 제대로 이해하기 어렵다는 점이 인상적이었다. 특히 매 반복마다 "현재 위치에 들어갈 값은 이미 확정된다"는 개념이 정렬 흐름을 이해하는 핵심이라는 것을 실습을 통해 체감할 수 있었다. 연습문제를 풀면서 단순히 결과만 맞추는 것이 아니라, 인덱스가 어떻게 이동하고 최소값 기준이 어떻게 바뀌는지를 추적하는 것이 알고리즘 이해에 훨씬 도움이 된다는 점을 느꼈다.

---

🚀 적용점

• 정렬 알고리즘을 처음 학습할 때 기본 개념용 예제로 매우 적합하다.
• 교환 횟수가 적기 때문에 데이터 이동 비용이 큰 환경에서는 개념적으로 참고할 수 있다.
• 이후 버블 정렬, 삽입 정렬과 비교하면서 알고리즘별 차이를 이해하는 기준점으로 활용할 수 있다.
• 코딩 테스트 대비보다는 알고리즘 사고 방식 훈련용으로 복습하면 효과적이다.