단순 선택 정렬(straight selection sort)

단순 선택 정렬(straight selection sort)

단순 선택 정렬은 두 가지 부분으로 볼 수 있다. 하나는 현재까지 정렬된 부분과 나머지 정렬해야하는 부분이다.

무슨 말인가? 즉, 단순 선택 정렬은 배열의 가장 앞 쪽부터 시작해서 정렬하고자하는 기준에 따라 정렬되지 않은 부분을 모두 검색하며, 그 중 현재 정렬되어야 할 위치에 기준에 따른 값을 정렬시키는 방식이다.

버블 정렬과 비교했을 경우 버블 정렬은 이웃하는 요소들을 검색하며, 정렬기준에 따라 이웃 간 교환이 발생한다면, 단순 선택 정렬은 정렬되지 않은 부분들을 모두 검색하여 그 중 정렬기준에 맞는 값을 현재 정렬해야하는 위치와 교환하는 방식이다.

---

Do it 자료구조와 함께 배우는 알고리즘 입문 참조

---

 

static int change = 0; //교환횟수
static int search = 0; //검색횟수

	// 교환부분
    static void swap(int[] a , int idx1 , int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

	//검색부분
    static void selectionSort(int[] a , int n){
        for(int i = 0 ; i < n-1 ; i++){
            int min = i;
            for(int j = i +1;j < n ;j++){
                search++;
                if(a[j] < a[min])
                    min = j;
            }
            change++;
            swap(a,i,min);
        }
    }
    
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);

        System.out.println("단순 선택 정렬");
        System.out.print("요솟수 : ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];

        for(int i = 0 ; i < nx; i++){
            System.out.print("x["+i+"]: ");
            x[i] = stdIn.nextInt();
        }

        selectionSort(x,nx);
        System.out.println("\n오름차순으로 정렬했습니다.");
        for(int i = 0 ; i < nx ; i++)
            System.out.print(x[i] + " ");

        System.out.println("\n\n교환 횟수: " + change);
        System.out.println("비교 횟수: " + search);
    }

단순 선택 정렬 결과

---

단순 선택 정렬 알고리즘의 경우)

 

1. 검색-비교가 n개 데이터에 대해서 (n^2 - n) / 2번 수행이된다.

-> n개의 데이터라고 했을 경우 검색범위는 현재 정렬하고자 하는 위치를 제외한 나머지 부분을 검색하게 된다. 그리고 정렬이 끝나고 나면 정렬하고자 하는 위치가 1칸 이동하며, 검색 범위도 1개가 줄어든다. 이런식으로 하다보면 최종적으로는 n-1 + .....+ 1번 검색-비교가 이루어지고 정수의 합은 (n)(n+1)/2이므로 n 대신 n-1을 넣으면 위와 같은 총 횟수가 나오게된다.

 

2. 안정적이지 않은 정렬 알고리즘이다.

->교환 하는 과정에서 동일한 값에 대해서 순서가 보장이 되지 않을 수 있다.

예시로 {3,4,2,3,1}이라는 배열을 정렬한다고 생각해보자.

이때 처음 요소 3과 마지막 요소 1이 최초로 교환될 것이다. 그리고 교환된 3은 4를 제외한 어떤 요소와도 교환이 이루어지지 않다가 최종적으로 4,3이 교환되면서 정렬이 완료되고, 해당 배열에 동일한 값을 갖고 있는 3의 순서가 바뀌게된다.

 

조금 더 이해를 위해서 배열의 요소 값은 학생들의 등급이라고 가정했을 때 같은 등급을 가진 학생이 있을 수 있다. 그러나 같은 등급을 가졌다고 두 학생이 같지는 않다. 그리고 순서대로 학생들이 서 있다고 했을 경우를 생각해보면 동일한 값을 갖는 두 학생이 정렬을 하면서 서 있는 순서가 바뀌게 되는 것이다. 이 부분은 단순 정수를 갖고 했을 경우 헷갈릴 수 있어서 한번 생각해본 것이다.