# 1. Introduction

*QuickSort* is a divide-and-conquer sorting algorithm that 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 recursively sorted.

# 2. Program Steps

1. Choose a ‘pivot’ element from the array.

2. Partition the elements into two sub-arrays according to whether they are less than or greater than the pivot.

3. Recursively apply the above steps to the sub-arrays.

4. Combine (concatenate) the sub-arrays and the pivot to get the sorted array.

# 3. Code Program

```
public class QuickSort {
// This function takes last element as pivot, places the pivot element at its correct position
// in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to the right of pivot.
public static int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1); // index of smaller element
for (int j = low; j < high; j++) {
// If 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;
}
// Main function that sorts arr[low..high] using partition()
public static void sort(int arr[], int low, int high) {
if (low < high) {
// pi is partitioning index, arr[pi] is now at the right place
int pi = partition(arr, low, high);
// Recursively sort elements before partition and after partition
sort(arr, low, pi - 1);
sort(arr, pi + 1, high);
}
}
// Driver method
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
// Call sort method to sort the array
sort(arr, 0, arr.length - 1);
// Print the sorted array
System.out.println("Sorted array:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
```

### Output:

Sorted array: 1 5 7 8 9 10

# 4. Step By Step Explanation

1. The *partition* function is the heart of the *QuickSort* algorithm. It selects the last element as the pivot, then places all smaller elements to the left and all larger elements to the right.

2. Within the *partition* function, the algorithm iterates over the elements, comparing them to the pivot, and swapping as necessary to ensure all elements less than the pivot come before all elements greater than the pivot.

3. The pivot's final position (returned by the *partition* function) is its sorted position in the array.

4. The *sort* function then recursively applies the *QuickSort* logic to the elements before and after the pivot.

5. In the *main* method, an unsorted array is initialized, the *sort* method is called to sort the array, and then the sorted array is printed.

The *QuickSort* algorithm is often faster in practice than other O(n log n) algorithms like *Merge Sort* or *Heap Sort*. However, its worst-case time complexity is O(n^2), which can occur when the array is already sorted, and the last element is always chosen as the pivot. There are variations of *QuickSort* that pick a random element as the pivot or use a median-of-three strategy to mitigate these worst-case scenarios.