[알고리즘은 처음이라] Selection Sort(선택 정렬)

 

 

🌈요약

Selection Sort란?
현재 순서에 원소를 넣을 위치는 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

시간복잡도
O(n^2)
- Bubble Sort는 정렬 유무 관계 없이 항상 2개의 원소를 비교하기 때문에 최선, 평균, 최악의 경우 시간복잡도가 모두 O(n^2)으로 동일

공간복잡도
O(n)
- 주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되는 제자리 정렬

 

---

Selection Sort (선택 정렬)이란?

Bubble Sort와 유사한 알고리즘

현재 순서에 원소를 넣을 위치는 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘

 

 

진행 과정(오름차순)

1.  주어진 배열 중에 최소값을 찾는다.
2. 그 값을 맨 앞에 위치한 값과 교체한다.
3. 맨 앞의 원소를 뺀 나머지 남은 배열을 같은 방법으로 교체한다. 

 

구현(Java)

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
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}

 

1. 현재 순서에 원소를 넣을 위치(i)를 정한다.

 

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

 

3. 현재 선택한 위치(i)에 있는 값이 순회하고 있는 값(j)보다 크다면, 위치(i)를 갱신한다

 

4. 1번에서 선택한 위치(i)에 들어가야 하는 값의 위치가 indexMin에 저장되어 있기 때문에 서로 교환해준다

 

시간복잡도

(n-1) + (n-2) + (n-3) + ... 2 + 1 >> n(n-1)/2 이기 때문에 O(n^2)

Selection Sort는 각 회전마다 원소를 비교할 때 비교하는 원소의 수가 하나씩 줄어들기 때문에 O(n^2)이다. 최선, 평균, 최악의 경우 모두 시간 복잡도가 O(n^2)으로 동일하다.

 

 

 

공간복잡도

주어진 배열 안에서 교환(swap)을 통해 정렬이 수행되기 때문에 O(n)

 

 

장점

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

 

단점

• 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로 굉장히 비효율적이다.
• 불안정 정렬(Unstable Sort)이다