[python] 파이썬 선택 정렬 알고리즘 (selection sort)

Selection sort

선택 정렬은 제자리 정렬(in-place) 알고리즘의 하나로, 알고리즘이 단순하며 사용할 수 있는 메모리가 제한적인 경우에 사용시 성능 상의 이점이 있다. 

시간 복잡도는 O(N^2)이다. 

 

알고리즘은 이렇다. 

1. 아직 정렬이 안된 배열에서 가장 작은 수를 찾는다.  min
2. 그 값을 정렬이 안 된 배열의 맨 앞으로 보낸다. 
3. 이 과정을 반복한다. 

def selectSort(arr, n):
    for i in range(0,n-1):
        min = i; 
        j = i+1
        while(j<n):
            if(arr[j] < arr[min]):
                min = j
            j += 1

        if(i != min):
            tmp = arr[i]
            arr[i] = arr[min]
            arr[min] = tmp