w3resource

JavaScript Sorting Algorithm: Sorts an array of numbers, using the quicksort algorithm

JavaScript Sorting Algorithm: Exercise-1 with Solution

Write a JavaScript program to sort a list of elements using Quick sort.

Quick sort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined.

Pictorial presentation - Quick Sort algorithm :

Quick sort part-1
Quick sort part-2
Sorting quicksort animation

Animated visualization of the quicksort algorithm. The horizontal lines are pivot values. Animation credits: RolandH

Sample Solution-1:

JavaScript Code:

function quick_Sort(origArray) {
	if (origArray.length <= 1) { 
		return origArray;
	} else {

		var left = [];
		var right = [];
		var newArray = [];
		var pivot = origArray.pop();
		var length = origArray.length;

		for (var i = 0; i < length; i++) {
			if (origArray[i] <= pivot) {
				left.push(origArray[i]);
			} else {
				right.push(origArray[i]);
			}
		}

		return newArray.concat(quick_Sort(left), pivot, quick_Sort(right));
	}
}

var myArray = [3, 0, 2, 5, -1, 4, 1 ];

console.log("Original array: " + myArray);
var sortedArray = quick_Sort(myArray);
console.log("Sorted array: " + sortedArray);

Sample Output:

Original array: 3,0,2,5,-1,4,1
Sorted array: -1,0,1,2,3,4,5

Flowchart:

Flowchart: JavaScript - Sorts an array of numbers, using the quicksort algorithm.

Sample Solution-2:

  • Use recursion.
  • Use the spread operator (...) to clone the original array, arr.
  • If the length of the array is less than 2, return the cloned array.
  • Use Math.floor() to calculate the index of the pivot element.
  • Use Array.prototype.reduce() and Array.prototype.push() to split the array into two subarrays (elements smaller or equal to the pivot and elements greater than it), destructuring the result into two arrays.
  • Recursively call quickSort() on the created subarrays.

JavaScript Code:

const quickSort = arr => {
  const a = [...arr];
  if (a.length < 2) return a;
  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = a[pivotIndex];
  const [lo, hi] = a.reduce(
    (acc, val, i) => {
      if (val < pivot || (val === pivot && i != pivotIndex)) {
        acc[0].push(val);
      } else if (val > pivot) {
        acc[1].push(val);
      }
      return acc;
    },
    [[], []]
  );
  return [...quickSort(lo), pivot, ...quickSort(hi)];
};
 
console.log(quickSort([1, 6, 1, 5, 3, 2, 1, 4]));

Sample Output:

[1,1,1,2,3,4,5,6]

Flowchart:

Flowchart: JavaScript - Sorts an array of numbers, using the quicksort algorithm.

Live Demo:

See the Pen searching-and-sorting-algorithm-exercise-1 by w3resource (@w3resource) on CodePen.


* To run the code mouse over on Result panel and click on 'RERUN' button.*

Improve this sample solution and post your code through Disqus

Previous: JavaScript Sorting Algorithm Exercises.
Next: Write a JavaScript program to sort a list of elements using Merge sort.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Become a Patron!

Follow us on Facebook and Twitter for latest update.

It will be nice if you may share this link in any developer community or anywhere else, from where other developers may find this content. Thanks.

https://www.w3resource.com/javascript-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-1.php