Quick Sort in Ascending Order in Java

Author:

Quick Sort is a widely used sorting algorithm that is based on the divide-and-conquer paradigm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. Let's implement the Quick Sort algorithm to sort an array of integers in ascending order. 

Step-by-step Implementation and Explanation

Partition: The array is partitioned into three parts: 

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

Recursive Sort: Recursively sort the elements that are less than the pivot and those greater than the pivot. 

Combine: The base case for the recursion is arrays of size zero or one, which never need to be sorted. 

Java Program to Implement Quick Sort in Ascending Order

public class QuickSortAscending {
    
    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 ascending order:");
        printArray(arr);
    }
    
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Find pivot element such that element smaller than pivot are on the left
            // and greater than pivot are on the right
            int pi = partition(arr, low, high);
            
            // Recursively sort elements before and after pivot
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];  // Taking last element as pivot
        int i = (low - 1);      // Index of smaller element
        
        for (int j = low; j < high; j++) {
            // If the current element is smaller than or equal to pivot
            if (arr[j] <= pivot) {
                i++;
                
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        
        // Swap arr[i+1] and arr[high] (or pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }
    
    // Utility function to print the array
    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 ascending order:
10 30 40 50 70 80 90

Explanation of the Code: 

quickSort Function: This is the main function that implements Quick Sort. low is the starting index and high is the ending index of the array being processed. 

partition Function: This function takes the last element as the pivot, places it at its correct position in the sorted array, and places all smaller elements to its left and all greater elements to its right.

Swapping: Within the partition function, we see multiple instances of swapping elements. Swapping is the primary operation in the partitioning process where we segregate elements based on their relation to the pivot. 

Quick Sort is an efficient, in-place sorting algorithm. While its worst-case time complexity is O(n^2), with good implementation and in average scenarios, its expected time complexity is O(n log n). The above code demonstrates the algorithm's capabilities and can be modified or extended for custom objects and conditions.

Comments

Post a Comment

Leave Comment