Sorting

Sorting

O(nlogn)의 복잡도를 가지는 정렬 알고리즘들에는 대표적으로 merge sort, quick sort, heap sort 가 있다.

이번 포스팅에서는 이 알고리즘들에 대해서 공부한다.

Merge Sort

구현된 코드는 아래와 같다.

public class MergeSort {

    void merge(int arr[], int l, int m, int r){
        int n1 = m - l + 1;
        int n2 = r - m;

        int L[] = new int[n1];
        int R[] = new int[n2];

        for(int i=0; i<n1; i++)
            L[i] = arr[l+i];
        for(int j=0; j<n2; j++)
            R[j] = arr[m+1+j];

        int i=0, j=0;

        int k = l;
        while(i < n1 && j < n2){
            if(L[i] <= R[j]){
                arr[k] = L[i];
                i++;
            }else{
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while(i < n1){
            arr[k] = L[i];
            i++;
            k++;
        }

        while(j < n2){
            arr[k] = R[j];
            i++;
            k++;
        }
    }

    void sort(int arr[], int l, int r){
        if(l < r){
            int m = (l+r)/2;
            sort(arr, l, m);
            sort(arr, m+1, r);
            merge(arr, l, m, r);
        }
    }
    //https://www.geeksforgeeks.org/merge-sort/
}

Quick Sort

구현된 코드는 아래와 같다.

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

    static int partition(int[] arr, int low, int high){
        int pivot = arr[high];

        int i = low-1;

        for(int j=low; j<=high-1; j++){
            if(arr[j] < pivot){
                swap(arr, ++i, j);
            }
        }
        swap(arr, i+1, high);
        return i+1;
    }

    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);
        }
    }

    //출처 : https://www.geeksforgeeks.org/quick-sort/
}

Heap Sort

구현된 코드는 아래와 같다.

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

        for(int i=n/2-1; i>=0; i--)
            heapify(arr, n , i);

        for(int i=n-1; i>0; i--){
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr,i,0);
        }
    }

    void heapify(int arr[], int n, int i){
        int largest = i;
        int l = 2*i+1;
        int r = 2*i+2;

        if(l < n && arr[l] > arr[largest])
            largest = l;
        if(r < n && arr[r] > arr[largest])
            largest = r;
        if(largest != i){
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            heapify(arr, n , largest);
        }
    }
    // 출처 : https://www.geeksforgeeks.org/heap-sort/
}