선택정렬 (selection sort)

 

단순검색
O(n) 시간은 목록의 모든 원소를 한 번씩 건드려야 한다는 뜻이다.
음악 플레이리스트에 가수별로 몇 곡이 들었는지 기록한 목록이 있다고 했을때, 가장 많이 들은 것부터 가장 적게 들은 것 순서로 정렬할시 단순검색을 사용한다면…

➜ 연주횟수가 가장 많은 가수를 찾는다. O(n)
➜ 연주횟수가 그 다음으로 가장 많은 가수를 찾는다. O(n)
➜ 연주횟수가 그 다음으로 가장 많은 가수를 찾는다. O(n)
…

모두 합해서 O(n*n)시간, 즉 O(n2)시간이 걸린다.
선택정렬은 깔끔한 알고리즘이지만 빠르지는 않다.


def findSmallest(arr) :
    smallest = arr[0] ##가장 작은 정수를 저장
    smallest_index = 0 ##가장 작은 정수의 인덱스를 저장
    for i in range(1, len(arr)) : 
        if arr[i] < smallest :
            smallest = arr[i]
            smallest_index = i
    return smallest_index

def selectionSort(arr) : ##배열정렬
    newArr = []
    for i in range(len(arr)) :
        smallest = findSmallest(arr) ##배열에서 가장 작은 정수를 찾아 새로운 배열에 추가한다.
        newArr.append(arr.pop(smallest))
    return newArr
print selectionSort([1,5,7,9,10])

 

reference

도서 : Hello Coding 그림으로 개념을 이해하는 알고리즘