Yahir
3/2/2020 - 7:07 AM

quickSort

A sorting algorithm that uses the divide-and-conquer principle through recursive calls and the use of a partition function to set the appropriate pivot and sort values lower and higher to the left and right of the pivot respectively. This is an in-place sorting algorithm.

/*
 * This is the partition function, which places the pivot in the center
 * in sorted array. All values smallr than pivot are placed to left of
 * pivot and all values higher are placed to the right of pivot for 
 * the quicksort algorithm.
 *
 * @param: array | an array of integer values
 * @param: int   | low or starting index
 * @param: int   | high or ending index 
 *
 */
int partition(int numbers[], int low, int high) 
{ 
  int pivot = numbers[high];  
  int i = (low-1); // set index of smallest element
  for (int j=low; j<high; j++) 
  { 
    // Check if current value is less than pivot
    if (numbers[j] < pivot) 
    { 
      i++; 

      // swap numbers at index i and numbers at index j 
      int temp = numbers[i]; 
      numbers[i] = numbers[j]; 
      numbers[j] = temp;
    }
  } 

  // swap numbers at [i+1] and numbers at [high] (or pivot) 
  int temp = numbers[i+1]; 
  numbers[i+1] = numbers[high]; 
  numbers[high] = temp; 

  return i+1;
} 

/*
 * The main impelementation of the quick sort algorithm
 *
 * @param: array  | an array of integer values to sort
 * @param: int    | low or starting index
 * @param: int    | high or ending index
 */
void quicksort(int numbers[], int low, int high) 
{
  if (low < high) 
  { 
    // Partition within the array and assign return last eleemnt in low partition
    int part = partition(numbers, low, high); 

    // Recursively sort elements before 
    // partition and after partition 
    quicksort(numbers, low, part-1); 
    quicksort(numbers, part+1, high);
  }
}
Quicksort in Javascript
- sort for single array or by the first value in a multi-dimensional array
/*
 * quicksort algorithm for an array or sorting by first value in multi-dimensional array
 */

function partition(items, left, right) {
	var temp 	= 0;
    var pivot   = items[Math.floor((right + left) / 2)], //middle element
        i       = left, //left pointer
        j       = right; //right pointer

    while (i <= j) {
        while (items[i] < pivot) {
            i++;
        }
        while (items[j] > pivot) {
            j--;
        }
        if (i <= j) {
            //swap values
            temp = items[i];
            items[i] = items[j];
            items[j] = temp;
            i++;
            j--;
        }
    }
    return i;
}

function quicksort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quicksort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quicksort(items, index, right);
        }
    }
    return items;
}
Quicksort in JavaScript
- sort by second value in 2D array object
function partition(items, left, right) {
	var temp 	= 0;
    var pivot   = items[Math.floor((right + left) / 2)].y, //middle element
        i       = left, //left pointer
        j       = right; //right pointer

    while (i <= j) {
        while (items[i].y < pivot) {
            i++;
        }
        while (items[j].y > pivot) {
            j--;
        }
        if (i <= j) {
            //swap values
            temp = items[i];
            items[i] = items[j];
            items[j] = temp;
            i++;
            j--;
        }
    }
    return i;
}

function quicksort(items, left, right) {
    var index;
    if (items.length > 1) {
        index = partition(items, left, right); //index returned from partition
        if (left < index - 1) { //more elements on the left side of the pivot
            quicksort(items, left, index - 1);
        }
        if (index < right) { //more elements on the right side of the pivot
            quicksort(items, index, right);
        }
    }
    return items;
}