[Sort] Quick Sort

Complexity

time complexity => best: nlogn
space complexity => best:

code

// arr = [4, -1, -2, 3, 1, -3, 0]

// need quicksort function
function quickSort(arr, l, r)
{
  	if (l < r)
    {
      // partition array
      let p = partition(arr, l, r); // [-1, -2, -3, 0, 3, 1, 4], p=3, arr[p] = 0
      quickSort(arr, l, p - 1); // [-1, -2, -3]
      quickSort(arr, p + 1, r); // [3, 1, 4]
    }
}


// need partition function to sort based on pivot element;
// return pivot index
fuction partition(arr, l, r) 
{
  // need pivot base
  // there are many ways to pick a point
  //  - pick random 3 and use median of them
  //  - just random pick
  // we use right end element for the base pivot index
  let pivot  = arr[r];

  // let i be tracking an index of the latest element, which is smaller than the pivot above
  let i = l - 1;
  // iterate arr with index j
  for (let j = i; j < arr.length - 1; j++) 
  {
    // if current element is smaller than pivot
    if (arr[j] < pivot)
    {
      
    	i++ // increase the index of smaller element
		// swap arr[j] and arr[i]
      	let temp = arr[j];
      	arr[j] = arr[i];
      	arr[i] = temp;
    }
  }
  
  // after the loop, we need to move pivot to i + 1
  let temp = arr[r];
  arr[r] = arr[i + 1];
  arr[i + 1] = temp;
  return i + 1;
}