[Algorithm] 단순 선택 정렬(Simple Selection Sort) (with Python)

안녕하세요. 성조입니다.

단순 선택 정렬(Simple Selection Sort)로 소개되는 정렬 알고리즘을 정리해 보려 합니다.

---

단순 선택 정렬이란?

단순 선택 정렬은 기본 동작 원리(탐색과 교환)를 기본으로 하며, 배열의 미정렬 부분에서 최솟값을 찾아 맨 앞의 원소와 교체하는 과정을 반복하며 정렬하는 알고리즘을 뜻한다.

 

선택 정렬의 성능

1) 시간 복잡도는(O(N^2))가 도출된다. (Time Complexity)

2) 데이터가 이미 정렬되어 있든, 역순으로 정렬되어 있든 무조건 전체를 탐색하며 최솟값을 찾아야 하므로 최선, 평균, 최악의 경우 모두 O(N^2)만큼 시간이 소요된다.

3) 공간 복잡도 (Space Complexity)

O(1) 주어진 배열 안에서 값들의 자리만 서로 바꾸므로(In-place Sort), 정렬을 제외한 추가적인 메모리 공간이 거의 필요하지 않는다.

 

 

동작 순서 원리

1. 주어진 데이터 배열에서 가장 작은 값(최소값)을 찾는다.

2. 그 최솟값을 배열의 맨 앞에 위치한 값과 자리를 바꾼다. (Swap).

3. 맨 앞자리는 정렬이 끝났으므로, 그 다음 자리부터 마지막 자리까지 배열을 대상으로 다시 최솟값을 찾아 두 번째 자리와 바꾼다.

4. 이 과정을 데이터가 모두 정렬될 때까지 처음부터 끝까지 완복하며 반복한다.

 

 

 

Python 코드

def selection_sort(arr):
    n = len(arr)
    
    # 배열의 처음부터 끝에서 두 번째 요소까지만 순회하면 됨.
    # (마지막 요소는 자동으로 정렬되기 때문)
    for i in range(n - 1):
        # 1. 현재 탐색 범위에서 가장 맨 앞의 인덱스를 최솟값 인덱스로 임시 지정.
        min_idx = i
        
        # 2. i의 다음 위치부터 배열 끝까지 돌면서 진짜 최솟값을 찾는다.
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j  # 더 작은 값을 발견하면 인덱스를 갱신.
                
        # 3. 안쪽 반복문이 끝나면 가장 작은 값의 인덱스(min_idx)를 찾은 상태.
        # 현재 기준 위치(i)의 값과 최솟값 위치(min_idx)의 값을 서로 바꿈 (Swap).
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        
        # 중간 과정 출력 (이해를 돕기 위함)
        print(f"{i+1}회전 결과: {arr}")
        
    return arr

# 테스트
sample_data = [64, 25, 12, 22, 11]
print("정렬 전:", sample_data)
print("-" * 30)
sorted_data = selection_sort(sample_data)
print("-" * 30)
print("정렬 후:", sorted_data)

 

 

장점과 단점 정리

장점

1. 원리가 단순하여 코드 구현이 매우 쉽다.

2. 추가적인 메모리 소비가 적다.(제자리에서 정렬하는 형식이라서)

3. 비교 횟수는 많지만, 실제로 값을 교환(Swap)하는 횟수는 적어 교환 비용이 큰 상황에서는 버블 정렬보다 나은 성능을 보인다.

 

 

단점

1. 시간 복잡도가 O(N^2)이라 데이터가 많아질수록 효율이 급격히 떨어지는 문제가 있다.

2. 값이 같은 두 데이터의 상대적인 위치가 정렬 후 바뀔 수 있는 불안정 정렬(Unstable Sort)이다.

 
 

---

오타나 궁금한 부분이 있다면 언제든지 댓글 남겨주세요.

다음 포스팅 때 뵙겠습니다.