선택 정렬 (Selection Sort)

written by sohyeon, hyemin 💡

1. 선택 정렬이란?

선택 정렬은 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘이다.

2. 동작 방식

1. 가장 작은 값의 요소인 1을 선택해 정렬을 시작하고, 6과 교환한다.
2. 아직 정렬하지 않은 배열에서 가장 작은 요소인 3을 선택해 정렬을 시작하고, 배열의 첫 번째 요소인 4와 3을 교환한다.
3~7. 위의 그림처럼 이 과정을 반복한다.

3. 특징

1) 장점

• 자료 이동 횟수가 미리 결정된다.

2) 단점

• 선택 정렬 알고리즘은 안정적이지 않다.
  • 즉, 요솟값이 중복될 경우 상대적인 위치가 변경될 수 있다.

4. 시간복잡도

• 비교 횟수

  • 두 개의 for 루프의 실행 횟수
  • 외부 루프 : (n-1)번
  • 내부 루프(최솟값 찾기) : 0에서 n-2까지 변하는 i에 대하여 (n-1)-i번 (n-1, n-2, ... , 2, 1번)

• 교환 횟수

  • 외부 루프의 실행 횟수와 동일하다.
  • 한 번 교환하기 위하여 3번의 이동이 필요하므로 전체 이동 횟수는 3(n-1)번

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

5. 선택 정렬 Java 코드

선택 정렬(SelectionSort)의 교환 과정

1. 아직 정렬하지 않은 부분에서 가장 작은 키의 값(a[min])을 선택한다.  
2. a[min]과 아직 정렬하지 않은 부분의 첫 번째 요소를 교환한다.

ex) 예제

// 단순 선택 정렬
static void selectionSort(int[] a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;           // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 기록한다.
        for (int j = i + 1; j < n; j++)
            if(a[j] < a[min])
            min = j;
        if(i != min)
            swap(a, i, min);   // 아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환한다. 
    }
}

단순 선택 정렬 알고리즘의 요솟값을 비교하는 횟수는 (n^2-n)/2회이다.

최솟값이 자기 자신이면 자료 이동을 하지 않도록 한다.

• 일반적으로 비교 연산 1개가 이동 연산 3개보다 시간이 적게 걸리므로 효과적이다.

Reference & Additional Resources

• Do it! 자료구조와 함께 배우는 알고리즘 입문 자바편

• C언어로 쉽게 풀어쓴 자료 구조