[모각코 3주차 개인블로그] 정렬

1. 버블 정렬 (Bubble Sort)

• 정의: 인접한 두 요소를 비교하면서 필요에 따라 위치를 교환하여 정렬하는 알고리즘.

• 자바 예제코드:

    public class BubbleSort {
        public static void bubbleSort(int[] arr) {
            int n = arr.length;
            for (int i = 0; i < n-1; i++) {
                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;
                    }
                }
            }
        }
  
        public static void main(String[] args) {
            int[] arr = {64, 34, 25, 12, 22, 11, 90};
            bubbleSort(arr);
            System.out.println("Sorted array:");
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
        }
    }

2. 삽입 정렬 (Insertion Sort)

• 정의: 각 요소를 적절한 위치에 삽입하여 정렬하는 알고리즘.

• 자바 예제코드:

    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;
                while (j >= 0 && arr[j] > key) {
                    arr[j + 1] = arr[j];
                    j = j - 1;
                }
                arr[j + 1] = key;
            }
        }
  
        public static void main(String[] args) {
            int[] arr = {64, 34, 25, 12, 22, 11, 90};
            insertionSort(arr);
            System.out.println("Sorted array:");
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
        }
    }

3. 퀵 정렬 (Quick Sort)

• 정의: 분할 정복 방식을 사용하여 배열을 정렬하는 알고리즘.

• 자바 예제코드:

    public class QuickSort {
        public static void quickSort(int[] arr, int low, int high) {
            if (low < high) {
                int pi = partition(arr, low, high);
                quickSort(arr, low, pi - 1);
                quickSort(arr, pi + 1, high);
            }
        }
  
        public 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[] arr = {64, 34, 25, 12, 22, 11, 90};
            int n = arr.length;
            quickSort(arr, 0, n - 1);
            System.out.println("Sorted array:");
            for (int i = 0; i < n; ++i) {
                System.out.print(arr[i] + " ");
            }
        }
    }