선택 정렬 알고리즘

선택정렬

정렬되지 않은 배열이 주어졌을 때 오름차순으로 선택정렬해보자.

 

arr[] = 5 | 4 | 6 | 8 | 2 | 3 | 1 | 7 | 9 | 0

의 배열을 선택정렬을 사용해 오름차순으로 정렬하고자 한다.

 

값을 swap할 기준 인덱스를 맨 처음 값 arr[0]=5로 잡는다.

그리고 값을 비교할 비교 인덱스를 arr[1]=4로 잡는다.

4와 다음 6,8,2 .. 를 비교하면서 가장 작은 비교 인덱스 값을 기준 인덱스와 swap한다.

6,8은 4보다 크니 지나가고, 2와 비교했을 때 2가 더 작으므로 비교 인덱스는 arr[3]=2로 바뀐다.

이제 2와 3을 비교, 1을 비교했을 때 1이 더 작으므로 비교 인덱스는 arr[5]=1로 바뀐다.

비교 인덱스의 변화는 4-> 2-> 1->0 순으로 변하고 0을 마지막으로 기준 인덱스와 swap한다.

 

arr[] = 0 | 4 | 6 | 8 | 2 | 3 | 1 | 7 | 9 | 5

 

다시 기준 인덱스를 arr[1]=4로 잡고, 비교 인덱스를 arr[2]=6으로 설정.

비교 인덱스의 변화는 6->2->1 이고, 5까지 비교한 후 1과 4를 swap한다.

 

arr[] = 0 | 1 | 6 | 8 | 2 | 3 | 4 | 7 | 9 | 5

 

다시 기준 인덱스는 arr[2]=6, 비교 인덱스는 arr[3]=8.

비교 인덱스의 변화는 8->2. 5까지 비교한 후 6과 2를 swap한다.

 

arr[] = 0 | 1 | 2 | 8 | 6 | 3 | 4 | 7 | 9 | 5

 

다시 기준 인덱스는 arr[3]=8, 비교 인덱스는 arr[4]=6.

비교 인덱스의 변화는 6->3. 5까지 비교한 후 8과 3을 swap.

 

arr[] = 0 | 1 | 2 | 3 | 6 | 8 | 4 | 7 | 9 | 5

 

기준 인덱스 arr[4]=6, 비교 인덱스 arr[5]=8

비교 인덱스 변화 8->4, 5까지 비교한 후 6과 4 swap.

 

arr[] = 0 | 1 | 2 | 3 | 4 | 8 | 6 | 7 | 9 | 5

 

기준 인덱스 arr[5]=8,비교 인덱스 arr[6]=6

비교 인덱스 변화 6->5, 8과 5 swap.

 

arr[] = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 9 | 8

 

기준 인덱스 arr[6]=6. 비교 인덱스의 변화 없으므로 skip

 

기준 인덱스 arr[7]=7. 비교 인덱스 변화 없으므로 skip

 

기준 인덱스 arr[8]=9. 비교 인덱스 8과 비교했을 때 더 크므로 swap.

 

arr[] = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

arr = [5, 4, 6, 8, 2, 3, 1, 7, 9, 0]

def sel_sort(arr):
    n = len(arr)
    for i in range(n):
        st_idx = i
        for j in range(i+1,n):
            if arr[j] < arr[st_idx]:
                st_idx = j
        arr[i],arr[st_idx] = arr[st_idx],arr[i]
        print(arr[:i+1])


print("before: ",arr)
sel_sort(arr)
print("after: ",arr)