[자료구조] 선택정렬

1. 전체 값 중 가장 작은 값을 찾음
2. 해당 값을 맨 첫번째에 배치함
3. 첫번째 값을 제외하고 가장 작은 값을 찾아 두번째에 배치함
4. 두번째, 세번째, ... n-1번째 값을 제외하고 가장 작은 값을 찾아 정해진 위치에 배치함.

✨선택정렬의 시간 복잡도

버블 정렬 : 중간에 정렬이 완료된 것이 확인되면 정지

선택 정렬 : 반드시 n-1,n-2,...,2,1 번의 비교 연산을 수행해야함. 약 n*(n-1)/2번의 연산을 필요로 함 = O(N^2)

 

✨선택정렬의 구현

python으로 구현해보겠다.

def selection_sort(arr):
    length = len(arr)
    for i in range(length-1):
        minindex = i
        for j in range(i+1,length):
            if arr[j] < arr[minindex]:
                minindex = j
            temp = arr[i]
            arr[i] = arr[minindex]
            arr[minindex] = temp
    return arr

arr = [10,2,3,5,9,1,4,6,8,7]
print(selection_sort(arr))