선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

정렬 알고리즘은 다음과 같이 나눠볼 수 있다.

• 단순하지만 비효율적인 방법 : 선택 정렬, 삽입 정렬, 버블 정렬
• 복잡하지만 조금 더 효율적인 방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

그 중에서 이번에는 선택 정렬에 대해 알아보려 한다.

개념

• 해당 순서에 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘이다.
• 현재 위치에 저장될 값의 크기가 작냐, 크냐에 따라서 최소 선택 정렬(오름차순 정렬)과 최대 선택 정렬(내림차순 정렬)로 나뉜다.

로직

1. 주어진 배열에서 첫번째 인덱스를 기준으로 잡는다. 기준은 처음부터 시작한다.
2. 주어진 배열에서 기준 이후의 값 중 최소값을 찾는다.
3. 최소값과 그 기준의 값을 교체한다.
4. 기준 이후의 나머지 배열을 같은 방법으로 교체한다.

int[] arr = {7, 6, 2, 4, 3, 9, 1};

private static void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) { // 1
            int standard = i;
            for (int j = i + 1; j < arr.length; j++) { // 2
                if (arr[j] < arr[standard]) standard = j; // 3
            }
          	
          	// 4
            int temp = arr[standard];
            arr[standard] = arr[i];
            arr[i] = temp;

            print(arr);
        }
    }

private static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

// 단계별 결과.
1단계 : 1 6 2 4 3 9 7 
2단계 : 1 2 6 4 3 9 7 
3단계 : 1 2 3 4 6 9 7 
4단계 : 1 2 3 4 6 9 7 
5단계 : 1 2 3 4 6 9 7 
6단계 : 1 2 3 4 6 7 9 
7단계 : 1 2 3 4 6 7 9 

• 먼저, 위치(index)를 선택한다. (주로 배열의 첫 번째부터 시작한다.)
• i+1번째 원소부터 선택한 위치의 값과 비교를 시작한다.
• 오름차순이므로 현재 선택한 자리에 있는 기준 값보다 순회하고 있는 값이 작다면 위치(index)를 갱신해준다.
• 코드의 2번 반복문이 끝난 뒤에는 작은 값을 찾아서 갱신했으므로 처음에 선택했던 기준값과 작은 값의 위치를 서로 교환해준다.

쉽게 말해서 기준이 되는 수와 나머지 수를 비교해서 가장 작은 수를 앞으로 계속 보내는 정렬이다.

간단하지만, 매우 비효율적이다.

1단계 => n개의 원소 비교

2단계 => n-1개의 원소 비교

3단계 => n-2개의 원소 비교

...

를 하여 비교 횟수는

n(n-1)/2가 된다.

즉, 시간 복잡도는 O(N^2)이 된다.

최악의 경우, 최선의 경우, 평균적인 경우 모두 시간 복잡도는 O(N^2)이 된다.

공간 복잡도는 주어진 배열 안에서 교환을 통해 정렬이 수행되므로 O(N)이다.

장점

• 알고리즘이 단순하다.
• 정렬을 위한 비교는 여러번 수행되지만, 실제로 교환 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료 상태에서 비교적 효율적인 면이 있다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

단점

• 시간 복잡도가 O(N^2)이므로 비효율적이다.
• 불안정 정렬(Unstable Sort)이다.