선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

개념 

• 정렬되지 않은 원소들에 대해 가장 작은 원소를 찾아 가장 앞의 데이터와 교환하는 방식 
• in-place sorting 알고리즘

코드

def selection_sort(arr):
    for i in range(len(arr) - 1):
        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]

1. 주어진 리스트 안에서 가장 작은 원소를 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 1,2의 과정을 반복
4. 내부 반복문에서는 현재 위치부터 마지막 위치까지 최소값의 위치를 찾는다.
5. 외부 반복문에서는 최소값의 위치에 있는 원소와 현재 위치에 있는 원소를 교대(swap) 진행 

특징

• 장점
  • 거품 정렬과 마찬가지로 구현이 단순
  • 자료 이동 횟수가 미리 결정
• 단점 
  •  안정적이지 않다.

시간 복잡도

• (N-1) + (N-2) + ... + 2 + 1 => N(N-1)/2 => O(N^2)

 

참고

https://www.daleseo.com/sort-selection/

[알고리즘] 선택 정렬 - Selection Sort (Python, Java)