[Algorithm] 선택 정렬(Selection Sort)

선택 정렬(Selection Sort)

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

public class p01_selectionSort {

    // 오름차순
    public static int[] solution(int n, int[] arr){
        for(int i = 0; i < n-1; i++){ // 1
            int idx = i;
            for(int j = i+1; j < n; j++){ // 2
                if(arr[j] < arr[idx]) idx = j; // 3
            }
            
            // 4
            int tmp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = tmp;
        }
        return arr;
    }

    // 내림차순
    public static int[] solution2(int n, int[] arr){
        for(int i = 0; i < n-1; i++){
            int idx = i;
            for(int j = i+1; j < n; j++){
                if(arr[j] < arr[idx]) idx = j;
            }
            int tmp = arr[i];
            arr[i] = arr[idx];
            arr[idx] = tmp;
        }
        return arr;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
        }
		System.out.println(solution(n, arr));
    }
}

1. 위치(idx)를 선택해준다.

2. i+1번째 원소부터 선택한 위치의 값(idx)과 비교를 시작한다.

3. 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(idx)를 갱신해준다. (가장 작은 값을 찾는 것)

4. 가장 작은 값을 찾았으므로 변경할 위치와 서로 교환해준다.

 

시간복잡도

• (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2
• 최선, 평균, 최악의 경우 시간복잡도는 O(n^2) 으로 동일

 

공간복잡도

주어진 배열 안에서 교환(swap)을 통해, 정렬이 수행되므로 O(n) 이다.

 

장점

• 정렬을 위한 비교 횟수는 많지만, Bubble Sort에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적이다.
• 다른 메모리 공간을 필요로 하지 않는다. (in-place sorting)

 

단점

• 시간복잡도가 O(n^2)이다.
• 불안정 정렬(Ustable Sort: 중복된 값이 입력 순서와 동일하지 않게 정렬되는 알고리즘) 이다. 

 

---

source

https://gyoogle.dev/blog/algorithm/Selection%20Sort.html

선택 정렬(Selection Sort) | 👨🏻‍💻 Tech Interview