Java Quick Sort

Java Quick SortWelcome 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");

		}

	}

}

13 Responses to “Java Quick Sort”

  1. Helton says:

    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

  2. waqas says:

    Good Job Derek …….. i,m desperately waiting for Android Tutorials. :)

  3. greg says:

    Derek,

    Great job. Thanks for sharing all of your hard work.

  4. Tim Hiller says:

    Having a ‘Partitioning’ object named partitionArray, when you already have a method named partitionArray was confusing and led to this code on line 020:
    partitionArray.partitionArray(35);

  5. Vachagan says:

    Just a little tip. In your source in the constructor you have call to generateRandomArray, and the same call in the main method…

  6. Hitesh says:

    By helping people learn things that matter to them, you are making this world a better place.
    I am also a fan of your presentation style, nice and lucid.
    I never understood sorting untill I found your youtube channel.
    Thanks

  7. Viswanth says:

    Hi Derek, I am a great fan of yours and learn a lot from your videos. I refer back to your videos whenever I have any doubt. Just like that I happened to watch this Quick Sort tutorial and I saw how you said that you would learn by printing out stuff. That is what even I do while writing programs and I think it is a great way to have a peek at what is going on in your code. I want to be an intensive programmer like you some day. How do you get yourself going day after day doing so many hundreds of videos?

    • Derek Banas says:

      Hi Viswanth,

      Thank you :) Yes that was a trick I developed over time. As per what motivates me, I guess I just really enjoy what I do. I think the reason why I get so much done is because I stick to a very tight schedule. If I schedule something between 1 PM and 3 PM, when 3 PM comes I immediately stop and move on to the next task on the schedule. I also know that I’ll get bored if I do something for to long. Everything for me is a matter of knowing myself. If I know I can perform best at a task if I do it for just 2 hours a day I do that. I know this isn’t always possible when you work for some one, but I’ve always done my best to make it work.

      I hope that helps :)
      Derek

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Google+