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 in Java.

The Essence of the QuickSort 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.
QuickSort in Java - 1

Before Implementing the Algorithm

Before you start coding, consider these key points about quicksort algorithm in Java: 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 in Java

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:
Unsorted Array: [17, 14, 15, 28, 6, 8, -6, 1, 3, 18] Sorted Array: [-6, 1, 3, 6, 8, 14, 15, 17, 18, 28]
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.

Detailed Breakdown of the Partitioning Process

The partitioning process is the cornerstone of the Quicksort algorithm. It divides the array into two sections based on a pivot element:

  • Elements smaller than the pivot are placed on the left.
  • Elements greater than the pivot are placed on the right.

Here’s a step-by-step explanation of how partitioning works:

Step-by-Step Partitioning

public class QuicksortPartition {
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // Choose the last element as the pivot
        int i = low - 1; // Pointer for smaller elements

        for (int j = low; j < high; j++) {
            // If the current element is smaller than the pivot
            if (arr[j] < pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap the pivot with the element at i + 1
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1; // Return the partition index
    }

    public static void main(String[] args) {
        int[] array = {10, 80, 30, 90, 40, 50, 70};
        int partitionIndex = partition(array, 0, array.length - 1);
        System.out.println("Partitioned Array: " + java.util.Arrays.toString(array));
        System.out.println("Partition Index: " + partitionIndex);
    }
}

Output:

  • Partitioned Array: [10, 30, 40, 50, 70, 90, 80]
  • Partition Index: 4

In this example, the pivot is 70, and the elements are rearranged to place all smaller elements to its left and larger ones to its right.

Quicksort on Different Data Structures

Quicksort is most commonly applied to arrays, but its implementation and performance characteristics differ when applied to other data structures like linked lists.

Quicksort on Arrays

Arrays are contiguous memory structures, making swaps and index-based access efficient. This is why Quicksort is often used with arrays.

Quicksort on Linked Lists

Linked lists have non-contiguous memory, making element swapping inefficient. Instead, Quicksort uses pointers to rearrange nodes:

class ListNode {
    int value;
    ListNode next;

    ListNode(int value) {
        this.value = value;
        this.next = null;
    }
}

// Implementing Quicksort for linked lists requires partitioning by rearranging pointers rather than swapping data.

Note: For linked lists, Merge Sort is often preferred due to its pointer-based operations and stable sorting behavior.

Recursive Nature and Execution Flow of Quicksort

Quicksort relies heavily on recursion to divide and conquer. Here's a step-by-step explanation of its recursive execution:

Recursive Steps

  1. Choose a pivot and partition the array into two sections.
  2. Recursively apply Quicksort to the left section.
  3. Recursively apply Quicksort to the right section.

Example: Recursive Implementation

public class Quicksort {
    public static void quicksort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array
            int pi = partition(arr, low, high);

            // Recursively sort the left and right sections
            quicksort(arr, low, pi - 1);
            quicksort(arr, pi + 1, high);
        }
    }

    public static void main(String[] args) {
        int[] array = {10, 80, 30, 90, 40, 50, 70};
        quicksort(array, 0, array.length - 1);
        System.out.println("Sorted Array: " + java.util.Arrays.toString(array));
    }
}

Output: Sorted Array: [10, 30, 40, 50, 70, 80, 90]

Visualization of Execution

At each recursive call:

  • The pivot is selected and the array is partitioned.
  • Left and right sections are sorted recursively.
  • The recursion terminates when the subarray has one or no elements.

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.