정렬 (합병, 힙, 퀵)

합병 정렬 구현하기

import java.util.Arrays;

public class Main {
    
    public static void mergeSort(int[] arr, int[] tmp, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, tmp, left, mid);
            mergeSort(arr, tmp, mid + 1, right);
            merge(arr, tmp, left, right, mid);
        }
    }

    public static void merge(int[] arr, int[] tmp, int left, int right, int mid) {
        int p = left;
        int q = mid + 1;
        int idx = p;

        while (p <= mid || q <= right) {
            if (p <= mid && q <= right) {
                if (arr[p] <= arr[q]) {
                    tmp[idx++] = arr[p++];
                } else {
                    tmp[idx++] = arr[q++];
                }
            } else if (p <= mid && q > right) {
                tmp[idx++] = arr[p++];
            } else {
                tmp[idx++] = arr[q++];
            }
        }
        for (int i = left; i <= right; i++) {
            arr[i] = tmp[i];
        }
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {3, 5, 2, 7, 1, 4, 6};
        int[] tmp = new int[arr.length];
        mergeSort(arr, tmp, 0, arr.length - 1);
        System.out.println("합병 정렬: " + Arrays.toString(arr));
    }
}

1. mergeSort 함수
   -배열을 반으로 나누어 왼쪽과 오른쪽 부분 배열을 재귀적으로 정렬
   -left와 right는 현재 정렬할 부분 배열의 시작과 끝 인덱스를 나타냄
   -mid는 중간 인덱스로, 배열을 두 부분으로 나누기 위해 사용

2.merge 함수
-두 개의 정렬된 부분 배열을 병합
-p 와 q 는 각각 왼쪽 부분 배열과 오른쪽 부분 배열의 시작 인덱스를 나타냄
-tmp 배열은 병합된 결과를 임시로 저장하기 위해 사용됨
-병합이 완료되면 tmp 배열의 내용을 원래 배열 arr에 복사

3. 시간복잡도 : O(nlogn)

힙 정렬 구현하기

import java.util.Arrays;

public class Main2 {
    
    public static void heapSort(int[] arr) {
        for (int i = arr.length / 2 - 1; i >= 0 ; i--) {
            heapify(arr, i, arr.length);
        }
        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, 0, i);
        }
    }

    public static void heapify(int[] arr, int parentIdx, int size) {
        int leftIdx = 2 * parentIdx + 1;
        int rightIdx = 2 * parentIdx + 2;
        int maxIdx = parentIdx;

        if (leftIdx < size && arr[maxIdx] < arr[leftIdx]) {
            maxIdx = leftIdx;
        }

        if (rightIdx < size && arr[maxIdx] < arr[rightIdx]) {
            maxIdx = rightIdx;
        }
        if (parentIdx != maxIdx) {
            swap(arr, maxIdx, parentIdx);
            heapify(arr, maxIdx, size);
        }

    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {3, 5, 2, 7, 1, 4, 6};
        heapSort(arr);
        System.out.println("힙 정렬: " + Arrays.toString(arr));
    }
}

1. heapSort 함수
   -배열을 최대 힙으로 변환. 이는 배열의 절반 길이부터 시작하여 각 부모 노드를 대상으로 heapify를 호출하여 이루어짐
   -힙 에서 루트 요소(최대값)를 배열의 끝으로 이동시킨 후, 배열 크기를 줄이고 heapify를 호출하여 다시 최대 힙을 유지. 이를 배열 크기가 1이 될 때까지 반복

2. heapify 함수
   -주어진 부모 노드와 그 자식 노드들 간의 관계를 비교하여 최대 힙을 유지. 필요 시 부모 노드와 자식 노드를 교환하고, 재귀적으로 호출하여 최대 힙 구조를 만듬

3. swap 함수
   -배열의 두 요소를 교환

4. 시간복잡도 : O(n log n)

퀵 정렬 구현하기

import java.util.Arrays;

public class Main3 {

    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivot = partition(arr, left, right);

        quickSort(arr, left, pivot - 1);
        quickSort(arr, pivot + 1, right);
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left;
        int j = right;

        while (i < j) {
            while (arr[j] > pivot && i < j) {
                j--;
            }
            while (arr[i] <= pivot && i < j) {
                i++;
            }
            swap(arr, i, j);
        }
        swap(arr, left, i);

        return i;
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {6, 2, 7, 9, 4, 5, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("퀵 정렬: " + Arrays.toString(arr));
    }
}

1. quickSort 함수
   -주어진 배열을 왼쪽과 오른쪽 인덱스 사이의 범위 내에서 정렬
   -partition 함수를 호출하여 배열의 피벗을 기준으로 두 부분으로 나눈 후, 두 부분에 대해 재귀적으로 quickSort를 호출

2. partition 함수
   -배열의 첫 요소를 피벗으로 설정하고, 배열의 왼쪽과 오른쪽에서 피벗보다 큰 요소와 작은 요소를 찾아 교환
   -교환이 완료되면 피벗을 올바른 위치로 이동시키고 그 위치를 반환

3. swap 함수
   -배열의 두 요소를 교환

4. 피벗 선택
   -현재 코드에서는 배열의 첫번째 요소를 피벗으로 선택했지만, 피벗 선택방법은 다양할수 있으며, 피벗 선택이 퀵 정렬의 성능에 영향을 미칠 수 있음.

5. 분할과정
   -배열의 왼쪽에서 시작하는 포인터 i 와 오른쪽에서 시작하는 포인터 j를 사용하여 피벗보다 큰 요소와 작은 요소를 찾음
   -i 와 j 가 서로 교차하지 않는 한 요소를 교환
   -i 와 j 가 교차하면 피벗을 올바른 위치로 이동시키고 그 위치를 반환

6. 재귀호출
   -partiotion 함수가 반환한 피벗 위치를 기준으로 배열을 두 부분으로 나누고, 각각에 대해 재귀적으로 quickSort를 호출

7. 시간복잡도 : 평균적으로는 O(n log n) 이지만, 최악의 경우엔 O(n^2) 가 됨. 그러나 일반적으로 퀵정렬은 대부분의 경우에 빠르게 동작함