CPT 102_ LEC 18

1. Merge Sort

see INT 102_Lec 04

2. QuickSort

2.1. Info

2.1.1. Basic

• Invented by C.A.R. Hoare
• Used more widely than others
• works well for different types of data
• divide & conquer on sorting

2.1.2. Time Complexity

• Average        O(N log N)
• Worst            O(N^2)

2.2. Idea

• partition the array into two parts
• partitioning involves the selection of a[i] where the following conditions are met
  • a[i] is in its final place in the array for some i
  • none in a[1], ... , a[i-1] is greater than a[i]
  • none in a[i+1], ... , a[r] is less than a[i] 
• apply quicksort recursively to each part independently

2.3. Java

• class Quick{
      int[]target;
  
      public Quick(int[] target) {
          this.target = quickSort(target,0,target.length-1);
      }
  
      public int[] quickSort(int[] arr,int left,int right){
          if (left < right) {
              int partitionIndex = partition(arr, left, right);
              quickSort(arr, left, partitionIndex - 1);
              quickSort(arr, partitionIndex + 1, right);
          }
          return arr;
      }
  
      //  Partition 
      private int partition(int[] arr, int left, int right) {
          //  Set reference value （pivot）
          int pivot = left;
          int index = pivot + 1;
          for (int i = index; i <= right; i++) {
              if (arr[i] < arr[pivot]) {
                  swap(arr, i, index);
                  index++;
              }
          }
          swap(arr, pivot, index - 1);
          return index - 1;
      }
  
      private void swap(int[] arr, int i, int j) {
          int temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
      }
  
      @Override
      public String toString() {
          System.out.println("Quick Sort");
          System.out.println("-------------------------");
          System.out.println("After Sorting\t\t" + Arrays.toString(target));
          return "";
      }
  }