설명

N개이 숫자가 입력되면 오름차순으로 정렬하여 출력하는 프로그램을 작성하세요.

정렬하는 방법은 선택정렬입니다.

코드

public class SelectSort {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int input1 = in.nextInt();
        int[] arr = new int[input1];
        for(int i=0; i<input1; i++){
            arr[i] = in.nextInt();
        }

        solution(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    public static void solution(int[] arr){
        int idx = 0;
        while(idx < arr.length){
            for(int i=idx+1; i<arr.length; i++){
                if(arr[i]<arr[idx]) swap(arr, idx, i);
            }
            idx++;
        }
    }
    public static void swap(int[] arr, int m, int k){
        int temp = arr[m];
        arr[m] = arr[k];
        arr[k] = temp;
    }
}

선택정렬을 구현한 코드이다. 2중 for문을

for(int i=0; i<length; i++){
	for(int j=0; j<length; j++){
    }
}

로 구현해도 상관 없으나 내가 선택 정렬을 공부할때 위와 같은 방법으로 구현된 코드는 내 머릿속에서 작동하질 않더라... 그래서 일부러 idx와 두개의 반복문을 구분해보기 위해 while과 for로 구현했다. 그리고 swap 부분도 따로 빼놨는데. 정렬 부분과 배열의 위치를 변경하는 부분을 분리해서 작성하는게 눈에 보기 쉬워서 이렇게 작성했다. swap method 대신 아래 값들을 그대로 옮겨서 사용해도 무방하다.

선택 정렬은 배열의 가장 앞에서부터 오름차순의 경우 가장 작은 값부터 차례대로 채워서 넣는 정렬이다.

장점

• 구현이 쉽고 로직을 이해하기 쉽다.

단점

• 시간 복잡도가 최악, 최선 O(N^2)으로 오래 걸린다.
• 값이 같을 경우 비교했을 때 불안정 정렬이다.

여기서 불안정 정렬과 안정 정렬이 무엇일까? 고민할 수 있다.

안정 정렬

• 정렬 후에도 값의 순서가 유지된다.

불안정 정렬

• 정렬 후에 값의 순서가 유지된다는 보장을 할 수 없다.

라는 차이점이 있는데 도대체 값의 순서가 무엇이고 순서를 유지한다? 유지한다고 보장할 수 없다? 차이는 무엇일까?

예를 들어
{2(0),2(1),1,3}
라는 배열을 오름차순으로 정렬할때 2라는 값은 중복되므로 우리가 알아볼 수 있게 (0)과 (1)로 표시해놨다. 위의 코드로 실행했을 했을 때

1번 실행했을 때
{1,2(1),2(0),3}
으로 정렬이 되고 이후에 정렬을 실행해도 정렬이 완료되었으므로 다음과 같이 종료된다. 이렇게 바로 이웃한 값을 비교하지 않고 기준보다 멀리 떨어진 배열의 값과 비교하는 정렬은 불안정 정렬이 되는데 위와 같이 2(0)과 2(1)의 순서가 보장될 수 없기 때문이다. 원래 순서대로라면 {1,2(0),2(1),3} 으로 정렬이 되어야 안정 정렬인데 선택 정렬은 값을 기준으로 자신과 이웃한 값으로 비교하는 정렬이 아니므로 불안정 정렬이라고 할 수 있다.