The#sorting-algorithms series is a collection of posts about reimplemented sorting algorithms in JavaScript.
If you are not familiar with sorting algorithms, a quick introduction and the full list of reimplemented sorting algorithms can be found in theintroduction post of the series on sorting algorithms in JavaScript.
If you feel comfortable with the concept of each sorting algorithm and only want to see the code, have a look at the summary post of the series. It removes all explanations and contains only theJavaScript code for all sorting algorithms discussed in the series.
Of course, all the code can also be found on Github in the repositorysorting-algorithms-in-javascript.
Unlike thedata structures, allsorting algorithms have the same goal and they can all take the same input data. So, for every sorting algorithms of the series, we are going sort anarray of 10 numbers from 1 to 10.
By doing so we will be able to compare the different sorting algorithms more easily. Sorting algorithms are very sensitive to the input data so we will also try different input data to see how they affect the performances.
Quicksort is a divide and conquer algorithm. Quicksort first divides a large array into two smaller sub-arrays: the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.FromWikipedia
If you want to have a nice visualization of the algorithm, thevisualgo.net website is a nice resource. You can play with many parameters and see which part of the algorithm is doing what.
| Time complexity | ||
|---|---|---|
| Best | Average | Worst |
| O(n log(n)) | O(n log(n)) | O(n^2) |
To get a full overview of the time and space complexity of the Merge sort algorithm, have a look to this excellentBig O cheat sheet.
For each sorting algorithm, we are going to look at 2 versions of the code. The first one is the final/clean version, the one that you should remember. The second one implements some counters in order to demonstrate the different time complexities depending of the inputs.
// array to sortvararray=[9,2,5,6,4,3,7,10,1,8];// basic implementation (pivot is the first element of the array)functionquicksortBasic(array){if(array.length<2){returnarray;}varpivot=array[0];varlesser=[];vargreater=[];for(vari=1;i<array.length;i++){if(array[i]<pivot){lesser.push(array[i]);}else{greater.push(array[i]);}}returnquicksortBasic(lesser).concat(pivot,quicksortBasic(greater));}console.log(quicksortBasic(array.slice()));// => [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]// swap function helperfunctionswap(array,i,j){vartemp=array[i];array[i]=array[j];array[j]=temp;}// classic implementation (with Hoare or Lomuto partition scheme, you can comment either one method or the other to see the difference)functionquicksort(array,left,right){left=left||0;right=right||array.length-1;// var pivot = partitionLomuto(array, left, right); // you can play with both partitionvarpivot=partitionHoare(array,left,right);// you can play with both partitionif(left<pivot-1){quicksort(array,left,pivot-1);}if(right>pivot){quicksort(array,pivot,right);}returnarray;}// Lomuto partition scheme, it is less efficient than the Hoare partition schemefunctionpartitionLomuto(array,left,right){varpivot=right;vari=left;for(varj=left;j<right;j++){if(array[j]<=array[pivot]){swap(array,i,j);i=i+1;}}swap(array,i,j);returni;}// Hoare partition scheme, it is more efficient than the Lomuto partition scheme because it does three times fewer swaps on averagefunctionpartitionHoare(array,left,right){varpivot=Math.floor((left+right)/2);while(left<=right){while(array[left]<array[pivot]){left++;}while(array[right]>array[pivot]){right--;}if(left<=right){swap(array,left,right);left++;right--;}}returnleft;}console.log(quicksort(array.slice()));// => [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]// sample of arrays to sortvararrayRandom=[9,2,5,6,4,3,7,10,1,8];vararrayOrdered=[1,2,3,4,5,6,7,8,9,10];vararrayReversed=[10,9,8,7,6,5,4,3,2,1];varcountOuter=0;varcountInner=0;varcountSwap=0;functionresetCounters(){countOuter=0;countInner=0;countSwap=0;}// basic implementation (pivot is the first element of the array)functionquicksortBasic(array){countOuter++;if(array.length<2){returnarray;}varpivot=array[0];varlesser=[];vargreater=[];for(vari=1;i<array.length;i++){countInner++;if(array[i]<pivot){lesser.push(array[i]);}else{greater.push(array[i]);}}returnquicksortBasic(lesser).concat(pivot,quicksortBasic(greater));}quicksortBasic(arrayRandom.slice());// => outer: 13 inner: 25 swap: 0console.log('outer:',countOuter,'inner:',countInner,'swap:',countSwap);resetCounters();quicksortBasic(arrayOrdered.slice());// => outer: 19 inner: 45 swap: 0console.log('outer:',countOuter,'inner:',countInner,'swap:',countSwap);resetCounters();quicksortBasic(arrayReversed.slice());// => outer: 19 inner: 45 swap: 0console.log('outer:',countOuter,'inner:',countInner,'swap:',countSwap);resetCounters();// swap function helperfunctionswap(array,i,j){vartemp=array[i];array[i]=array[j];array[j]=temp;}// classic implementation (with Hoare or Lomuto partition scheme, you can comment either one method or the other to see the difference)functionquicksort(array,left,right){countOuter++;left=left||0;right=right||array.length-1;// var pivot = partitionLomuto(array, left, right); // you can play with both partitionvarpivot=partitionHoare(array,left,right);// you can play with both partitionif(left<pivot-1){quicksort(array,left,pivot-1);}if(right>pivot){quicksort(array,pivot,right);}returnarray;}// Lomuto partition scheme, it is less efficient than the Hoare partition schemefunctionpartitionLomuto(array,left,right){varpivot=right;vari=left;for(varj=left;j<right;j++){countInner++;if(array[j]<=array[pivot]){countSwap++;swap(array,i,j);i=i+1;}}countSwap++;swap(array,i,j);returni;}// Hoare partition scheme, it is more efficient than the Lomuto partition scheme because it does three times fewer swaps on averagefunctionpartitionHoare(array,left,right){varpivot=Math.floor((left+right)/2);while(left<=right){countInner++;while(array[left]<array[pivot]){left++;}while(array[right]>array[pivot]){right--;}if(left<=right){countSwap++;swap(array,left,right);left++;right--;}}returnleft;}quicksort(arrayRandom.slice());// => Hoare: outer: 9 inner: 12 swap: 12 - Lomuto: outer: 10 inner: 35 swap: 28console.log('outer:',countOuter,'inner:',countInner,'swap:',countSwap);resetCounters();quicksort(arrayOrdered.slice());// => Hoare: outer: 9 inner: 9 swap: 9 - Lomuto: outer: 9 inner: 45 swap: 54console.log('outer:',countOuter,'inner:',countInner,'swap:',countSwap);resetCounters();quicksort(arrayReversed.slice());// => Hoare: outer: 9 inner: 13 swap: 13 - Lomuto: outer: 10 inner: 54 swap: 39console.log('outer:',countOuter,'inner:',countInner,'swap:',countSwap);resetCounters();