자바로 구현한 선택 정렬 알고리즘

선택 정렬알고리즘은 O(N²)의 시간 복잡도를 가지는 정렬 알고리즘 중에 하나입니다.

선택 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬입니다. 3. 불안정 정렬입니다.

 

1. 비교 정렬 : 서로 값을 비교하여 정렬하는 알고리즘입니다.

2. 제자리 정렬 : 해당 배열 외에 또 다른 배열의 저장 공간이 필요가 없습니다.

3. 안정정렬 : 같은 값일 경우 해당 정렬이 변경되지 않습니다.

 

선택정렬은 이름에서와 같이 최솟값을 찾아 선택하여 선수대로 교환하는 정렬방식입니다.

정렬 과정을 요약하면 다음과 같습니다.

1. 해당 리스트의 최솟값을 찾는다.

2. 리스트의 맨 처음 인덱스와 교환한다.

3. 교환한 인덱스를 제외한 리스트에서 최솟값을 찾고 정렬된 인덱스를 제외한 맨 앞 인덱스와 교환한다.

 

알고리즘은 어렵지 않은 정렬 방식입니다.

 

자바로 구현한 코드를 보겠습니다.

public class Select_sort {

    public static void main(String[] args) {
        int[] array = new int[10];

        //배열에 난수 저장
        for(int i=0; i<array.length; i++){
            array[i] = (int)(Math.random()*100);
        }

        //정렬전 배열
        for(int i=0; i<array.length; i++){
            System.out.printf("%d ",array[i]);
            if((i+1)%10 == 0){
                System.out.println();
            }
        }

        //선택 정렬
        selection_sort(array);

        System.out.println();
        System.out.println();

        //정렬후 배열
        for(int i=0; i<array.length; i++){
            System.out.printf("%d ",array[i]);
            if((i+1)%10 == 0){
                System.out.println();
            }
        }
    }

    public static void selection_sort(int array[]){
        for(int i=0; i<array.length; i++){
            int min = i;//최솟값은 초기에는 첫 인덱스로 설정
            //저장된 인덱스를 제외한 인덱스부터 비교하여 최솟값 탐색
            for(int j=i+1; j<array.length; j++){
                //최솟값 변경
                if(array[min] > array[j]){
                    min = j;
                }
            }
            
            //최솟값과 해당 인덱스를 변경
            swap(array,i,min);
        }
    }

    public static void swap(int[] array, int i, int min){
        int temp = array[i];
        array[i] = array[min];
        array[min] = temp;

    }
}

 

결과 값

 

선택정렬의 코드와 정렬 과정은 어렵지 않습니다. 코드와 그림을 보고 충분히 이해하실 수 있을 거라고 생각합니다.

 

선택정렬의 장단점입니다.

 

장점

1. 메모리가 추가적으로 필요하지 않다.

 

단점

1. 시간복잡도가(N²)이다. 보통 너무 느려 사용하지 않는 정렬이다.

2. 안정정렬이 아니다.