Can you explain how the quicksort algorithm works?

The Quick Sort algorithm works on the principle of "divide and conquer." It selects a pivot element from the array and rearranges the elements so that all elements less than the pivot are on the left, and all greater are on the right. Then it recursively applies the same operation to the subarrays on the left and right of the pivot.

Main steps:

1. Choose a pivot element (for example, the last element of the array).
2. Partition the array into two parts: elements less than the pivot and elements greater than the pivot.
3. Recursively sort both parts.

Example in C++:

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                std::swap(arr[i], arr[j]);
            }
        }
        std::swap(arr[i + 1], arr[high]);
        int pi = i + 1;

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}