정렬 알고리즘이란?
정렬 알고리즘은 데이터를 특정한 순서로 배열하는 프로세스입니다.
이 중 선택정렬은 그 구현의 단순성으로 인해 기초 컴퓨터 과학 교육에서 자주 다루어지는 알고리즘입니다.
이 게시글에서는 선택정렬의 메커니즘, 장단점, 그리고 코드 구현을 통해 이 알고리즘을 자세히 살펴보겠습니다.
다음 게시글에서는 선택정렬의 표현 방법을 보다 더 구체적이고 재귀, 반복문을 활용하여 각기 다른 방식으로 표현해보겠습니다.
선택정렬이란?
선택정렬은 배열의 각 위치를 차례로 확인하며, 해당 위치에 들어갈 가장 작은 (또는 가장 큰) 요소를 찾아 위치를 교환하는 방식으로 작동합니다. 이 과정은 배열이 정렬될 때까지 반복됩니다.
처음부터 끝까지 순회:
- 배열의 첫 번째 위치에서 시작하여 가장 작은 요소를 찾고, 그 요소를 첫 번째 위치의 요소와 교환합니다.
- 다음 위치로 이동하여 나머지 배열에서 가장 작은 요소를 찾고, 현재 위치의 요소와 교환합니다.
- 이 과정을 배열의 마지막 위치에 도달할 때까지 반복합니다.
다음은 직접 선택정렬을 시각화 하여 구현한 것 입니다. 이 시각화 코드는 다음 게시물에서 다루겠습니다.
코드 예시
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[min_idx] > arr[j]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
정렬 알고리즘 비교
| 정렬 알고리즘 | 최선 시간 복잡도 | 평균 시간 복잡도 | 최악 시간 복잡도 | 공간 메모리 | 추가 정보 |
| 선택정렬 | O(n2) | O(n2) | O(n2) | O(1) | 제자리 정렬(안전) 비교적 구현이 간단 |
| 삽입 정렬 | O(n) | O(n2) | O(2) | O(1) | 제자리 정렬(안전) 작은 데이터 세트나 거의 정렬된 데이터에 매우 효율적 |
| 버블 정렬 | O(n) | O(n2) | O(n2) | O(1) | 제자리 정렬, 매우 비효율적, 데이터가 거의 정렬된 상태에서 효율적 |
| 퀵 정렬 | O(nlogn) | O(nlogn) | O(n**2) | O(nlogN) | 공간 복잡도는 재귀 깊에 따라 달라짐, 평균적으로 가장 빠름 |
| 힙 정렬 | O(nlogn) | o(nlogn) | O(nlogn) | O(1) | 힙 구조를 사용, 데이터 크기에 따라 일정하게 빠름 |
| 병합 정렬 | O(nlogn) | O(nlogn) | O(nlogn) | O(nlogn) | 외부 메모리 사용, 대규모 데이터에 효율적, 안정 정렬 |
| 팀 정렬 | O(n) | O(nlogn) | O(nlogn) | O(n) | 하이브리드 알고리즘, 대규모 데이터에 매우 효과적, 매우 안정적인 정렬 |
비교적으로 선택정렬은 정렬 알고리즘 중에서 구현이 간단하지만 성능이 좋지 않음을 알 수 있습니다. 하지만 정렬 알고리즘을 이해하는데 있어 toy example의 대표입니다. 따라서 다음 게시물에서 선택정렬을 파이썬으로 보다 다양한 방법으로 표현하는데 참고하시면 다른 정렬들을 이해함에 있어 비교적 편리할 것 입니다.
'Data Structure' 카테고리의 다른 글
| 정렬 | 삽입정렬 | 특이 case에 적합한 정렬 (0) | 2025.01.23 |
|---|---|
| 누구나 구현 할 수 있는 알고리즘 II (0) | 2025.01.20 |
| 재귀 함수 III (2) | 2025.01.15 |
| 재귀 함수 II (0) | 2025.01.15 |
| 재귀 함수 I (0) | 2025.01.15 |