Algorithm - QuickSort in Javascript


Posted on Jan 19th, 2016


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.

The steps are:

  1. Pick an element, called a pivot, from the array.
  2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
  3. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.

The base case of the recursion is arrays of size zero or one, which never need to be sorted.

The pivot selection and partitioning steps can be done in several different ways; the choice of specific implementation schemes greatly affects the algorithm's performance.

/**
 * Quicksort Algorithm
 * Usage:
 * var arr = [8,3,1,7,6];
 * sort(arr).qsort(); //this is in-place
 * console.log(arr);
 */

var sort = function(arr) {
  
  	/* Swap positions */
	function swap(idx1, idx2) {
    
		var temp = arr[idx1];
		arr[idx1] = arr[idx2];
		arr[idx2] = temp;
    
  	}
  
  	/* Partiton the array */
	function partition(left,right,pivot) {

		//incremenet this counter when we find an element 
		//less than the pivot value
		var j = left;

		for(var i = left; i < right; i++) {
		  
			if(arr[i] < arr[pivot]) {
				swap(j,i);
				j++;
			}
		  
		}

		var newPivot = j;
		//bring the pivot in the right position
		swap(pivot, newPivot);

		return newPivot;

	}
  
  /** 
   * Triggers the sort. Initially left and right will be undefined.
   * @param int left   | default: 0
   * @param int right  | default: lastIndex of array
   */
  	function qsort(left, right) {
    
	    left = (typeof left === 'number') ? left : 0;
	    
	    right = (typeof right === 'number') ? right : arr.length - 1;
	    
	    if(left < right) {
	    	//the last index is going to be the pivot
			var pivot = right;
			// identify the new pivot, so that the 
			//left elements < pivot and right elements > pivot
			var newPivot = partition(left,right,pivot);

			//apply the sort on the left elements
			qsort(left, newPivot - 1);
			//apply the sort on the right elements
			qsort(newPivot+1, right);
	      
	    }
  	}
  
	return {
		qsort: qsort
	}
  
}

 


Algorithm - List Prime Numbers in JavascriptSetting up hosting environment on Amazon EC2 with NodeJS, Nginx and php-fpm

Comments
100% Complete