정렬 알고리즘 : 선택 정렬 (Python)

스터디 목표 설정 | 2021.09.08 부터 '이것이 취업을 위한 코딩테스트다.' 책을 기반으로 공부한 알고리즘을 블로그에 기록하고 프로그래머스 및 백준 사이트에서 알고리즘 문제를 풀이합니다. 이 과정을 통해 상황에 가장 적절한 알고리즘을 선택하여 문제를 빠르고 정확하게 해결하는 소양을 갖추려고 합니다.

---

 

선택 정렬

---

 

선택 정렬 gif

개념

 데이터가 무작위로 여러 개 있을 때, 이중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번쨰와 데이터와 바꾸는 과정을 반복하는 정렬 방법이다.

 

소스 코드

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

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

print('result', array)

 

시간 복잡도

O(N^2)

 N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다. 또한 매번 가장 작은 수를 찾기 위해서 비교 연산이 필요하다. 다른 정렬 알고리즘과 비교했을 때 매우 비효율적이지만, 특정한 리스트에서 가장 작은 데이터를 찾는 일에 사용할 수 있다.