Skip to content

Instantly share code, notes, and snippets.

@danielrobertson

danielrobertson/QuickSort.java

Created July 10, 2016 23:15
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save danielrobertson/73f279e4482dffef49bce79505f87e47 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save danielrobertson/73f279e4482dffef49bce79505f87e47 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. danielrobertson created this gist Jul 10, 2016.
    29 changes: 29 additions & 0 deletions QuickSort.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,29 @@
    void quickSort(int arr[], int left, int right) { //Confirmed
    int index = partition(arr, left, right);
    if (left < index - 1) { //when sorting 2 3 1, will return 2 1 3, left point at 3 and 2 1 unsorted
    quickSort(arr, left, index - 1);
    }
    if (index < right) { //when sorting 3 1 2, will return 1 3 2, index at 3 and right is 2.
    quickSort(arr, index, right);
    }
    }

    int partition(int arr[], int left, int right) {
    int pivot = arr[(left + right) / 2];
    while (left < right) { //1. left -> 2, right -> 3 2. left -> 2, right -> 2. Be clear with these two cases, and know how do decide comparison in quickSort();
    while (arr[left] < pivot)
    left++; //cannot write while (arr[left++] < pivot);
    while (arr[right] > pivot)
    right--;
    if (left < right) {
    swap(arr, left++, right--);
    }
    }
    return left; //when return, we want left to point at a number > pivot. and all orgin_left : left - 1 <= pivot.
    }

    void swap(int arr[], int left, int right) {
    int tmp = arr[left];
    arr[left] = arr[right];
    arr[right] = tmp;
    }