[파이썬] 정렬 알고리즘 - 선택 정렬

선택 정렬(Selection Sort)

정렬과정

• 리스트 내의 최소값을 찾음
• 그 값을 리스트의 맨 앞에 위치한 값과 교환
• 맨 처음 위치를 제외한 나머지 값들을 대상으로 위 과정 반복 (시간 복잡도 O(n^2)

Step

최솟값 7을 찾아 맨앞 35와 교환하고 다시 최소값을 찾음

다시 정렬 안된 리스트와 교환하고 위의 과정을 반복함

정렬되지 않은 마지막 원소가 가장 큰 값을 가지므로 정렬 완료

 

코드 구현

def selectionsort(arr) :
    n = len(arr)
    for i in range(n-1) :
        min_arr = i
        for j in range(i+1, n) :
            if arr[min_arr] > arr[j]:
                min_arr = j
        arr[i], arr[min_arr] = arr[min_arr], arr[i]
    return arr

반응형

k번째로 작은 원소를 찾는 알고리즘

def selectionsort(arr, k) :
    n = len(arr)
    for i in range(k) :
        min_arr = i
        for j in range(i+1, n) :
            if arr[min_arr] > arr[j]:
                min_arr = j
        arr[i], arr[min_arr] = arr[min_arr], arr[i]
    return arr[k-1]