[Java] 정렬 알고리즘

자주 쓰이는 정렬 알고리즘 정리.

각 알고리즘은 설명, 순서도, Java 코드로 구성되어 있음. 

---

✅ 1. 버블 정렬 (Bubble Sort)

🔍 알고리즘 설명

• 인접한 두 원소를 비교하여 큰 값을 뒤로 보내는 방식임.
• 한 번 순회를 마칠 때마다 가장 큰 값이 뒤로 "정렬"됨.
• 시간 복잡도는 O(n²)임.

📈 순서도

1. 배열을 순회하며 인접한 원소 비교
2. 크기 순서가 잘못되었으면 교환
3. 이 과정을 n-1회 반복

💻 Java 코드

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        // 배열 전체를 순회함
        for (int i = 0; i < n - 1; i++) {
            // 마지막 i개의 요소는 이미 정렬되어 있음
            for (int j = 0; j < n - 1 - i; j++) {
                // 인접한 두 요소 비교 후 교환
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];       // 임시 변수에 저장
                    arr[j] = arr[j + 1];     // 작은 값을 앞으로
                    arr[j + 1] = temp;       // 큰 값을 뒤로
                }
            }
        }
    }

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

---

✅ 2. 선택 정렬 (Selection Sort)

🔍 알고리즘 설명

• 매 반복마다 가장 작은 값을 선택해서 앞쪽에 위치시킴.
• 시간 복잡도는 O(n²)임.
• 교환 횟수가 적고 단순함.

📈 순서도

1. 현재 위치에서 가장 작은 값 탐색
2. 해당 값을 현재 위치의 값과 교환
3. 반복

💻 Java 코드

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

        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;  // 가장 작은 값의 인덱스

            // i 이후의 값들 중 최소값 찾기
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // 현재 위치(i)와 최소값 위치(minIndex) 교환
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {64, 25, 12, 22, 11};
        selectionSort(numbers);
        for (int num : numbers) {
            System.out.print(num + " ");
        }
    }
}

---

✅ 3. 삽입 정렬 (Insertion Sort)

🔍 알고리즘 설명

• 현재 값을 정렬된 부분의 적절한 위치에 "삽입"하는 방식임.
• 시간 복잡도는 O(n²)이나, 거의 정렬된 배열에 대해서는 효율적임.

📈 순서도

1. 두 번째 원소부터 시작
2. 현재 원소를 앞쪽 정렬된 부분에 삽입
3. 전체 배열을 순차적으로 수행

💻 Java 코드

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

        for (int i = 1; i < n; 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;  // 올바른 위치에 삽입
        }
    }

    public static void main(String[] args) {
        int[] numbers = {12, 11, 13, 5, 6};
        insertionSort(numbers);
        for (int num : numbers) {
            System.out.print(num + " ");
        }
    }
}

---

✅ 4. 병합 정렬 (Merge Sort)

🔍 알고리즘 설명

• 분할 정복(Divide & Conquer) 방식의 정렬임.
• 배열을 반으로 나누고, 각 부분을 정렬한 뒤 병합함.
• 시간 복잡도는 O(n log n)으로 효율적임.

📈 순서도

1. 배열을 반으로 나눔
2. 각각 정렬
3. 두 부분을 병합

💻 Java 코드

public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr.length < 2) return;

        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];

        // 배열을 반으로 분할
        for (int i = 0; i < mid; i++) left[i] = arr[i];
        for (int i = mid; i < arr.length; i++) right[i - mid] = arr[i];

        // 재귀적으로 정렬
        mergeSort(left);
        mergeSort(right);

        // 정렬된 두 배열 병합
        merge(arr, left, right);
    }

    public static void merge(int[] arr, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;

        // 작은 값을 먼저 병합
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) arr[k++] = left[i++];
            else arr[k++] = right[j++];
        }

        // 남은 값 병합
        while (i < left.length) arr[k++] = left[i++];
        while (j < right.length) arr[k++] = right[j++];
    }

    public static void main(String[] args) {
        int[] numbers = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(numbers);
        for (int num : numbers) {
            System.out.print(num + " ");
        }
    }
}

---

✅ 5. 퀵 정렬 (Quick Sort)

🔍 알고리즘 설명

• 분할 정복 방식으로, 피벗을 기준으로 작은 값과 큰 값을 나눔.
• 평균 시간 복잡도는 O(n log n), 최악은 O(n²)이지만 매우 빠름.

📈 순서도

1. 피벗 선택
2. 피벗보다 작은 값, 큰 값 분리
3. 재귀적으로 정렬

💻 Java 코드

public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);

            // 피벗 기준 왼쪽과 오른쪽 정렬
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // 마지막 요소를 피벗으로 사용
        int i = low - 1;

        for (int j = low; j < high; j++) {
            // 피벗보다 작으면 왼쪽으로 이동
            if (arr[j] < pivot) {
                i++;
                // 값 교환
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // 피벗을 올바른 위치로 이동
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        int[] numbers = {10, 7, 8, 9, 1, 5};
        quickSort(numbers, 0, numbers.length - 1);
        for (int num : numbers) {
            System.out.print(num + " ");
        }
    }
}

 

 

 

참고 :

https://visualgo.net/en/sorting

https://www.toptal.com/developers/sorting-algorithms

https://prepinsta.com/java-program/bubble-sort/