[정렬 알고리즘 / Python] 선택 정렬 | 초코더

정렬 알고리즘 개념을 뿌셔볼게요..

 

선택정렬(Selection Sort)

주어진 배열에서 최댓값(최솟값)을 찾아 맨 오른쪽(왼쪽)값과 교체한다. 최댓값을 맨 오른쪽으로 보낸다는 점에서 버블정렬과 비슷하지만, 이웃한 두 값을 정렬하는 과정이 없기 때문에 대체로 버블정렬보다 빠르다. 최댓값을 찾아야 하므로 정렬 상태에 관계없이 언제나 O(n2)이다.

 

def swap(x, i, j):
    x[i], x[j] = x[j], x[i]

def selectionSort(x):
    for size in reversed(range(len(x))):
        max_i = 0
        for i in range(1, 1+size):
            if x[i] > x[max_i]:
                max_i = i
        swap(x, max_i, size)