All Articles

알고리즘 - 선택 정렬(Selection sort)

선택 정렬(Selection sort)이란

주어진 데이터 중 최소값을 찾아서 맨 앞에 있는 값과 위치를 바꾼다. 맨 앞 값과 바꿔준 최소값을 제외한 나머지 데이터에서 최소값을 찾아 그 다음 앞(두 번째 턴이라면 1번 인덱스 값)에 있는 값과 위치를 바꾼다. 바꿀 요소가 없을 때까지 반복한다.

선택 정렬 예시

요소가 4개일 때

nums = [2, 4, 1, 3]

  1. 0번 인덱스를 기준으로 1~3번 인덱스와 값 비교
  2. 2, 4 비교
  3. 2, 1 비교
  4. 1, 3 비교
  5. 1이 최소값이므로 2와 자리 바꿈 [1, 4, 2, 3] - 1턴 완료
  6. 1번 인덱스를 기준으로 2~3번 인덱스와 값 비교
  7. 4, 2 비교
  8. 2, 3 비교
  9. 2가 최소값이므로 4와 자리 바꿈 [1, 2, 4, 3] - 2턴 완료
  10. 2번 인덱스를 기준으로 3번 인덱스와 값 비교
  11. 4, 3 비교
  12. 3이 최소값이므로 4와 자리 바꿈 [1, 2, 3, 4] - 3턴 완료

요소가 5개일 때

nums = [7, 3, 2, 4, 1]

  1. 0번 인덱스를 기준으로 1~4번 인덱스와 값 비교
  2. 7, 3 비교
  3. 3, 2 비교
  4. 2, 4 비교
  5. 2, 1 비교
  6. 1이 최소값이므로 7과 자리 바꿈 [1, 3, 2, 4, 7] - 1턴 완료
  7. 1번 인덱스를 기준으로 2~4번 인덱스와 값 비교
  8. 3, 2 비교
  9. 2, 4 비교
  10. 2, 7 비교
  11. 2가 최소값이므로 3과 자리 바꿈 [1, 2, 3, 4, 7] - 2턴 완료
  12. 2번 인덱스를 기준으로 3~4번 인덱스와 값 비교
  13. 3, 4 비교
  14. 3, 7 비교
  15. 3이 최소값이자 기준값이므로 자리 바꿈 없음 [1, 2, 3, 4, 7] - 3턴 완료
  16. 3번 인덱스를 기준으로 4번 인덱스와 값 비교
  17. 4, 7 비교
  18. 4가 최소값이자 기준값이므로 자리 바꿈 없음 [1, 2, 3, 4, 7] - 4턴 완료

귀납적 판단

  • 기준 인덱스 번호는 0부터 데이터 전체 길이에서 1 뺀 값까지다.
  • 기준 인덱스와 비교할 나머지 인덱스 범위는 기준 인덱스에 1 더한 값부터 데이터 전체 길이까지다.
  • 기준 인덱스로 비교를 시작하지만 중간에 더 작은 값이 있으면 비교 기준을 바꿔준다.

버블 정렬 알고리즘 시나리오

  1. 기준 인덱스 범위를 지정해 인덱스 값이 커지도록 반복문을 돌린다.
  2. 기준 값과 비교할 값의 인덱스 범위를 지정해 반복문을 돌린다.
  3. 이때 기준 값이 비교할 값보다 크다면 기준 값을 작은 값으로 바꿔준다.
  4. 2번 반복문을 다 돌리면 기준 값이 제일 작은 값이 되며, 그 값을 가장 앞에 있는 값과 바꿔준다.

코드 작성

def selectionsort(nums):
  for standard in range(len(nums)-1):
    lowest = standard
    for idx in range(standard+1, len(nums)):
      if nums[standard] > nums[idx]:
        standard = idx
    nums[lowest], nums[standard] = nums[standard], nums[lowest]
  return nums

검증

import random

# 0부터 99까지 숫자 중 50개를 무작위로 뽑아서 리스트 생성
nums = random.sample(range(100), 50)
print(selectionsort(nums))

복잡도

이중 for문이므로 O(n2)

기억해두기

기준 값 잡고 기준 값을 바꿔주는 방식

for standard in range(len(nums)-1):
    lowest = standard
    for idx in range(standard+1, len(nums)):
      if nums[standard] > nums[idx]:
        standard = idx

Published 21 Aug 2020