What is the time complexity of the quicksort algorithm, and what is its worst-case scenario?

The quicksort algorithm is a widely used sorting algorithm that uses a divide-and-conquer approach to sort an array of elements in O(n log n) time on average, where n is the number of elements in the array. The algorithm works by selecting a pivot element from the array and partitioning the array into two subarrays, one containing elements less than or equal to the pivot, and one containing elements greater than the pivot. The algorithm then recursively sorts the two subarrays.

The time complexity of quicksort is O(n log n) on average, making it one of the fastest sorting algorithms for large datasets. This is because the algorithm’s performance is dependent on the size of the subarrays being sorted, rather than the total number of elements in the array. In other words, the algorithm’s time complexity grows logarithmically with the size of the subarrays.

However, the worst-case scenario for quicksort occurs when the pivot element is consistently chosen to be the minimum or maximum element in the array, resulting in unbalanced partitioning of the subarrays. In this case, the time complexity of the algorithm becomes O(n²), which is much less efficient than the average case. The worst-case scenario can be avoided by using a randomized pivot selection method or by selecting the pivot element from a median-of-three sample.

Here is an example of quicksort implementation in Java:

public static void quicksort(int[] arr, int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high);
        quicksort(arr, low, pivot-1);
        quicksort(arr, pivot+1, high);
    }
}

private 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++;
            swap(arr, i, j);
        }
    }
    swap(arr, i+1, high);
    return i+1;
}

private static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

In this example, we implement the quicksort algorithm in Java using a recursive approach. The quicksort function takes in an integer array arr, a lower index low, and an upper index high. If the lower index is less than the upper index, the function selects a pivot element using the partition function and recursively sorts the subarrays to the left and right of the pivot.

The partition function takes in the same inputs as quicksort and partitions the array into two subarrays by selecting the pivot element and rearranging the elements such that all elements less than the pivot are to the left of it and all elements greater than the pivot are to the right of it.

Overall, the quicksort algorithm has an average time complexity of O(n log n) and a worst-case time complexity of O(n²) when the pivot selection leads to unbalanced partitioning.