선택 정렬(selection sort)

eunseo kim 👩‍💻·2021년 1월 4일
0

✨알고리즘 기본

목록 보기
5/10

📌 선택 정렬

  • 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 그 위치에 어떤 원소를 넣을지 선택하는 알고리즘이다.
  • 다음과 같은 순서를 반복하며 정렬하는 알고리즘이다.
    1. 주어진 데이터 중, 최소값을 찾음
    2. 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
    3. 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함



📌 선택 정렬 구현하기

문제 해결

  1. for stand in range(len(data) - 1) 로 반복
    • 맨 끝 원소는 마지막에 자동으로 정해진다. 왜냐하면 해당 알고리즘은 맨 앞부터 차례대로 정렬을 완성해나가는 알고리즘이기 때문이다.
  2. lowest = stand 로 놓고,
  3. for num in range(stand + 1, len(data)) (stand 이후부터 반복)
    • 내부 반복문 안에서 data[lowest] > data[num] 이면,
      • lowest = num
  4. data[num], data[lowest] = data[lowest], data[num]

✅ Code

def selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for index in range(stand + 1, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[stand] = data[stand], data[lowest]
    return data

📌 선택 정렬 시간복잡도

  • 반복문이 두 개 O(n2n^2)
    • 실제로 상세하게 계산하면, n(n1)2\frac { n * (n - 1)}{ 2 }
profile
열심히💨 (알고리즘 블로그)

0개의 댓글