Java Quick Sort
Welcome to my Java Quick Sort tutorial! In most situations the Quick Sort is the fastest sorting algorithm.
In essence, the quick sort works by partitioning arrays so that the smaller numbers are on the left and the larger are on the right. I’ll cover what partitioning is in this video.
The Quick Sort then recursively sends small parts of larger arrays to itself and partitions again. Between the code and the video below you will completely get it in the end.
If you like videos like this, it helps to tell Google+
Code from the Video
Partitioning.java
import java.util.Arrays;
// When we partition data we are dividing it into
// two parts. All items with data above a defined value
// will go in one part and the rest will go in the other
// The value that defines in which group data will go
// is known as the pivot value
public class Partitioning {
private static int[] theArray;
private static int arraySize;
public static void main(String[] args) {
Partitioning partitionArray = new Partitioning(10);
partitionArray.generateRandomArray();
System.out.println(Arrays.toString(Partitioning.theArray));
// Every item smaller than 35 will be on the left and
// everything bigger will be on the right
partitionArray.partitionArray(35);
System.out.println(Arrays.toString(Partitioning.theArray));
}
public void partitionArray(int pivot) {
// If leftPointer finds an item that is greater
// than pivot it stops and waits for the rightPointer
// to find a value less than pivot. Then the items
// are switched
// Starts at the left side of array before index 0
int leftPointer = -1;
// Starts at the right side of the array after the last index
int rightPointer = arraySize;
while (true) {
// Cycle through array until the end is reached
// or an item bigger than pivot is found. Then
// wait for rightPointer to finish cycling
while (leftPointer < (arraySize - 1)
&& theArray[++leftPointer] < pivot)
;
printHorzArray(leftPointer, rightPointer);
System.out.println(theArray[leftPointer] + " in index "
+ leftPointer + " is bigger than the pivot value " + pivot);
// Cycle through array until the beginning is reached
// or an item smaller than pivot is found.
while (rightPointer > 0 && theArray[--rightPointer] > pivot)
;
printHorzArray(leftPointer, rightPointer);
System.out.println(theArray[rightPointer] + " in index "
+ rightPointer + " is smaller than the pivot value "
+ pivot);
printHorzArray(leftPointer, rightPointer);
// When the 2 pointers meet at the middle break
// out of the while loop
if (leftPointer >= rightPointer)
break;
else {
// Swap the values in the pointers
swapValues(leftPointer, rightPointer);
System.out.println(theArray[leftPointer] + " was swapped for "
+ theArray[rightPointer]);
}
}
}
public void swapValues(int indexOne, int indexTwo) {
int temp = theArray[indexOne];
theArray[indexOne] = theArray[indexTwo];
theArray[indexTwo] = temp;
}
Partitioning(int newArraySize) {
arraySize = newArraySize;
theArray = new int[arraySize];
generateRandomArray();
}
public void generateRandomArray() {
for (int i = 0; i < arraySize; i++) {
// Generate a random array with values between
// 10 and 59
theArray[i] = (int) (Math.random() * 50) + 10;
}
}
static void printHorzArray(int i, int j) {
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
for (int n = 0; n < arraySize; n++) {
System.out.format("| %2s " + " ", n);
}
System.out.println("|");
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
for (int n = 0; n < arraySize; n++) {
System.out.print(String.format("| %2s " + " ", theArray[n]));
}
System.out.println("|");
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
if (i != -1) {
// Number of spaces to put before the F
int spacesBeforeFront = 5 * i + 1;
for (int k = 0; k < spacesBeforeFront; k++)
System.out.print(" ");
System.out.print("L");
// Number of spaces to put before the R
int spacesBeforeRear = (5 * j + 1 - 1) - spacesBeforeFront;
for (int l = 0; l < spacesBeforeRear; l++)
System.out.print(" ");
System.out.print("H");
System.out.println("\n");
}
}
}
QuickSort.java
import java.util.Arrays;
// The Quick Sort is normally the fastest sorting algorithm
public class QuickSort {
private static int[] theArray;
private static int arraySize;
public static void main(String[] args) {
QuickSort theSort = new QuickSort(10);
theSort.generateRandomArray();
System.out.println(Arrays.toString(QuickSort.theArray));
theSort.quickSort(0, 9);
System.out.println(Arrays.toString(QuickSort.theArray));
}
QuickSort(int newArraySize) {
arraySize = newArraySize;
theArray = new int[arraySize];
generateRandomArray();
}
public void quickSort(int left, int right) {
if (right - left <= 0)
return; // Everything is sorted
else {
// It doesn't matter what the pivot is, but it must
// be a value in the array
int pivot = theArray[right];
System.out.println("Value in right " + theArray[right]
+ " is made the pivot");
System.out.println("left = " + left + " right= " + right
+ " pivot= " + pivot + " sent to be partitioned");
int pivotLocation = partitionArray(left, right, pivot);
System.out.println("Value in left " + theArray[left]
+ " is made the pivot");
quickSort(left, pivotLocation - 1); // Sorts the left side
quickSort(pivotLocation + 1, right);
}
}
public int partitionArray(int left, int right, int pivot) {
int leftPointer = left - 1;
int rightPointer = right;
while (true) {
while (theArray[++leftPointer] < pivot)
;
printHorzArray(leftPointer, rightPointer);
System.out.println(theArray[leftPointer] + " in index "
+ leftPointer + " is bigger than the pivot value " + pivot);
while (rightPointer > 0 && theArray[--rightPointer] > pivot)
;
printHorzArray(leftPointer, rightPointer);
System.out.println(theArray[rightPointer] + " in index "
+ rightPointer + " is smaller than the pivot value "
+ pivot);
printHorzArray(leftPointer, rightPointer);
if (leftPointer >= rightPointer) {
System.out.println("left is >= right so start again");
break;
}
else {
swapValues(leftPointer, rightPointer);
System.out.println(theArray[leftPointer] + " was swapped for "
+ theArray[rightPointer]);
}
}
swapValues(leftPointer, right);
return leftPointer;
}
public void swapValues(int indexOne, int indexTwo) {
int temp = theArray[indexOne];
theArray[indexOne] = theArray[indexTwo];
theArray[indexTwo] = temp;
}
public void generateRandomArray() {
for (int i = 0; i < arraySize; i++) {
// Generate a random array with values between
// 10 and 59
theArray[i] = (int) (Math.random() * 50) + 10;
}
}
static void printHorzArray(int i, int j) {
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
for (int n = 0; n < arraySize; n++) {
System.out.format("| %2s " + " ", n);
}
System.out.println("|");
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
for (int n = 0; n < arraySize; n++) {
System.out.print(String.format("| %2s " + " ", theArray[n]));
}
System.out.println("|");
for (int n = 0; n < 61; n++)
System.out.print("-");
System.out.println();
if (i != -1) {
// Number of spaces to put before the F
int spacesBeforeFront = 6 * (i + 1) - 5;
for (int k = 0; k < spacesBeforeFront; k++)
System.out.print(" ");
System.out.print("L" + i);
// Number of spaces to put before the R
int spacesBeforeRear = 5 * (j + 1) - spacesBeforeFront;
for (int l = 0; l < spacesBeforeRear; l++)
System.out.print(" ");
System.out.print("R" + j);
System.out.println("\n");
}
}
}
Hi, Derek!
Your tutorials are always awesome! Thank you very much for all!
Do you have any tutorial about Test-Driven Development? About mocks objects? If you have, let me know, please. I’m sure that your opinion about that will help me (and other programmers too)…
Regards,
Helton
Thank you very much
I’ll be covering that topic soon. I’ll cover everything about java by the end
Good Job Derek …….. i,m desperately waiting for Android Tutorials.
They will start this month finally! Sorry about the wait
Derek,
Great job. Thanks for sharing all of your hard work.
Thank you and you are very welcome