Selection Sort [선택정렬]

Selection Sort [선택정렬]

Worst case performance : O(n^2)

Best case performance : O(n^2)

Average case performance : O(n^2)

Worst case space complexity : O(n) total, O(1) auxiliary

선택정렬은 퍼포먼스가 n squared 로 좋지 않다. 하지만 구현이 쉬워서 많은 사람들이 사용하고 있다.

[ 예제 ] 

아래 그림의 4 6 1 3 5 2 리스트를 1 2 3 4 5 6 으로 차례가 맞게 정렬하자.

선택정렬의 예시를 알아보자. 선택정렬은 하나의 공간이 필요하다 그것을 Minimum value라는 공간이라고 한다.

그러면 처음 아이템부터 끝까지 비교하면서 해당 리스트를 정렬해보자. ( Minimum value란 비교할 값이 더 작으면 해당 값을 Minimum value로 지정해준다. )

1. 첫번째 아이템인 4를 Minimum value로 지정하고 하나씩 비교를 하다보면 4가 1보다 크니까 Minimum value가 1로 된다. Minimum value인 1을 나머지 3하고 비교하고, 5하고 비교하고, 2하고 비교해도 1이 작으므로 Minimum value는 1이된다. 그러므로 현재에 있는 포지션 4와 Minimum value값인 1이 서로 값이 다르므로 리스트에서 두개의 값을 swapping 해준다.

-

2. 1번과 같이 첫번째 비교가 끝났으므로 비교할 point를 6으로 이동하고 그러면 Minimum value도 같이 6이된다. 그리고 정렬되지 않는 리스트를 순차적으로 비교하게 된다. 비교한 후 현재에 있는 포지션 6과 Minimum value값인 2가 서로 값이 다르므로 리스트에서 두개의 값을 swapping 해준다.

3. 2번과 같이 비교가 끝났으므로 비교할 point를 next point인 4로 이동한다. 그러면 Minimum value도 같이 4가 된다. 그리고 정렬되지 않는 리스트를 순차적으로 비교하게 된다. 비교한 후 현재에 있는 포지션 4와 Minimum value값인 3이 서로 값이 다르므로 리스트에서 두개의 값을 swapping 해준다.

4. 그 후에 과정에도 반복적으로 하다보면 

   - 비교할 point가 이동하여 4가 되며 Minimum value도 4가 되고 순차적으로 비교하면 4는 그 다음 비교할 숫자들인 5랑 6보다 작으므로 Minimum value에 있는 값하고 비교할 point하고 값이 같다. 그러므로 swapping이 이루어지지 않는다. 

   - 그리고 next point인 5로 비교할 point를 잡아도 5는 6보다 작으므로 swapping이 이루어지지 않는다. 

   - 그리고 마지막인 6으로 next point가 이동하면 비교할게 없으므로 그 역시 swapping이 일어나지 않는다.

[결론]

해당 정렬이 과정을 보면 모든 아이템을 각각 다른 아이템을 비교하니까 현재 갖고있는 6개의 아이템을 6번 비교하면 6 * 6 = 36개 즉, n의 squared가 된다.

[예제소스]

public class SelectionSortExample {
    // 오름차순 선택정렬
    public static void selectionSortAsc(int[] arr){
        for (int i = 0; i < arr.length - 1; i++)
        {
            int index = i;
            for (int j = i + 1; j < arr.length; j++){
                // 선택 원소보다 작은 원소위치 찾기
                if (arr[j] < arr[index]){
                    index = j;
                }
            }

            int smallerNumber = arr[index]; // 최솟값 임시 저장
            arr[index] = arr[i]; // 최솟값 위치에 선택위치의 원소와 교환
            arr[i] = smallerNumber; // 선택위치에 최솟값 교환
        }
    }

    // 내림차순 선택 정렬
    public static int[] selectionSortDesc(int[] items) {
        int indexMax, temp;
        for (int i=0;i<items.length-1;i++) {
            indexMax = i;
            for(int j=i+1;j<items.length;j++) {
                //선택원소 보다 큰 원소위치 찾기
                if (items[j] > items[indexMax]) {
                    indexMax = j;
                }
            }
            temp = items[indexMax]; //최대값 임시 저장
            items[indexMax] = items[i]; //최대값 위치에 선택위치의 원소와 교환
            items[i] = temp; //선택위치에 최대값 교환
        }
        return items;
    }

    public static void main(String a[]){
        int[] arr1 = {9,14,3,2,43,11,58,22};
        System.out.println("Before Selection Sort");
        for(int i:arr1){
            System.out.print(i+" ");
        }
        System.out.println();

        selectionSortAsc(arr1);
        //selectionSortDesc(arr1);

        System.out.println("After Selection Sort");
        for(int i:arr1){
            System.out.print(i+" ");
        }
    }
}