[Data Structure] 선택 정렬 - Selection Sort

선택 정렬 (Selection Sort)

Unstable Sort

 

시간복잡도

- O(n²)

 

장점

- 알고리즘이 단순하다

- 실제로 교환하는 횟수가 적기 때문에 많은 교환이 일어나는 자료상태에서 Bubble Sort보다는 효율적이다

- 추가 메모리가 필요없다

 

단점

- 불안정 정렬(Unstable Sort)이다

- 시간복잡도가 최선/평균/최악 전부 O(n²)으로, 굉장히 비효율적이다

 

과정

1. 주어진 배열 중 최솟값 찾기
2. 해당 값을 맨앞으로 옮기기
3. 나머지 요소들도 똑같이 반복

 

 

▶ Selection Sort Code

static void selection_sort(int [] A){
        for(int i=0; i<A.length-1; i++){
            int min = i;
            for(int j=i+1; j<A.length; j++){
                if(A[j] < A[min])
                    min = j;
            }
            int tmp = A[min];
            A[min] = A[i];
            A[i] = tmp;
        }
    }

 

 

▶ Full Code

package Sort;

public class Selection_Sort_11 {
    public static void main(String[] args) {
        int [] A = new int[30]; // 정렬할 배열 A

        for(int i=0; i<A.length; i++)
            A[i] = (int)(Math.random()*201); // 0~200

        // 정렬 전 A 출력
        System.out.print("A []");
        for(int i=0; i<A.length; i++){
            if(i%10==0) System.out.println();
            System.out.print(A[i] + "\t");
        }
        System.out.println("\n");

        selection_sort(A);

        // 정렬 후 A 출력
        System.out.print("result []");
        for(int i=0; i<A.length; i++){
            if(i%10==0) System.out.println();
            System.out.print(A[i] + "\t");
        }
        System.out.println("\n");
    }

    static void selection_sort(int [] A){
        for(int i=0; i<A.length-1; i++){
            int min = i;
            for(int j=i+1; j<A.length; j++){
                if(A[j] < A[min])
                    min = j;
            }
            int tmp = A[min];
            A[min] = A[i];
            A[i] = tmp;
        }
    }
}