[탐색과 정렬] 선택 정렬

정렬

자료를 크기 순서에 맞춰 일렬로 나열하는 것

가나다 순 또는 알파벳 순으로 나열한 사전이 좋은 예시 중 하나다.

 

정렬 종류

• 선택 정렬 (Selection Sort)
• 삽입 정렬 (Insertion Sort)
• 병합 정렬 (Merge Sort)
• 퀵 정렬 (Quick Sort)
• 거품 정렬 (Bubble Sort)

 

선택 정렬

제자리 정렬 알고리즘의 하나

가장 작은 값을 선택하여 자리를 교체하는 방식을 반복하여 진행한다.

 

이미지 출처 : https://godgod732.tistory.com/13?category=659135

 

코드

def selection_sort(list):
    for i in range(0, len(list) - 1):
        for j in range(i + 1, len(list)):
            if list[i] > list[j]:
                list[i], list[j] = list[j], list[i] # swap
    return list

계산 복잡도는 $$ O(n^2) $$

 

마지막 값은 비교할 필요가 없으므로 바깥 반복문의 반복 횟수는 자료의 수보다 하나 적게 설정하면 된다.

개인적으로 선택 정렬은 기준값 하나를 나머지 자료와 비교해나간다는 점을 기억하는 게 추후 구현하기에 더 편하다.