목차
1. 선택 정렬 알고리즘이란?
선택 정렬 알고리즘은 배열을 정렬하는 데 사용되는 간단한 정렬 방법입니다.
2. 선택 정렬 동작 원리
선택 정렬은 배열에서 최솟값을 찾아 순차적으로 정렬하는 방식입니다.
3. 선택 정렬의 장단점
선택 정렬의 장단점에 대한 설명입니다.
장점
- 간단한 구현: 선택 정렬은 구현이 간단하고 이해하기 쉬우며 기본적인 반복문과 조건문만으로도 구현 가능
- 공간 복잡도: 선택 정렬은 입력 배열 안에서 정렬을 수행하므로 별도의 추가 메모리 공간이 필요없음
- 불안정 정렬 방식: 선택 정렬은 값이 같은 요소의 순서를 보장하지 않으므로, 원래 순서가 중요하지 않은 경우에 적합
단점
- 비효율적인 시간 복잡도: 선택 정렬의 시간 복잡도는 항상 O(n^2)으로 매우 비효율적
- 불안정한 정렬: 선택 정렬은 값이 같은 레코드의 순서를 보장하지 않음
- 비교 횟수의 한계: 선택 정렬은 매번 최솟값을 찾아서 정렬하기 때문에 비교 횟수가 상당히 많음
- 데이터의 이동: 선택 정렬은 정렬 중에 데이터의 이동이 빈번하게 발생
4. 선택 정렬 예제 코드
아래는 함수의 인자로 값이 저장되어있는 배열을 전달하면 선택 정렬해주는 예제입니다.
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
5. 배열 정렬 예제
선택 정렬을 사용하여 배열을 정렬하는 예제 코드입니다.
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if arr[j] < arr[min_index]:
min_index = j
arr[i], arr[min_index] = arr[min_index], arr[i]
arr = [64, 34, 25, 12, 22, 11, 90]
selection_sort(arr)
print("정렬된 배열:", arr)
6. 최솟값 찾기 예제
선택 정렬을 활용하여 배열에서 최솟값을 찾는 예제 코드입니다.
def find_min(arr):
min_val = arr[0]
for num in arr:
if num < min_val:
min_val = num
return min_val
arr = [64, 34, 25, 12, 22, 11, 90]
print("가장 작은 값: %d" % find_min(arr))
7. 문자열 정렬 예제
선택 정렬을 활용하여 문자열을 정렬하는 예제 코드입니다.
def string_selection_sort(strings):
str_list = list(strings)
for i in range(len(str_list)):
min_index = i
for j in range(i + 1, len(str_list)):
if str_list[j] < str_list[min_index]:
min_index = j
str_list[i], str_list[min_index] = str_list[min_index], str_list[i]
return ''.join(str_list)
test_str = "hello world"
test_str = string_selection_sort(test_str)
print(test_str)
반응형