[Algorithm] 정렬 알고리즘_3(단순 선택 정렬)

06-3 단순 선택 정렬

단순 선택 정렬 알아보기

단순 선택 정렬(straight selection sort): 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘

단순 선택 정렬에서 교환 과정은 다음과 같습니다.

1. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택합니다.
2. a[min]과 아직 정렬하지 않은 부분에서 맨 앞에 있는 원소를 교환합니다.

이 과정을 n - 1번 반복하면 정렬하지 않은 부분이 없어지면서 정체 정렬을 완료합니다. 이 알고리즘의 개요는 다음과 같습니다.

for i in range(n - 1):
	min	# a[i], ···, a[n-1]에서 키값이 가장 작은 원소의 인덱스
    a[i]와 a[min]의 값을 교환합니다.

---

실습 6-6 단순 선택 정렬 알고리즘 구현하기

# 단순 선택 정렬 알고리즘 구현하기

from typing import MutableSequence

def selection_sort(a: MutableSequence) -> None:
  """단순 선택 정렬"""
  n = len(a)
  for i in range(n - 1):
    min = i       # 정렬한 부분에서 가장 작은 원소의 인덱스
    for j in range(i + 1, n):
      if a[j] < a[min]:
        min = j
    a[i], a[min] = a[min], a[i]   # 정렬한 부분에서 맨 앞의 원소와 가장 작은 원소를 교환

if __name__ == '__main__':
  print('단순 선택 정렬을 수행합니다.')
  num = int(input('원소 수를 입력하세요.: '))
  x = [None] * num    # 원소 수가 num인 배열을 생성

  for i in range(num):
    x[i] = int(input(f'x[{i}]: '))

  selection_sort(x)      # 배열 x를 버블 정렬

  print('오름차순으로 정렬했습니다.')
  for i in range(num):
    print(f'x[{i}] = {x[i]}')

단순 선택 정렬을 수행합니다.
원소 수를 입력하세요.: 7
x[0]: 6
x[1]: 4
x[2]: 8
x[3]: 3
x[4]: 1
x[5]: 9
x[6]: 7
오름차순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 7
x[5] = 8
x[6] = 9

 

단순 선택 정렬 알고리즘의 원솟값을 비교하는 횟수는 (n² - n) / 2번입니다.
하지만 이 알고리즘은 서로 이웃하지 않는 떨어져 있는 원소를 교환하므로 안정적이지 않습니다.

- 출처: Do it! 자료구조와 함께 배우는 알고리즘 입문 - 파이썬 편
- notebook ipynb file:
https://github.com/heejvely/Algorithm/blob/main/Do_it_algorithm/Do_it_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98_%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.ipynb

GitHub - heejvely/Algorithm: 파이썬 알고리즘 인터뷰 책을 참고한 파이썬 알고리즘 연습