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;
}