Quicksort
public static void quicksort(int[] array)
{
array = quicksort(array, 0, array.length-1);
}
private static int[] quicksort(int[] array, int lo, int hi) {
if (hi > lo)
{
int partitionPivotIndex = (int)(Math.random()*(hi-lo) + lo);
int newPivotIndex = partition(array, lo, hi, partitionPivotIndex);
quicksort(array, lo, newPivotIndex-1);
quicksort(array, newPivotIndex+1, hi);
}
return (int[]) array;
}
private static int partition(int[] array, int lo, int hi, int pivotIndex)
{
int pivotValue = array[ pivotIndex ];
swap(array, pivotIndex, hi); //send to the back
int index = lo;
for (int i = lo; i < hi; i++)
{
if ( (array[i])<=(pivotValue))
{
swap(array, i, index);
index++;
}
}
swap(array, hi, index);
return index;
}
private static void swap(int[] array, int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
Java quicksort program. Notice that quicksort is the name of two methods with the same name. Call quicksort(array) which sorts integer arrays. Quicksort is a recursive algorithm that finds a pivot, rearranges elements less than the pivot left and elements more than the pivot right, and recursively does the same with the two left and right subarrays until the algorithm is sorted. One of the most popular algorithms because it is simple and quick, quicksort runs on O(nlog(n)) time as opposed to the O(n^2) time of bubblesort.
Pseudocode (if you want for other languages):
function partition(array, left, right, pivotIndex)
pivotValue := array[pivotIndex]
swap array[pivotIndex] and array[right] // Move pivot to end
storeIndex := left
for i from left to right - 1 // left ≤ i < right
if array[i] ≤ pivotValue
swap array[i] and array[storeIndex]
storeIndex := storeIndex + 1
swap array[storeIndex] and array[right] // Move pivot to its final place
return storeIndex
Java code is above: just copy-and-paste and quicksort works immediately.
{
array = quicksort(array, 0, array.length-1);
}
private static int[] quicksort(int[] array, int lo, int hi) {
if (hi > lo)
{
int partitionPivotIndex = (int)(Math.random()*(hi-lo) + lo);
int newPivotIndex = partition(array, lo, hi, partitionPivotIndex);
quicksort(array, lo, newPivotIndex-1);
quicksort(array, newPivotIndex+1, hi);
}
return (int[]) array;
}
private static int partition(int[] array, int lo, int hi, int pivotIndex)
{
int pivotValue = array[ pivotIndex ];
swap(array, pivotIndex, hi); //send to the back
int index = lo;
for (int i = lo; i < hi; i++)
{
if ( (array[i])<=(pivotValue))
{
swap(array, i, index);
index++;
}
}
swap(array, hi, index);
return index;
}
private static void swap(int[] array, int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
Java quicksort program. Notice that quicksort is the name of two methods with the same name. Call quicksort(array) which sorts integer arrays. Quicksort is a recursive algorithm that finds a pivot, rearranges elements less than the pivot left and elements more than the pivot right, and recursively does the same with the two left and right subarrays until the algorithm is sorted. One of the most popular algorithms because it is simple and quick, quicksort runs on O(nlog(n)) time as opposed to the O(n^2) time of bubblesort.
Pseudocode (if you want for other languages):
function partition(array, left, right, pivotIndex)
pivotValue := array[pivotIndex]
swap array[pivotIndex] and array[right] // Move pivot to end
storeIndex := left
for i from left to right - 1 // left ≤ i < right
if array[i] ≤ pivotValue
swap array[i] and array[storeIndex]
storeIndex := storeIndex + 1
swap array[storeIndex] and array[right] // Move pivot to its final place
return storeIndex
Java code is above: just copy-and-paste and quicksort works immediately.
Provided by website-hit-counters.com site. |