[Algorithm] (이코테) 선택 정렬 - 파이썬

교재 : 이것이 코딩 테스트다 with 파이썬
CHAPTER 6 정렬
실전문제 6-1 선택 정렬 156p

선택 정렬 기본예제

문제

가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음으로 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복하는 선택 정렬(Selection Sort)을 진행하자

제시된 데이터 : 7, 5, 9, 0, 3, 1, 6, 2, 4, 8

접근

처음에는 min_idx가 아니고 min을 value로 저장했는데 그렇게하니까 나중에 swap을 할 수 가 없어서 바꾸어주었다. 그렇게 했더니 책에 제시된 정답이랑 같은 코드를 낼 수 있었당~! 왕

노트

#python swap 코드
arr = [3,5]
arr[0],arr[1]=arr[1],arr[0]

풀이

array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
    min_idx = i
    for j in range(i+1,len(array)):
        if array[min_idx]>array[j]:
            min_idx = j
    array[i],array[min_idx]=array[min_idx],array[i]
    
print(array)

선택 정렬

• 시간 복잡도 : O(N^2)
• 알고리즘 풀이에 사용하기엔 너무 느리다.

References

이것이 코딩 테스트다 with 파이썬 - 나동빈 저