[정렬] 선택정렬(Selection Sort)의 개념/Java코드/시간복잡도/공간복잡도

[정렬] 선택정렬(Selection Sort)의 개념/Java코드/시간복잡도/공간복잡도

📌선택정렬의 개념

선택정렬(Selection Sort)은 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 그 위치에 어떤 원소를 넣을지 선택하는 알고리즘입니다. 선택정렬(Selection Sort)와 삽입정렬(Insertion Sort)이 종종 헷갈릴 수 있는데,

 

선택정렬은 배열에서 해당 자리를 이미 선택하고 그 자리에 오는 값을 찾는 것이며,

삽입정렬은 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 것입니다.

 

- 선택정렬은 제자리 정렬(in-place sorting) 알고리즘의 하나

 

제자리 정렬이란, 입력 배열(정렬되지 않은 값들) 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법이며
해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

- 선택정렬의 과정 

 

 

 

1. 주어진 배열 중에 최소값을 찾습니다.
2. 그 값을 맨 앞에 위치한 값과 교체합니다. (pass)
3. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체합니다.
4. 하나의 원소만 남을 때까지 위의 1~3 과정을 반복합니다.

gif로 보는 선택정렬 [출처 : https://github.com/GimunLee]

📌Java Code (오름차순 조건)

void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        // 1.
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  // 2.
            if (arr[j] < arr[indexMin]) {           // 3.
                indexMin = j;
            }
        }
        // 4. swap(arr[indexMin], arr[i])
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

1. 우선, 위치(index)를 선택해줍니다.
2. i+1번째 원소부터 선택한 위치(index)의 값과 비교를 시작합니다.
3. 오름차순이므로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(index)를 갱신해줍니다.
4. '2'번 반복문이 끝난 뒤에는 indexMin에 '1'번에서 선택한 위치(index)에 들어가야하는 값의 위치(index)를 갖고 있으므로 서로 교환(swap)해줍니다.

📌선택정렬의 시간복잡도

데이터의 개수가 n개라고 했을 때,
첫 번째 회전에서의 비교횟수 : 1 ~ (n-1) => n-1
두 번째 회전에서의 비교횟수 : 2 ~ (n-1) => n-2
           ...
(n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

비교하는 것이 상수 시간에 이루어진다는 가정 아래,
n개의 주어진 배열을 정렬하는데 O(n^2) 만큼의 시간이 걸립니다.
최선, 평균, 최악의 경우 시간복잡도는 O(n^2) 으로 동일합니다.

 📌선택정렬의 공간복잡도

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

💡 선택정렬의 장점

• 거품정렬(Bubble sort)과 마찬가지로 알고리즘이 단순합니다.
• 정렬을 위한 비교 횟수는 많지만, 거품정렬(Bubble Sort)에 비해 실제로 교환하는 횟수는 적기 때문에 많은 교환이 일어나야 하는 자료상태에서 비교적 효율적입니다.
• 거품정렬(Bubble Sort)와 마찬가지로 정렬하고자 하는 배열 안에서 교환하는 방식(제자리 정렬, In-place Sort)이므로, 다른 메모리 공간을 필요로 하지 않습니다. 

💡 선택정렬의 단점

• 시간복잡도가 O(n^2)으로, 비효율적입니다.
• 불안정 정렬(Unstable Sort) 입니다.

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

• 단순(구현 간단)하지만 비효율적인 방법 : 삽입 정렬, 선택 정렬, 버블 정렬
• 복잡하지만 효율적인 방법 : 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬
  
  

출처

https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

https://github.com/GimunLee/tech-refrigerator/blob/master/Algorithm/%EC%84%A0%ED%83%9D%20%EC%A0%95%EB%A0%AC%20(Selection%20Sort).md#%EC%84%A0%ED%83%9D-%EC%A0%95%EB%A0%AC-selection-sort