Quick sort is a divide-and-conquer algorithm developed by Tony Hoare in 1959. Let's look at how Quick Sort works.

- Assign the last element as a pivot.
- Place a line to partition the array into two, starting from the far left end of the array.
- For each element in our array that is less than or equal to the pivot, swap it with the element to the right of the wall and move wall up one.
- Place pivot as the first element on the right of the partitioning wall.
- Split and repeat, then merge together for sorted array.

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(n ^{2})` at worst case, and

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

This fourth edition of Algorithms is the leading textbook on algorithms today and is widely used in universities worldwide. This book surveys the most important computer algorithms currently in use and provides a full treatment of data structures and algorithms for sorting, searching, graph processing, and string processing.

$ Check price(148+ reviews)

A handy guide of sorts for any computer science professional, Data Structures And Algorithms Made Easy in Java: Data Structure And Algorithmic Puzzles is a solution bank for various complex problems related to data structures and algorithms. It can be used as a reference manual by those readers in the computer science industry.

$ Check price(339+ reviews)

Ad