Quick Sort

quicksort.c

void swap(int& a, int& b)
{
  int temp = a;
  a = b;
  b = temp;
}

void partition(int * arr, int left, int right)
{
  int pivotValue = arr[right];
  int pos = left -1;  // This is the position in the subarray where the pivot should be present
  
  for (int j = left; j < right; j++)
  {
    if (arr[j] < pivotValue)
    {
      //This means that this element should be on the left of the pivot
      pos++;
      // we need to move the pivot right so we swap with this element the pivot position
      swap (arr[pos],arr[j]);
    }
  }
  //At this point the pos is pointing to the position just before the pivot
  swap(arr[pos+1], arr[right]);
  return (pos+1);
}

void quickSort(int* arr, int left, int right)
{
  if (left < right)
  {
    int pos = partition(arr, left, right);
    
    quickSort(arr,left, (pos - 1));
    quickSort(arr, (pos+1), right);
  }
}