[선택 정렬] Selection sort - python

출처:https://ko.wikipedia.org/wiki/%EC%84%A0%ED%83%9D_%EC%A0%95%EB%A0%AC

Selection Sort

---

시간복잡도: 

선택 정렬(selection sort)은 in-place 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

1. 주어진 리스트 중 최솟값을 찾는다

2. 그값을 맨 앞에 위치한 값과 교체한다.

3. 맨 처음 위치를 뺀 나머지를 같은 방법으로 교체한다.

9 1 6 8 4 3 2 0

을 그림으로 표현해 보았당.

def selection_sort(a):
    for i in range(len(a)-1):
        min_index = i
        for j in range(i+1, len(a)):
            if a[min_index] > a[j]:
                min_index = j
        a[i], a[min_index] = a[min_index], a[i]
    return a
 
a = [9,1,6,8,4,3,2,0]
 
print(selection_sort(a))

[9, 1, 6, 8, 4, 3, 2, 0]

min: 0

after: [9, 1, 6, 8, 4, 3, 2, 0]

min: 1

after: [0, 1, 6, 8, 4, 3, 2, 9]

min: 2

after: [0, 1, 6, 8, 4, 3, 2, 9]

min: 3

after: [0, 1, 2, 8, 4, 3, 6, 9]

min: 4

after: [0, 1, 2, 3, 4, 8, 6, 9]

min: 6

after: [0, 1, 2, 3, 4, 8, 6, 9]

min: 8

after: [0, 1, 2, 3, 4, 6, 8, 9]

[0, 1, 2, 3, 4, 6, 8, 9]