선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

0. 선택 정렬(selection sort)이란?

배열(array) / 리스트(list)에서 최소 값 을 선택하여 맨 앞부터 정렬시키는 방법

1. 선택 정렬(selection sort) 알고리즘의 예제

[5, 1, 3, 7, 2, 9]의 배열

• 1회전
  최솟값 : 1
  모든 배열을 확인하여 최솟값 1을 맨 앞으로 이동

• 2회전
  최솟값 : 2
  두 번째 부터 마지막까지 배열을 확인하여 최솟값 3을 두 번째 자리로 이동

• 3회전
  최솟값 : 3
  세 번째 부터 마지막까지 배열을 확인하여 최솟값 4을 세 번째 자리로 이동
  ...

• 최종
  1 2 3 5 7 9 로 정렬을 완성

---

# 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]
    return arr

# Selection Sort - pseudo code
for i ← 0 to n-2 do{
    min ← i 
    for j ← i+1 to n-1 do{
    # list : A[i+1] ... A[n-1]
        if(A[j] < A[min]) min ← j
    }
    swap(A[i], A[min])
}

2. 선택 정렬(selection sort)의 특징

• 장점

  • 자료 이동 횟수가 지정되어져 있다.
  • 단순 구현이 가능하다.

• 단점

  • 안정성을 만족하지 않는다.
  • 같은 값을 가진 레코드가 있는 경우에 상대적인 위치가 변경될 수도 있다.
  • 비효율적인 방법이다.

---

3. 선택 정렬(selection sort)의 시간복잡도

• 비교 횟수
  • 2 번의 for 루프 실행 횟수
  • 외부 루프: (n-1)
  • 내부 루프: 최솟값 찾기
• T(n) = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n²)

References

Blog