삽입정렬, 선택정렬, 버블정렬

1. 삽입 정렬 (Insertion Sort)

두번째 값부터 이전 값들과 비교를 시작한다.

비교하는 값을 Key라고 할 때, 순서를 변경해야 한다면 Key를 변경 할 자리에 삽입하고 그 자리에 있던 값은 뒤로 한 칸 이동 시킨다.

예시 "85624"

1. key = 5 : 85624 -> 58624
2. key = 6 : 58624 -> 56824 
3. key = 2 : 56824 -> 25674
4. key = 4 : 25684 -> 24568

public class InsertionSort {
    public static void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;

            // key보다 큰 값을 오른쪽으로 한 칸씩 이동
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

삽입 정렬은 현재 위치의 원소가 정렬된 앞부분의 원소들과 비교되며, 자신보다 큰 원소들은 한 칸씩 뒤로 밀려나고, 그 자리에 현재 원소가 삽입되는 방식으로 동작한다. 예를 들어 3회전에서, 현재 비교 중인 값이 1이고 그 앞의 값이 6이라면 6은 뒤로 밀려나고, 1이 그 자리에 삽입된다.
이때 1<6 가 확인되면, 1 앞의 값들은 이미 정렬되어 있고 6보다 작거나 같기 때문에 더 이상 비교하지 않아도 된다.
이러한 방식은 앞쪽에서 순서를 유지하며 삽입하는 구조이므로, 같은 값을 가진 원소가 있을 경우 원래의 순서가 유지된다.
따라서 삽입 정렬은 선택 정렬과 달리 안정 정렬에 해당한다.

2. 선택 정렬 (Selection Sort)

처음 원소 자리부터 순서대로 모든 값들을 검사하여 작은 순서대로 정렬하는 방법

매 회전마다 최솟값(또는 최댓값)을 찾아 현재 위치와 교환한다.

정렬된 부분과 정렬되지 않은 부분을 구분하여, 하나씩 자리를 채워간다.

예시 "85624"

• 첫번째 원소 자리 : 85624 -> 25684
• 두번째 원소 자리 : 25684 -> 24685
• 세번째 원소 자리 : 24685 -> 24586
• 네번째 원소 자리 : 24586 -> 24568

public class SelectionSort {
    public static void sort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            int minIdx = i;

            // 가장 작은 값의 인덱스 찾기
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }

            // 최소값을 맨 앞(i)과 교환
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }
}

3. 버블 정렬(Bubble Sort)

인접한 두 원소를 비교해 큰 값을 뒤로 보내는 과정을 반복한다.

매 회전마다 가장 큰 값이 맨 뒤로 '버블'처럼 밀려난다.

버블 정렬을 수행하면 1회전마다 가장 큰 숫자가 맨 오른쪽으로 이동하고, 나머지 숫자의 위치에는 변화가 없다.

public class BubbleSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        boolean swapped;

        for (int i = 0; i < n - 1; i++) {
            swapped = false;

            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }

            // 더 이상 바꿀 게 없다면 종료
            if (!swapped) break;
        }
    }
}

참고 자료

• chatGPT
• https://gmlwjd9405.github.io/2018/05/06/algorithm-bubble-sort.html
• 시나공 정보처리기사 실기