QuickSort

Quick Sort

Algorithm

quickSort(array, low, high):
    if (low < high){
        pi = partition(array, low, high);
        quickSort(arr, low, pi);
        quickSort(arr, pi + 1, high);
    }

partition(arr, low, high):
    pivot = array[low];
    i = low;
    j = high;
    while (i < j){
        do{
            i += 1;
        } while(array[i] <= pivot);
        do{
            j += 1;
        } while(array[j] > pivot);
        if (i < j){
            swap(array[i], array[j]);
        }
    }
    swap(array[low], array[j]);
    return j;

Complexity

• Time:
  • Worst Case:
  • Average Case:
  • Best Case:
• Space:
  • Worst Case: