In this post we will take a look on a working Java code example of QuickSort algorithm. We will also clarify the Quicksort by itself, describing the main steps of implementing it in Java language.
About QuickSort
QuickSort is a very popular algorithm for sorting. In most cases it is quicker than Insertion sort and Bubble sort (in average cases it’s complexity is O(n log n)). But it is also a little bit harder to implement.
The QuickSort is not really sophisticated. Its main principle is the partition-exchange. At first, we need to choose the pivot. In our case it will be a last element in the array. The next part is to separate items that are less than pivot and greater than pivot. The same algorithm should be repeated for sub-arrays from the left of a pivot and from the right.
QuickSort Java code implementation
We need to create only one class. Let’s call it QuickSort.java. Here is the full code listing:
import java.util.Random; public class QuickSort { public int [] arr; public QuickSort(int[] arr) { this.arr = arr; } public void sort() { sort(0, arr.length - 1); } public void sort(int first, int last){ // this is the point when we break the recursion if (last - first < 1) return; int pivot = arr[last]; // the pivot is a last item of array System.out.println("Pivot: " + pivot); int index = first - 1; // after this loop array will be reorganized: // items <= pivot will be on the left of pivot; items greater than pivot - on the right; for (int i = first; i<last; i++) { if (arr[i] <= pivot) { swap(++index, i); } printArray(); // this line prints out the array on each iteration } swap(index + 1, last); // recursively running same algorithm for 2 sub-arrays: // smaller than pivot and larger than pivot sort(first, index); sort(index + 2, last); } public void swap (int first, int second) { int temp = arr[first]; arr[first] = arr[second]; arr[second] = temp; } private void printArray() { for (int i : arr){ System.out.print(i + " "); } System.out.println(); } public static void main(String[] args) { QuickSort quickSort = new QuickSort(initRandomArray(10, 10)); quickSort.sort(); } private static int[] initRandomArray(int size, int range) { int [] arr = new int[size]; for (int i = 0; i < size; i++) { arr[i] = new Random().nextInt(range); } return arr; } }
Explanation
The main logic is located inside the sort(int first, int last) method. You can see some utility methods like swap() – replaces 2 elements in array, printArray() – simply prints the array in the console, initRandomArray() – generates the random data.
The sort() method implements the Quicksort algorithm code like in the description above. If the logic is too complicated for you, take a look at this video. I hope it will clarify a lot.
If you know how to improve this QuickSort Java code example please let me know by leaving a comment below.
Leave a Reply
Be the First to Comment!