선택 정렬(Selection Sort)

  선택 정렬은 여러 가지 면에서 앞에서 살펴본 버블 정렬과 상당히 비슷하다. 두 가지 정렬 방법을 구분하는 게 어렵지는 않으니, 선택 정렬을 공부하는 김에 버블 정렬도 같이 공부하는 것을 추천한다.

1. 정의 🎿

선택 정렬

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

 

2. 동작 방식 🧦

  N개의 원소가 있다고 하자.
  우선, 배열에서 최솟값을 찾는다. 그리고 첫 번째 원소와 배열에서 찾은 최솟값의 원소를 바꿔준다. 이것이 1회전 수행한 것이다. 이렇게 되면 배열의 첫 번째에 위치한 원소가 가장 작은 값을 가지게 된다. 
  2회전을 수행할 때는 첫 번째 원소를 제외한 나머지 배열들 중에서 최솟값을 찾는다. 그리고 해당 원소와 배열의 두 번째 원소를 바꿔준다. 이와 같은 방식으로 (N -1) 회전까지 수행하면 정렬이 마무리된다.
  위의 방식은 오름차순으로 정렬을 하고 있다. 만약 배열 중에서 최솟값이 아닌 최댓값을 찾아서 정렬한다면 내림차순으로 정렬할 수 있다.

 

3. 구현(JAVA) 👡

void selectionSort(int[] arr) {
    int indexMin, temp;

    // (원소의 개수 - 1)번 반복
    for(int i = 0; i < arr.length - 1; i++) {
        // 주어진 배열에서 최솟값 원소의 인덱스 번호 찾기
        indexMin = i;
        for(int j = i + 1; j < arr.length; j++) {
            if(arr[j] < arr[indexMin]) {
                indexMin = j;
            }
        }

        // 이미 정해져있는 교환 위치의 값과 최솟값 교환
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
    }
}

 

4. 시간복잡도 & 공간복잡도 👠

1. 시간복잡도

  위에서 살펴보았듯이 총 (N - 1)번 회전하고, i번째 회전에서 (N - i)의 연산을 수행한다. 그러면, 아래에 해당하는 수만큼 연산을 수행하게 된다.

(N - 1) + (N - 2) + ... + 2 + 1 = N * (N - 1) / 2

  따라서, 시간복잡도는 O(N^2)이다.
  정렬이 되어있던 안되어 있던 항상 비교를 수행하므로 최선, 평균, 최악의 상황에서 모두 O(N^2)의 시간복잡도를 가진다.

	최선(BEST)	평균(AVERAGE)	최악(WORST)
시간복잡도	O(N^2)	O(N^2)	O(N^2)

2. 공간복잡도

공간복잡도의 경우 추가적인 배열을 만들지 않고 해당 배열에서 교환이 이루어지므로 O(N)이다.

 

5. 장점 & 단점 🦶

1. 장점

• 코드가 매우 단순하다.
• 다른 메모리 공간을 필요로 하지 않는다.

2. 단점

• 시간복잡도가 O(N^2)이므로 상당히 비효율적이다.
• 정렬이 되어있더라도 비교 연산을 수행한다.

 

해당 글은 Gyoogle님의 선택 정렬(Selection Sort)을 참고하였습니다.