QuickSort in Java

There's a whole smorgasbord of sorting algorithms in the programming world, each flaunting its uniqueness in efficiency (think execution time and memory usage) and simplicity of implementation. But wait, there's more — factors like stability (do equal elements keep their order?), adaptability (how well does it handle partially sorted data?), and scalability (can it handle the big stuff?) also play a big role. In this article, we dive into the world of Quick Sort algorithm.

The Essence of the Algorithm

QuickSort is a nifty little algorithm. It might seem a bit tricky for beginners, but its core principle is as old and simple as time itself: "divide and conquer". Here's the rundown:

1. First up, pick a pivot element in the array. The middle one's a common choice, but hey, why not live on the edge and pick it randomly? Or, if you're feeling lazy, just snag the first or last element.
2. Time to partition! Split the array so that elements less than the pivot scooch to the left, and the bigger ones shuffle to the right.
3. Keep on dividing. Repeat the process recursively for the left and right parts of the array until each part is just one element strong.

Before Implementing the Algorithm

Before you start coding, consider these key points about quicksort algorithm: Watch the boundaries. Be careful with the array limits to avoid stepping out of bounds. In other words, make sure the range (low and high indexes) is legit before you partition or call QuickSort recursively. Stack overflow. No, not the website. With recursion, you might run into stack overflow issues, especially with big arrays. How to dodge this? Maybe start with the smaller of the two subarrays post-partition. Picking the pivot in QuickSort is like choosing the right spice — it can make or break your dish. Here are some popular methods:

• First or last element. Easy peasy, but it might backfire in performance, especially if the array is already somewhat sorted.
• Middle element. Calculating the index as (low + high) / 2 can dodge some worst-case scenarios.
• Median of three. Choose the median of three elements (usually the first, middle, and last). This often leads to a more balanced split.
• Random element. This can reduce the chance of hitting the worst-case performance, especially for arrays that are already sorted or have a certain structure.
• For massive arrays, there's a method called "median of medians". It's complex and involves extra calculations but offers a more balanced pivot selection.

Overall, your choice depends on the specific conditions and performance requirements. Let's start simple with the last element as the pivot.

Implementing QuickSort

Let's jump into implementing QuickSort in Java.

import java.util.Arrays;


public class QuickSort {




   public static void main(String[] args) {
       int[] array = {17, 14, 15, 28, 6, 8, -6, 1, 3, 18};
       System.out.println("Unsorted Array: " + Arrays.toString(array));
       quickSort(array, 0, array.length - 1);
       System.out.println("  Sorted Array: " + Arrays.toString(array));


   }


   public static void quickSort(int[] arr, int low, int high) {
       if (low < high) {
           int pi = partition(arr, low, high);


           quickSort(arr, low, pi - 1);
           quickSort(arr, pi + 1, high);
       }
   }


   private static int partition(int[] arr, int low, int high) {
       int pivot = arr[high];
       int i = (low - 1);
       for (int j = low; j < high; j++) {
           if (arr[j] < pivot) {
               i++;


               int temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
           }
       }


       int temp = arr[i + 1];
       arr[i + 1] = arr[high];
       arr[high] = temp;


       return i + 1;
   }
}

The output of the program is here: Let's break down what's happening here. The recursive method quickSort takes in an array, along with lower (low) and upper (high) indexes. If low is less than high, the array is partitioned using the partition method, and then quickSort is called recursively for the left and right parts. The partition method positions the pivot element (here, the last array element) and shuffles the elements so that those less than the pivot are on the left, and the larger ones are on the right, returning the pivot's index after the swap. Now, let's tweak the quicksort example to pick the middle element as the pivot.

Import java.util.Arrays;

public class QuickSort {
   public static void main(String[] args) {
       int[] array = {17, 14, 15, 28, 6, 8, -6, 1, 3, 18};
       System.out.println("Unsorted Array: " + Arrays.toString(array));
       quickSort(array, 0, array.length - 1);
       System.out.println("  Sorted Array: " + Arrays.toString(array));
   }

   public static void quickSort(int[] arr, int low, int high) {
       if (low < high) {
           int pi = partition(arr, low, high);

           quickSort(arr, low, pi - 1);
           quickSort(arr, pi + 1, high);
       }
   }

   private static int partition(int[] arr, int low, int high) {
       // our pivot is the middle element of the array 
       int middle = low + (high - low) / 2;
       int pivot = arr[middle];

       // Swap the pivot element with the last one to use existing logic
       int temp = arr[middle];
       arr[middle] = arr[high];
       arr[high] = temp;

       int i = (low - 1);
       for (int j = low; j < high; j++) {
           if (arr[j] < pivot) {
               i++;

               temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
           }
       }

       temp = arr[i + 1];
       arr[i + 1] = arr[high];
       arr[high] = temp;

       return i + 1;
   }
}

This approach might be faster than using the last element as the pivot on certain datasets, especially partially sorted arrays.

Iterative QuickSort Algorithm

Java's QuickSort doesn't just dance to the recursive tune; it can groove iteratively too. Let's try implementing that version. This one uses a stack to keep track of the indexes of subarrays that need sorting.

import java.util.Arrays;
import java.util.Stack;


public class QuickSort {


   static void quickSort(int[] arr, int l, int h) {
       if (arr == null || arr.length == 0)
           return;


       if (l >= h)
           return;


       Stack stack = new Stack<>();
       stack.push(l);
       stack.push(h);


       while (!stack.isEmpty()) {
           h = stack.pop();
           l = stack.pop();


           int pivotIndex = partition(arr, l, h);


           if (pivotIndex - 1 > l) {
               stack.push(l);
               stack.push(pivotIndex - 1);
           }


           if (pivotIndex + 1 < h) {
               stack.push(pivotIndex + 1);
               stack.push(h);
           }
       }
   }


   private static int partition(int[] arr, int low, int high) {
       int pivot = arr[high];
       int i = low;
       for (int j = low; j < high; j++) {
           if (arr[j] <= pivot) {
               int temp = arr[i];
               arr[i] = arr[j];
               arr[j] = temp;
               i++;
           }
       }


       int temp = arr[i];
       arr[i] = arr[high];
       arr[high] = temp;
       return i;
   }


   public static void main(String[] args) {
       int[] array = {17, 14, 15, 28, 6, 8, -6, 1, 3, 18};
       System.out.println("Unsorted Array: " + Arrays.toString(array));
       quickSort(array, 0, array.length - 1);
       System.out.println("  Sorted Array: " + Arrays.toString(array));;
       }
   }

The output will be the same as in the previous cases.

Complexity of the QuickSort Algorithm

Algorithm complexity is all about measuring how cool your algorithm is. It's often expressed in "Big O notation", which paints a picture of the algorithm's worst-case behavior as the input size grows. Remember, Big O doesn't give you exact execution times; it's more about showing how the algorithm's performance trends. QuickSort's complexity depends on several factors, including the pivot choice and data distribution. Generally, it's like this: Best case: O(n log n). The algorithm splits the array into equal parts, leading to super-efficient division and cutting down on time. Average case: Also O(n log n). For random data and a savvy pivot choice, QuickSort often hits this complexity sweet spot. Worst case: O(n²). Not so cool. This happens when each division splits the array into parts of size '1' and 'n-1', often occurring when the pivot is the smallest or largest element in the array. For example, if the array is already sorted and the pivot is the first or last element, the algorithm's performance takes a hit.