합병, 힙 vs 퀵 정렬(Quick sort)

정렬 종류

참고 : http://hsp1116.tistory.com/33

선택, 삽입, 버블, 합병(merge), 퀵, 힙 정렬이 있지만 이 중에서 성능이 뛰어난 합병, 퀵, 힙을 비교하고

결국 왜 퀵이 제일 빠른지를 설명한다.

퀵 정렬 vs 힙 정렬

참고 : https://brunch.co.kr/@k2u4yt/3

위의 블로그가 정말 자세하게 나와있다. 보시다시피 성능비교에서 퀵 정렬이 우세한 것을 볼 수 있는데,

이는 두 정렬이 얼마나 swap을 하는지에 달려있다. (퀵 정렬의 swap 횟수가 현저히 낮다.)

퀵 정렬에서 최악의 경우가 O(n^2) 이고 힙은 최악이든 최선이든 O(NlogN)이지만 swap의 횟수 때문에 퀵이 더 빠른것을 알 수 있다.

퀵 정렬 vs 합병 정렬

참고 : http://penpen.tistory.com/entry/Algorithm-Quick-Sort-Merge-Sort-%EB%B9%84%EA%B5%90%EC%B2%B4%ED%97%98

 위의 블로그는 정말 대박인게 직접 손수 비교를 해주셔서, 어떤 정렬이 더 우세한지 수치상으로 나타내준다.

합병 정렬도 고루고루 O(NlogN)이고, 퀵 정렬은 최악의 시간 복잡도가 O(N^2)인데, 어째서 모든 경우에 퀵 정렬이 우세하다고 나올까?

위의 블로그에도 나와있겠지만, 조금 더 구글링 한 결과 합병 정렬은 "배열을 생성하는" 시간이 있기 때문이다.

이는, 정렬하고자 하는 배열의 길이가 길면 길수록 차이가 난다.

Quick Sort Code

 
public class quickSortClass {
    public static void main(String[] args) {
        int[] arr = {11,4,8,5,9,21,7,15,1,13};
        
        quickSort(arr, 0, arr.length - 1);
 
        for (int i : arr) 
            System.out.print(i+ " ");
        
    }
 
    public static void quickSort(int[] arr, int low, int high) {
 
        int middle = (high + low) / 2;
        int pivot = arr[middle];
 
        int i = low, j = high; // i : low의 포인터, j : high의 포인터
        int temp;
 
        while (i <= j) {
            System.out.print("(low,high,i,j,middle : "+ low + "," + high + "," + i + ","+ j + "," + middle + ") ");
            
            while (arr[i] < pivot) // pivot보다 작은 구간에서 pivot보다 값이 작으면 넘기기
                i++;
            while (arr[j] > pivot) // pivot보다 큰 구간에서 pivot보다 값이 크면 넘기기
                j--;

            // 만일 조건에 맞지 않은 i,j가 나오면 while문에서 벗어나 i,j값으로 뭔갈 하겠지.
 
            if (i <= j) { // while문에서 나온 i와 j값이 교차하지 않았다면(만나지 않았다면)
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp; // swap
                i++; 
                j--; // i(low의 포인터)는 오른쪽으로, j(high의 포인터)는 왼쪽으로 진행
            }
            
            for(int k : arr) 
                System.out.print(k + " ");
            System.out.println();
            
        } // 이 while문에서 벗어났다는 얘기는, i>j라는 뜻이며 
          // low 포인터가 high 포인터보다 더 high쪽에 있다는 이야기.
        
        if (low < j) // low~j까지 구간에서 원소가 2개 이상이면,
            quickSort(arr, low, j);
        
        if (high > i) // i~high까지 구간에서 원소가 2개 이상이면,
            quickSort(arr, i, high);
 
    }
}

* 메카니즘에 대한 주석때문에 조금 지저분해 보이지만, 구글링해서 여러 퀵 정렬 코드를 본 결과

 가장 깔끔함. 그만큼 이해하기가 다른 코드들에 비해 조금 어려워서 주석을 달았음.

* 메카니즘은 다른 퀵정렬과 비슷함.

* 이해하기 어렵다면 main에 있는 배열을 가지고 손으로 직접 하는것이 제일 도움 됨.

그렇게 하라고 중간중간에 디버그용 log를 남김.

우선 돌려놓고, 콘솔창에 뜬 log와 내가 손으로 직접 하는 것과 비교해가면서 하면 이해가 될 것.