버블 정렬:

버블 정렬은 배열을 반복적으로 순회하며 두 개의 요소를 비교하고 필요에 따라 교환하는 과정을 통해 정렬을 수행합니다. 이 과정이 배열이 정렬될 때까지 계속됩니다.

특징: 비교적 안정적이며, 작은 크기의 배열에서 잘 작동합니다.

package sorting.example;

public class BubbleSortExample {
    private static boolean validateArray(int[] array) {
        return array != null && array.length > 0;
    }

    public static int[] bubbleSort(int[] array) {
        if (!validateArray(array)) {
            return null;
        }
        int swapCount = 0;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapCount++;
                }
            }
        }
        System.out.println("총 교환 횟수: " + swapCount);
        return array;
    }

    public static void main(String[] args) {
        int[] numbers = {8, 4, 9, 13, 11, 99, 2, 1, 5, 3, 6};
        bubbleSort(numbers);
        for (int num : numbers) {
            System.out.print(num + ",");
        }
    }
}

선택 정렬:

선택 정렬은 배열에서 가장 작은 값을 찾아 첫 번째 위치에 배치하고, 다음으로 작은 값을 찾아 두 번째 위치에 배치하는 방식으로 진행됩니다. 이 알고리즘은 입력 데이터와 상관없이 항상 동일한 시간 복잡도를 가집니다.

특징: 데이터 이동이 최소화되지만, 불안정하며 작은 크기의 배열에서 효과적입니다.

package sorting.example;

public class SelectionSortExample {
    public static int[] selectionSort(int[] array) {
        int swapCount = 0;
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
                swapCount++;
            }
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
        System.out.println("총 교환 횟수: " + swapCount);
        return array;
    }

    public static void main(String[] args) {
        int[] numbers = {8, 4, 9, 13, 11, 99, 2, 1, 5, 3, 6};
        selectionSort(numbers);
        for (int num : numbers) {
            System.out.print(num + ",");
        }
    }
}

삽입 정렬:

삽입 정렬은 배열의 처음 두 요소부터 시작하여 정렬된 상태를 유지하면서 다음 요소를 삽입하는 방식으로 진행됩니다. 이미 정렬된 부분과 비교하여 적절한 위치에 삽입됩니다.

특징: 안정적이며 대부분의 경우 이미 정렬된 배열에서는 매우 효율적입니다.

package sorting.example;

public class InsertionSortExample {
    public static int[] insertionSort(int[] array) {
        int insertCount = 0;
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
                insertCount++;
            }
            array[j + 1] = key;
        }
        System.out.println("총 삽입 횟수: " + insertCount);
        return array;
    }

    public static void main(String[] args) {
        int[] numbers = {8, 4, 9, 13, 11, 99, 2, 1, 5, 3, 6};
        insertionSort(numbers);
        for (int num : numbers) {
            System.out.print(num + ",");
        }
    }
}