[Algorithm] JAVA 정렬 알고리즘 - 선택정렬(Selection Sort)

 

 

ㅇ 정렬이란?

데이터를 정해진 기준에 따라 배치해 의미 있는 구조로 재설정하는 것이다. 즉, 내림차 순이나 오름차 순으로 다시 배치하는 것이다.

 

 

 

ㅇ 정렬의 종류

① 버블 정렬(Bubble Sort) : 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식

② 선택 정렬(Selection Sort) : 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식

③ 삽입 정렬(Insertion Sort) : 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식

④ 퀵 정렬(Quick Sort) : pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식

⑤ 병합 정렬(Merge Sort) : 이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식

⑥ 기수 정렬(Radix Sort) : 데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식

 

 

 

 

ㅇ 선택 정렬 (Selection Sort)

대상 데이터에서 최솟(최댓)값을 찾아 "선택"하여 "선택된 최솟(최댓)값"을 차례대로 바꿔가면서 정렬하는 방법이다.

 

구현이 복잡하고, 시간 복잡도도 O(n²)으로 효율적이지 않아 코딩테스트에서는 많이 사용하지 않는다.

 

 

 

 

ㅇ 선택 정렬의 이해

 

선택 정렬의 과정은 다음과 같다.

 

① 남은 데이터에서 최솟(최대)값을 찾는다.

② 남은 데이터에서 가장 앞에 있는 데이터와 선택된 데이터를 바꾼다(swap).

③ 가장 앞에 있는 데이터의 위치를 변경해 (index++) 남은 정렬 부분의 범위를 축소한다.

④ 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정렬 부분이 없을 때까지 반복한다.

 

이 과정이 반복적으로 있는 것이다.

 

5 4 1 3 2 라는 배열을 초기 상태를 두고 그림으로 표현하면 다음과 같다.

 

 

최솟값을 찾아 앞에서부터 나열하기 때문에 앞에서부터 배열된 모습을 확인할 수 있다.

 

선택 정렬은 앞 index(0)부터 비교하면서 최솟값을 찾는다.

 

1회전에는 index가 0(나열할 대상 데이터)이며, 처음 데이터부터 마지막 데이터까지 비교하며 최솟값을 찾는다. 최솟값은 1이므로 index[0] 데이터와 자리를 바꾼다. 

 

2회전에는 index가 1(나열할 대상 데이터)이며, index[1] 데이터부터 마지막 데이터까지 비교하며 최솟값을 찾는다. 최솟값은 2이므로 index[1] 데이터와 자리를 바꾼다.

 

3회전에는 index가 2(나열할 대상 데이터)이며, index[2] 데이터부터 마지막 데이터까지 비교하며 최솟값을 찾는다. 최솟값은 3이므로 index[2] 데이터와 자리를 바꾼다.

 

4회전에는 index가 3(나열할 대상 데이터)이며, index[3] 데이터부터 마지막 데이터까지 비교하며 최솟값을 찾는다. 최솟값은 4이므로 index[3] 데이터와 자리를 바꾼다.

 

 

 

선택정렬의 시간 복잡도를 빅오(Big-O) 기법을 적용하면 총 두 가지의 계산을 한다.

 

첫번째는 비교 연산의 횟수를 계산하는 것이다.

1회전부터 마지막 회전까지 n-1번, n-2번, ... , 1번의 횟수로 최솟값을 찾는다. 즉, (n-1) + (n-2) + ... + 1 = n(n-1)/2번이다.

 

두 번째는 교환 연산의 횟수를 계산하는 것이다.

교환 횟수는 데이터들의 위치를 바꾸는 경우의 수에 비례하여 교환 연산의 횟수는 n-1번이다.

 

따라서 선택 정렬의 시간 복잡도는 비교 연산의 횟수와 교환 연산의 횟수를 더한 것으로 O(n²)이다.

 

데이터의 크기가 작으면 알고리즘이 간단하여 사용하기 수월하지만, 데이터의 크기가 커질 수록 오래 걸리기 때문에 다른 알고리즘을 사용하는 것이 좋다.

 

 

 

 

 

 

 

 

ㅇ 선택 정렬 자바 코드

class Main {
    public static int[] arr = new int[5];

    public static void main(String[] args) {

        arr = new int[]{5, 4, 1, 3, 2};

        selectionSort(arr);
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " " );
        }
    }

    static void selectionSort(int[] arr) {
        for (int i=0; i<arr.length-1; i++) {
            int minIdx = i;
            for (int j=i+1; j<arr.length; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIdx];
            arr[minIdx] = temp;
        }
    }
}

 

먼저 arr을 5 4 1 3 2라는 정렬되지 않은 배열로 초기화한 후, selectionSort(arr)을 수행한다.

 

selectionSort에서는 arr의 index를 0부터 데이터의 크기-1까지 회전하며, 최솟값을 가지는 인덱스를 i로 설정한다.

각 회전에서는 i+1부터 마지막 데이터까지 비교하며 최솟값을 가지는 인덱스를 찾는다.

 

그 후, 현재 데이터와 최솟값을 가지는 데이터를 교환한다.

 

 

 

 

 

---

 

 

ㅇ 선택 정렬 정리

 

 >  메모리 소모가 적으며, 뒤의 index로 갈수록 최솟값을 찾는 범위가 점점 줄어든다.

 >  안정성을 만족하지 않는다.

     이 특징은 선택 알고리즘을 찾아보면서 알게 되었는데 만약 값이 같은 데이터가 있다면 그 데이터가 어디있느냐에 따라 결과값이 변경될 수 있다는 것이다.

 

만약 [(연필, 100) , (펜, 50) , (지우개, 50) , (가위, 150)] 가 있다면 가격 순대로 나열하고, 가격이 같다면 가나다 순으로 정렬한다고 해보자.

 

가격순으로 정렬을 하면

round1 : [(펜, 50) , (연필, 100) , (지우개, 50) , (가위, 150)] 

round2 : [(펜, 50) , (지우개, 50) , (연필, 100)  , (가위, 150)] 

round3 : [(펜, 50) , (지우개, 50) , (연필, 100)  , (가위, 150)] 

 

가나다 순으로 정렬하면 지우개가 더 앞에 있어야 한다. 

 

즉, 지우개가 펜보다 앞에 위치하고 있으면 주어진 조건을 만족하며 배열할 수 있지만

지우개가 펜보다 뒤에 위치하고 있다면, 주어진 조건을 만족시키지 않는다.

 

이 특징이 안정성을 만족하지 않는다고 한다.