Quick sort is a divide-and-conquer algorithm developed by Tony Hoare in 1959. Let's look at how Quick Sort works.
Here's a step-by-step illustration of what is going on. Try writing down the array [8, 4, 7, 2, 9, 5] and running through Quick Sort yourself.
Here's a nifty animation for your better learning experience.
Quick sort is said to be similar to insertion and bubble, but more efficient in most cases. Depending on the implementation, it may or may not be a stable sort.
O(n2) at worst case, and O(n log n) on average. O(n) space for recursion stack.
Here's a sample implementation written in Java. Note that it extends the Sort.java class.
import java.util.Arrays;
public class QuickSort extends Sort {
public static void main(String[] args) {
int[] testInt = {1,6,2,3,6,7,4,2,5};
quickSort(testInt, 0, testInt.length-1);
System.out.println(Arrays.toString(testInt));
}
public static void quickSort(int[] input, int low, int high) {
// Base case
if (low >= high) {
return;
}
// Use last element as pivot
int pivot = input[high];
// Set our wall at the first element
int wall = low;
/**
* Iterate through array - if current element is less that or equal
* to pivot, swap with element above wall
*/
for (int i = low; i < high; i++) {
if (input[i] <= pivot) {
swap(input, i, wall++);
}
}
// Place pivot to right to just right of wall
swap(input, wall, high);
// Recursively call for each part of array
quickSort(input, low, wall-1);
quickSort(input, wall, high);
}
}
Ever feel achy from sitting crunched up on your computer table? Try lying down with these optical glasses that allow you to work on your laptop while lying flat on your back. This is the perfect solution with those with limited mobility or those who wish to prevent neck cramps and back strains.
$ Check priceAlgorithms are the procedures that software programs use to manipulate data structures. Besides clear and simple example programs, the author includes a workshop as a small demonstration program executable on a Web browser. The programs demonstrate in graphical form what data structures look like and how they operate.
$ Check priceAd