Program Code

public class QuickSort {
    
    /**
     * Sorts an array using the Quick Sort algorithm.
     *
     * @param array the array to be sorted
     * @param low the starting index
     * @param high the ending index
     */
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }
    
    /**
     * Partitions the array and returns the pivot index.
     *
     * @param array the array to be partitioned
     * @param low the starting index
     * @param high the ending index
     * @return the index of the pivot
     */
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = (low - 1);
        
        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                swap(array, i, j);
            }
        }
        swap(array, i + 1, high);
        return i + 1;
    }
    
    /**
     * Swaps two elements in an array.
     *
     * @param array the array containing the elements
     * @param i the index of the first element
     * @param j the index of the second element
     */
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    /**
     * Main method to test the Quick Sort implementation.
     *
     * @param args command line arguments
     */
    public static void main(String[] args) {
        int[] array = {10, 7, 8, 9, 1, 5};
        int n = array.length;
        
        System.out.println("Original array:");
        printArray(array);
        
        quickSort(array, 0, n - 1);
        
        System.out.println("Sorted array:");
        printArray(array);
    }
    
    /**
     * Prints the elements of the array.
     *
     * @param array the array to be printed
     */
    private static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Explanation of the Program Structure

The Quick Sort algorithm is an efficient sorting algorithm that follows the divide-and-conquer principle. The main components of the program are as follows:

1. quickSort Method:
   This method is the main sorting function that takes the array, the starting index (low), and the ending index (high) as parameters. It recursively partitions the array around a pivot element until the entire array is sorted.
2. partition Method:
   This method rearranges the elements in the array based on the pivot element. It places all elements smaller than or equal to the pivot on its left and all larger elements on its right. The method returns the index of the pivot after partitioning.
3. swap Method:
   This helper method swaps two elements in the array, which is essential for rearranging elements during partitioning.
4. Main Method:
   This method serves as the entry point of the program. It initializes an array, prints the original array, calls the quickSort method to sort it, and then prints the sorted array.
5. printArray Method:
   This method prints the elements of the array for easy visualization of the results before and after sorting.

Conclusion

The Quick Sort algorithm is a widely used sorting technique due to its efficiency and ease of implementation. The provided Java program demonstrates its structure and functionality, making it a valuable tool for sorting arrays in various applications.