Quick Sort in Descending Order in Java

Author:

Quick Sort is a renowned and efficient sorting algorithm built upon the divide-and-conquer strategy. Fundamentally, it selects a 'pivot' element from the array and subsequently partitions the other elements into two sub-arrays based on whether they're greater or less than the pivot. Following this, the sub-arrays are sorted through recursive methods. In this guide, we'll walk through the process of implementing the Quick Sort algorithm to sort an array of integers in descending order. 

Step-by-step Implementation and Explanation

Partition: The array is sectioned into three segments: 

  • Elements greater than the pivot. 
  • The pivot itself. 
  • Elements less than the pivot. 

Recursive Sort: The elements greater than the pivot and those less than the pivot are sorted recursively. 

Combine: Arrays of size zero or one act as the base case for the recursion. These arrays don't need sorting.

Java Program for Quick Sort in Descending Order

public class QuickSortDescending {

    public static void main(String[] args) {
        int[] arr = {10, 80, 30, 90, 40, 50, 70};

        System.out.println("Unsorted array:");
        printArray(arr);

        quickSort(arr, 0, arr.length - 1);

        System.out.println("\nSorted array in descending order:");
        printArray(arr);
    }

    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);
        }
    }

    public 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;
    }

    public static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Output: 

Unsorted array:
10 80 30 90 40 50 70

Sorted array in descending order:
90 80 70 50 40 30 10

Explanation of the Code: 

quickSort Function: This is the primary function that enacts Quick Sort. low marks the starting index, while high denotes the ending index of the array in play. 

partition Function: This function chooses the final element as the pivot, accurately positions it in the sorted array, and then positions all larger elements on its left and all the smaller ones to its right. 

Swapping: The partition function features several instances of element swapping. This is the essential operation in the partitioning phase, wherein we categorize elements depending on their relation to the pivot.

Comments

Post a Comment

Leave Comment