선택 정렬(Selection Sort)

개념

• 제자리 정렬 - 추가 메모리 필요없음
• 최솟값을 찾아서 맨앞과 교체
• 맨앞 빼고 다시 최솟값 찾아서 반복

구체적인 개념

선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.

• 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.

예시

배열에 9, 6, 7, 3, 5가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

코드

def selectionSort(arr):
    n = len(arr)
    for i in range(n):
        min = i
        for j in range(i,n):
            if arr[min] >= arr[j]:
                min = j
        arr[min], arr[i] = arr[i], arr[min]


arr = [9,6,7,3,5]
selectionSort(arr)
print(arr)

특징

• 장점
  - 거품 정렬과 마찬가지로 간단해서 구현이 쉽다.
  • 자료 이동 횟수가 미리 결정된다.
• 단점
  - 안정성을 만족하지 않는다.
  (값이 같은 레코드가 있는 경우 상대적인 위치가 바뀔 수 있다.)
  

시간복잡도

비교횟수

• 두 개의 for문
• 외부 루프 : n-1
• 내부 루프 : (최솟값 찾기) n-1, n-2, ... , 2, 1

교환 횟수

• 외부 루프의 실행 횟수와 동일. 즉, 상수 시간
• 한 번 교환하기 위하여 3번의 이동 3(n-1)

T(n) = n(n-1)/2 = O(n^2)

---

정렬 알고리즘 시간복잡도 비교