
안녕하세요. 성조입니다.
단순 선택 정렬(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)이다.
오타나 궁금한 부분이 있다면 언제든지 댓글 남겨주세요.
다음 포스팅 때 뵙겠습니다.
'Algorithm' 카테고리의 다른 글
| [Algorithm] 버블 정렬(Bubble Sort) (with Python) (0) | 2023.01.09 |
|---|---|
| [Data Structures] 큐(Queue) (with. a little deep dive and Java) (0) | 2022.04.17 |
| [Data Structures] 자료구조(Data Structure)란? (0) | 2022.04.15 |
| [Algorithm] 알고리즘(Algorithm)이란? (0) | 2020.06.14 |