/*algorithm quicksort(A, lo, hi) is 
  // Ensure indices are in correct order
  if lo >= hi || lo < 0 then 
    return
    
  // Partition array and get the pivot index
  p := partition(A, lo, hi) 
      
  // Sort the two partitions
  quicksort(A, lo, p - 1) // Left side of pivot
  quicksort(A, p + 1, hi) // Right side of pivot

// Divides array into two partitions
algorithm partition(A, lo, hi) is 
  pivot := A[hi] // Choose the last element as the pivot

  // Temporary pivot index
  i := lo

  for j := lo to hi - 1 do 
    // If the current element is less than or equal to the pivot
    if A[j] <= pivot then 
      // Swap the current element with the element at the temporary pivot index
      swap A[i] with A[j]
      // Move the temporary pivot index forward
      i := i + 1

  // Swap the pivot with the last element
  swap A[i] with A[hi]
  return i // the pivot index*/

int Partition(int * array, int lo, int hi){
  /*variables*/
  int pivot = array[hi];
  int tmp_ind = lo;
  int tmp;
  int i = 0;

  /*pivots*/
  for(i=lo; i<hi; i++){
    if(array[i]<=pivot){
      tmp = array[i];
      array[i] = array[tmp_ind];
      array[tmp_ind] = tmp;
      tmp_ind++;
    }
  }
  tmp = array[tmp_ind];
  array[tmp_ind] = array[hi];
  array[hi] = tmp;
  return tmp_ind;
}

void quicksort(int * array, int lo, int hi){
  /*variables*/
  int p;

  /*test - indices dans l'ordre*/
  if((lo>=hi)||(lo<0)){
    return;
  }

  p = Partition(array, lo, hi);

  quicksort(array, lo, p-1);
  quicksort(array, p+1, hi);
}