[자료구조] 선택 정렬(Selection Sort)

목차

정렬 종류
비교 기반 정렬(Comparison Based Sorts) 
- Selection Sort, Bubble Sort, Insertion Sort, Heap Sort, Merge Sort, Quick Sort
비비교 기반 정렬(Non-comparison Based Sorts)
- Counting Sort, Radix Sort, Bucket Sort

선택 정렬(Selection Sort)

개념

• 선택 정렬은 제일 작은 값을 찾고 앞에 있는 값들과 하나씩 변경하는 과정입니다. 단순하게 그냥 정렬 방식을 생각했을 때 떠올릴 수 있는 가장 쉬운 방법입니다.
  • 정렬되어 있지 않은 책장이 있을 때, 모든 책을 살핀 뒤 제일 크기가 작은 책과 제일 왼쪽에 있는 책과 바꾸어 책장에 넣습니다. 그 후에 이제 나머지 책중에서 다시 두 번째로 크기가 작은 책을 찾고 두 번째 책과 바꾸어 책장에 넣습니다. 이런 식으로 반복해서 진행하면 모든 책이 올바르게 정렬될 것입니다.
• 시간복잡도는 O(n^2)으로 비효율적인 정렬 알고리즘입니다. 
• 공간복잡도는 해당 배열에 그대로 swap 하며 진행하면 되기 때문에 O(1)입니다.
• 

코드

• Selection Sort

  • def selection_sort(arr):
        for i in range(len(arr)):
            min_index = i
            for j in range(i + 1, len(arr)):
                if arr[j] < arr[min_index]:
                    min_index = j
    
            arr[i], arr[min_index] = arr[min_index], arr[i]
    
    
    arr = [7, 3, 2, 5, 6, 10, 9, 8, 1]
    selection_sort(arr)
    print(arr)
    
    -->
    [1, 2, 3, 5, 6, 7, 8, 9, 10]

출처

• https://leetcode.com/explore/learn/card/sorting/694/comparison-based-sorts/4433/