Implementation of Quick Sort Algorithm in Java

Quick Sort is a powerful and efficient sorting algorithm that follows the “divide and conquer” approach. In this article, we’ll implement the Quick Sort algorithm in Java, starting with a basic version and then exploring several variations including different pivot selection strategies, sorting in descending order, and sorting custom objects. By the end, you’ll have a solid understanding of how to implement Quick Sort in Java for various scenarios.

Basic Quick Sort Implementation

Let’s start with a standard implementation of Quick Sort in Java. This version uses the last element as the pivot and sorts an array in ascending order.

public class QuickSort {
  // The main function that implements QuickSort
  public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
      // Partition the array and get the pivot index
      int pivotIndex = partition(arr, low, high);
      
      // Recursively sort elements before and after the pivot
      quickSort(arr, low, pivotIndex - 1);
      quickSort(arr, pivotIndex + 1, high);
    }
  }
  
  // This function takes the last element as pivot, places it at its correct
  // position, and places all smaller elements to the left and larger to the right
  private static int partition(int[] arr, int low, int high) {
    // Select the pivot (last element)
    int pivot = arr[high];
    
    // Index of smaller element
    int i = low - 1;
    
    // Traverse through all elements
    // Compare each element with pivot
    for (int j = low; j < high; j++) {
      // If current element is smaller than the pivot
      if (arr[j] < pivot) {
        // Increment index of smaller element
        i++;
        
        // Swap elements
        swap(arr, i, j);
      }
    }
    
    // Swap the pivot element with the element at (i + 1)
    // This puts pivot in its correct position
    swap(arr, i + 1, high);
    
    // Return the position of the pivot
    return i + 1;
  }
  
  // A utility function to swap two elements
  private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  
  // Utility method to print an array
  public static void printArray(int[] arr) {
    for (int num : arr) {
      System.out.print(num + " ");
    }
    System.out.println();
  }
  
  // Driver method to test the implementation
  public static void main(String[] args) {
    int[] arr = {10, 7, 8, 9, 1, 5};
    
    System.out.println("Original array:");
    printArray(arr);
    
    quickSort(arr, 0, arr.length - 1);
    
    System.out.println("Sorted array:");
    printArray(arr);
  }
}

In this implementation:

  1. The quickSort method is the main recursive function that sorts the array.
  2. The partition method selects the last element as the pivot, places it at its correct position, and arranges all smaller elements to the left and all larger elements to the right.
  3. The swap method is a utility function to swap two elements in the array.

Implementing Different Pivot Selection Strategies

The choice of pivot can significantly impact the performance of Quick Sort. Let’s implement three common pivot selection strategies:

First Element as Pivot

private static int partitionFirstPivot(int[] arr, int low, int high) {
  // Select the first element as pivot
  int pivot = arr[low];
  
  // Start from the element after the pivot
  int i = low;
  
  for (int j = low + 1; j <= high; j++) {
    // If current element is smaller than the pivot
    if (arr[j] < pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  
  // Place pivot in its correct position
  swap(arr, low, i);
  
  return i;
}

Middle Element as Pivot

private static int partitionMiddlePivot(int[] arr, int low, int high) {
  // Select the middle element as pivot
  int mid = low + (high - low) / 2;
  int pivot = arr[mid];
  
  // Move the pivot to the end temporarily
  swap(arr, mid, high);
  
  // Now partition as usual with the last element as pivot
  int i = low - 1;
  
  for (int j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  
  // Place pivot in its correct position
  swap(arr, i + 1, high);
  
  return i + 1;
}

Random Element as Pivot

private static int partitionRandomPivot(int[] arr, int low, int high) {
  // Select a random element as pivot
  Random rand = new Random();
  int randomIndex = low + rand.nextInt(high - low + 1);
  int pivot = arr[randomIndex];
  
  // Move the pivot to the end temporarily
  swap(arr, randomIndex, high);
  
  // Now partition as usual with the last element as pivot
  int i = low - 1;
  
  for (int j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  
  // Place pivot in its correct position
  swap(arr, i + 1, high);
  
  return i + 1;
}

Median-of-Three Pivot Selection

private static int partitionMedianOfThree(int[] arr, int low, int high) {
  // Find the median of the first, middle, and last elements
  int mid = low + (high - low) / 2;
  
  // Sort the three elements: arr[low], arr[mid], arr[high]
  if (arr[low] > arr[mid]) {
    swap(arr, low, mid);
  }
  if (arr[low] > arr[high]) {
    swap(arr, low, high);
  }
  if (arr[mid] > arr[high]) {
    swap(arr, mid, high);
  }
  
  // Now arr[mid] is the median
  // Move the pivot (median) to the end temporarily
  swap(arr, mid, high - 1);
  
  // Use arr[high-1] as pivot
  int pivot = arr[high - 1];
  int i = low;
  
  // Partition the array
  for (int j = low + 1; j < high - 1; j++) {
    if (arr[j] < pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  
  // Place pivot in its correct position
  swap(arr, i + 1, high - 1);
  
  return i + 1;
}

Sorting in Descending Order

To sort an array in descending order, we simply need to change the comparison in the partition function:

private static int partitionDescending(int[] arr, int low, int high) {
  int pivot = arr[high];
  int i = low - 1;
  
  for (int j = low; j < high; j++) {
    // Change the comparison to sort in descending order
    if (arr[j] > pivot) {
      i++;
      swap(arr, i, j);
    }
  }
  
  swap(arr, i + 1, high);
  return i + 1;
}

public static void quickSortDescending(int[] arr, int low, int high) {
  if (low < high) {
    int pivotIndex = partitionDescending(arr, low, high);
    quickSortDescending(arr, low, pivotIndex - 1);
    quickSortDescending(arr, pivotIndex + 1, high);
  }
}

Sorting Custom Objects

In real-world applications, we often need to sort objects based on specific properties. Let’s implement Quick Sort for a list of Person objects, sorting them by age:

class Person {
  private String name;
  private int age;
  
  public Person(String name, int age) {
    this.name = name;
    this.age = age;
  }
  
  public String getName() {
    return name;
  }
  
  public int getAge() {
    return age;
  }
  
  @Override
  public String toString() {
    return name + " (" + age + ")";
  }
}

public class QuickSortObjects {
  public static void quickSort(Person[] people, int low, int high, Comparator<Person> comparator) {
    if (low < high) {
      int pivotIndex = partition(people, low, high, comparator);
      quickSort(people, low, pivotIndex - 1, comparator);
      quickSort(people, pivotIndex + 1, high, comparator);
    }
  }
  
  private static int partition(Person[] people, int low, int high, Comparator<Person> comparator) {
    Person pivot = people[high];
    int i = low - 1;
    
    for (int j = low; j < high; j++) {
      // Use the comparator to compare objects
      if (comparator.compare(people[j], pivot) < 0) {
        i++;
        swap(people, i, j);
      }
    }
    
    swap(people, i + 1, high);
    return i + 1;
  }
  
  private static void swap(Person[] arr, int i, int j) {
    Person temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
  
  public static void main(String[] args) {
    Person[] people = {
      new Person("Alice", 25),
      new Person("Bob", 20),
      new Person("Charlie", 30),
      new Person("David", 22)
    };
    
    System.out.println("Original array:");
    for (Person person : people) {
      System.out.println(person);
    }
    
    // Sort by age using a comparator
    quickSort(people, 0, people.length - 1, Comparator.comparing(Person::getAge));
    
    System.out.println("\nSorted by age:");
    for (Person person : people) {
      System.out.println(person);
    }
    
    // Sort by name
    quickSort(people, 0, people.length - 1, Comparator.comparing(Person::getName));
    
    System.out.println("\nSorted by name:");
    for (Person person : people) {
      System.out.println(person);
    }
  }
}

This implementation uses Java’s Comparator interface to define how objects should be compared, making it flexible for different sorting criteria.

What’s Next?

Now that you’ve learned how to implement Quick Sort in Java, you might want to explore: