선택정렬 selection Sorting

주어진 리스트에서 최소값을 찾아 맨 앞에 위치한 원소와 자리를 바꾸고, 그 다음으로 작은 값을 찾아 그 다음 위치에 위치시키는 과정을 반복하여 정렬하는 알고리즘

선택정렬 1

def selection_sort(arr):
    n = len(arr)
    # 배열의 모든 요소를 순회
    for i in range(n-1):
        # 최소값의 인덱스를 찾음
        min_idx = i
        for j in range(i+1,n):
            if arr[min_idx] > arr[j] :
                min_idx = j
        # 현재 인덱스와 최소값의 인덱스를 swap
        arr[min_idx], arr[i] = arr[i], arr[min_idx]
    return arr

arr = [64, 25, 12, 22, 11]
selection_sort(arr)

[11, 12, 22, 25, 64]

• 알고리즘
  • 첫번째 반복문
    • 모든 요소를 비교하기 위해 n-1번 비교한다.
    • n번째는 n-1에서 정해지기 때문에 할 필요가 없다.
  • 두번째 반복문
    • i 이상의 인덱스에서 최소값을 가진 인덱스(min_idx)를 구한다.
    • 범위는 i ~ n까지의 원소 중에 비교하면 된다.
      • 두번째 반복문 시작전 min_idx = 1 는 범위의 첫번째 인자를 최소값으로 초기화 시키고 시작한다는 의미이다.
  • Swap
    • 두번째 반복문이 끝나면 범위 안에 최소값인 인덱스를 알 수 있다.
    • 범위의 첫번째 인자 i와 최소값의 인덱스 min_index를 서로 교체한다.
• 시간복잡도
  • O(n^2)
  • 버블정렬보다는 빠르다. ( 교환이 많이 일어나야하는 자료에 유리 )
  • 리스트가 길수록 오래걸린다.