선택정렬(Selection Sort)

선택정렬(Selection Sort)

개념

Selection Sort는 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘입니다.

로직

최소값을 찾아 왼쪽으로 이동시키는데 데이터의 크기만큼 반복하여 정렬하는 방법

1. 주어진 배열에서 최소값을 찾습니다.
2. 그 값을 맨앞에 위치한 값과 교채합니다.
3. 맨처음 위치를 뺀 나머지 배열에 1~2의 과정을 반복합니다.

코드

SelectionSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class SelectionSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void selectionSort(int[] arr) {
        int index;
        for (int i = 0; i < arr.length; i++) {
            index = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[index] > arr[j]) {
                    index = j;
                }
            }
            swap(arr, index, i);
        }
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

console

정렬 전: [56, 11, 41, 96, 29, 9, 19, 13, 39, 28]
정렬 후: [9, 11, 13, 19, 28, 29, 39, 41, 56, 96]

시간복잡도

주어진 데이터의 개수가 $n$개 일때
$$
\sum_{i=1}^{n-1}n-i=(n-1)+(n-2)+(n-3)+...+1=\frac{n(n-1)}{2}
$$
번의 비교를 하게 된다.

최선, 최악, 평균 모두 $O(N^2)$의 동일한 시간복잡도를 갖습니다.

장점

1. 알고리즘이 단순하여 구현이 쉽다.
2. Bubble Sort와 실제로 비교하는 횟수는 같지만 교환하는 횟수가 작기때문에 Bubble Sort에 비해 비교적 효율적입니다.
3. 추가적인 메모리 공간이 필요하지 않다.

단점

1. 시간복잡도가 $O(N^2)$으로 비효율적이다.
2. 불완전 정렬이다.