3.1. Sorting - 3.1.2 Selection Sort

CS - 3. Common Algorithms - 3.1. Sorting - 3.1.2 Selection Sort

 

💡 Selection sort is a sorting algorithm that selects the smallest unsorted item in the list and swaps it with index 0, then finds the next smallest and places it into index 1 and so on.

선택 정렬은 목록에서 정렬되지 않은 가장 작은 항목을 선택하여 인덱스 0으로 바꾼 다음 다음으로 작은 항목을 찾아서 인덱스 1에 배치하는 정렬 알고리즘입니다.

 

선택 정렬(Selection Sort)은 이름에서 알 수 있듯이, 가장 적은 값을 선택하여 앞으로 옮기는 방식으로 정렬하는 알고리즘입니다.

선택 정렬의 동작 과정은 이런 순입니다.

1. 주어진 리스트 중에서 최소값을 찾습니다.

2. 그 값을 리스트의 맨 앞에 위치한 값과 교체합니다.

3. 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복합니다.

4. 이 과정이 끝나면 리스트는 정렬된 상태가 됩니다.

 

In Python

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

 

선택 정렬의 시간 복잡도는 O(n^2)로, 버블 정렬과 동일하게 데이터의 양이 많지 않은 경우에 효과적입니다.

하지만, 마찬가지로 데이터의 양이 많거나 무작위로 배열된 퀵 정렬, 병합 정렬 등이 더 효율적인 정렬 알고리즘을 사용하는것이 좋다!