정렬 - 선택 정렬(selection sort)

1. 선택 정렬(selection sort) 란?

🖐 주어진 데이터 중 최소값을 찾아 맨 앞 값과 교체

🖐 맨 앞을 빼고 다시 반복 

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix) - VisuAlgo

 

2. 단순하게 생각하기

👉 최소값을 찾아라!

👉 앞부터 하나씩 결정된다!

 

3. 알고리즘 구현

✍ 데이터 갯수의 -1만큼 반복

✍ 가장 첫 자리를 lowest로 두고 시작

✍ 더 작은 숫자가 있다면 첫 자리와 바꾸기 -> 앞부터 채워나가기 !

def selection_sort(data):
    for t in range(len(data) - 1):
        lowest = t # 가장 처음부터
        for idx in range(t+1, len(data)):
            if data[lowest] > data[idx]: # 만약 더 작은 수가 있다면
                lowest = idx
        data[lowest], data[t] = data[t], data[lowest]  
        # 만약 더 작은수가 있었다면 여기서 lowest=가장 작은 수의idx -> 가장 작은 수를 앞에서부터 채워나감
    return data

selection_sort([9,7,5,3,1])
# 출력결과: [1,3,5,7,9]

 

4. 복잡도

👉 반복문이 두 개  O(n**2)

👉 상세하게 계산하면  n*(n-1) / 2