Sorting

Quick Sort

Is one of the fastest sorting algorithms , it starts by choosing a pivot element and then moving all the elements lower than the pivot to the left of the pivot and all the elements higher than the pivot to the right of the pivot. After that we make a recursive call twice, one for the left side and the other for the right side. In this recursive call the algorithms are going to repeat the same thing until the dataset is sorted. video shows how the algorithm works

Big(O)

| | speed | | -------- | ------- | | Best | O(n logn) | | Average | O(n logn) | | Worst | O(n^2) |

Implementation

function quickSort(data){
  if(data.length<=1){
    return data;
  }
  let pivot = data[0];
  let left = [];
  let right = [];
  for(let i=1;i<data.length;i++){
    if(data[i]<pivot){
      left.push(data[i]);
    }else{
      right.push(data[i]);
    }
  }
  return [...quickSort(left),pivot,...quickSort(right)];
}