[Java][알고리즘][정렬] Selection Sort / 선택 정렬

정렬에 대해서 쭉 포스팅을 시작하겠다!

선택 정렬

선택정렬은 배열에서 아직 정렬되지 않은 부분의 원소 중에서 최솟값을 찾아 정렬된 부분의 바로 오른쪽 원소와 교환하는 알고리즘이다.

 

따라서 for문을 돌면서 min을 i번째로 설정하고 정렬이 안된 부분에서 최솟값을 찾아 교환해주면 된다.

모든 요소에 대해 i를 정하고 정렬 안된 부분이 하나씩 줄어들면서 계속 비교하므로 시간 복잡도는 O(N^2)이 된다. 

가장 기본적인 정렬이지만 시간 복잡도가 좋지는 않으니 거의 사용하지 않는다.

 

코드

public class Selection {
    
    public static boolean isless(Comparable a, Comparable b) {
        return a.compareTo(b) < 0;
    }
    
    public static void swap(Comparable[] arr, int i,int j) {
        Comparable p = arr[i];
        arr[i] = arr[j];
        arr[j] = p;
    }
    
    public static void show(Comparable[] arr) {
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    public static void Sort(Comparable[] arr) {
        for(int i=0; i<arr.length; i++) {
            int min = i;
            for(int j=i+1; j<arr.length; j++) {
                if(isless(arr[j],arr[min])) {
                    min = j;
                }
            }
            swap(arr,i,min);
            show(arr);
        }
    }
}
 

static를 쓴 이유는 Main문에서 바로 접근하기 위해서다. 포스팅을 위해 따로 class를 만들었으나 실제로는 바로 Main문에 쓰면 된다.