[Java] 선택정렬 & 버블정렬 & 삽입정렬

선택정렬

해당 위치에 들어갈 원소를 결정한다.

배열 예시

위와 같은 배열을 오름차순으로 정렬하고자 할 때 i의 index를 0에 고정하고 j의 index를 1부터 끝까지 순회하면서 가장 작은 값을 index 0에 배치한다.

그 다음 i의 index를 1에 고정하고 j의 index를 2부터 끝까지 순회하면서 가장 작은 값을 index 1에 배치한다. 위 과정을 반복하게 되면 배열은 결국 오름차순으로 정렬이 된다.

public class Main {
    public int[] solution(int[] input) {
        for (int i = 0; i < input.length - 1; i++) {
            int minIdx = i;
            for (int j = i + 1; j < input.length; j++) {
                if (input[minIdx] > input[j]) {
                    minIdx = j;
                }
            }
            int tmp = input[i];
            input[i] = input[minIdx];
            input[minIdx] = tmp;
        }
        return input;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] input = new int[N];
        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }

        int[] result = T.solution(input);
        for (int i : result) {
            System.out.print(i + " ");
        }
    }
}

결과

결과

내림차순의 경우 부등호 방향을 바꿔주면 된다.

---

버블정렬

버블정렬은 자기 자신의 옆에 있는 값과 비교하며 순서를 바꿔나가는 정렬 방식이다.

배열 예시

위와 같은 배열을 오름차순으로 정렬할 때 다음과 같이 자신의 옆에 있는 값과 비교하여 바꿔나가는 방식이다.

첫번째 반복

두 번째 반복

위와 같이 정렬되기 때문에 가장 뒤쪽의 index부터 정렬이 된다.

public class Main {
    public int[] solution(int[] input) {
        for (int i = 0; i < input.length - 1; i++) {
            for (int j = 0; j < input.length - i - 1; j++) {
                if (input[j] > input[j + 1]) {
                    int tmp = input[j];
                    input[j] = input[j + 1];
                    input[j + 1] = tmp;
                }
            }
        }
        return input;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] input = new int[N];
        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }

        int[] result = T.solution(input);
        for (int i : result) {
            System.out.print(i + " ");
        }
    }
}

위와 같은 배열은 두번만에 정렬이 완료되었지만 내림차순으로 정렬되어 입력되었을 때는 다음과 같이 정렬될 수 있다.

내림차순으로 정렬하고자 할때에는 선택정렬과 마찬가지로 부등호 방향을 바꿔주면 된다.

---

삽입정렬

삽입정렬은 i의 index를 1부터 두고 j의 index를 i-1부터 0까지 순회하면서 i의 index에 해당하는 값을 적절한 자리에 삽입하는 정렬 방식이다.

배열 예시

위와 같은 배열에서 정렬을 해 나아가면 다음과 같다.

정렬 과정

public class Main {
    public int[] solution(int[] input) {
        for (int i = 1; i < input.length; i++) {
            int target = input[i], j = i - 1;
            while (j >= 0 && target < input[j]) {
                input[j + 1] = input[j];
                j--;
            }
            input[j + 1] = target;
        }
        // 아래와 같은 방식도 가능하다
//        for (int i = 1; i < input.length; i++) {
//            int tmp = input[i], j;
//            for (j = i - 1; j >= 0; j--) {
//                if (input[j] > tmp) {
//                    input[j + 1] = input[j];
//                } else {
//                    break;
//                }
//            }
//            input[j + 1] = tmp;
//        }
        return input;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] input = new int[N];
        for (int i = 0; i < N; i++) {
            input[i] = sc.nextInt();
        }

        int[] result = T.solution(input);
        for (int i : result) {
            System.out.print(i + " ");
        }
    }
}

결과

결과