# 4. Lomuto Quick Sort in C++

This section explains how the "divide and conquer" strategy of Quick Sort is implemented in C++. The logic is split into two primary functions: `quickSort()` which handles the recursive division, and `partition()` which rearranges the array using the popular **Lomuto partition scheme**.

### The C++ Code Implementation

Here is the complete code for a Quick Sort implementation using `std::vector`.

```cpp
#include <iostream>
#include <vector>
#include <utility> // For std::swap

// Utility function to print a vector
void printVector(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

// This function implements the Lomuto partition scheme. It takes the last 
// element as pivot and places it at its correct position in the sorted array.
int partition(std::vector<int>& arr, int low, int high) {
    // Choose the last element as the pivot (key to Lomuto)
    int pivot = arr[high]; 
    
    // Index of the smaller element, acting as a "wall"
    int i = (low - 1); 

    for (int j = low; j <= high - 1; j++) {
        // If the current element is smaller than the pivot
        if (arr[j] < pivot) {
            i++; // Move the wall to the right
            std::swap(arr[i], arr[j]);
        }
    }
    // Place the pivot in its correct position after the wall
    std::swap(arr[i + 1], arr[high]);
    return (i + 1);
}

// The main recursive function that implements Quick Sort
void quickSort(std::vector<int>& arr, int low, int high) {
    // Base case: if the array has 1 or 0 elements, it's already sorted
    if (low < high) {
        // pi is the partitioning index from the Lomuto partition
        int pi = partition(arr, low, high);

        // Separately sort elements before and after the partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Main driver function
int main() {
    std::vector<int> data = {6, 5, 3, 1, 8, 7, 2, 4};
    std::cout << "Original array: ";
    printVector(data);

    quickSort(data, 0, data.size() - 1);

    std::cout << "Sorted array:   ";
    printVector(data);

    return 0;
}
```
### Output
```
Original array: 6 5 3 1 8 7 2 4 
Sorted array:   1 2 3 4 5 6 7 8 
```
### Code Breakdown

#### The `quickSort()` Function: The Recursive Driver
This function orchestrates the **"Divide"** phase of the algorithm.
1.  **Base Case**: The recursion continues as long as `low < high`. If `low >= high`, it means the sub-array has one or zero elements, which is inherently sorted.
2.  **Partition**: It calls the `partition()` function. This function rearranges the sub-array and returns the index `pi` where the pivot element is now correctly placed.
3.  **Recurse**: It calls itself twice for the two sub-arrays created by the partition: one for the elements to the left of the pivot (`low` to `pi - 1`) and one for the elements to the right (`pi + 1` to `high`). Because this uses the Lomuto scheme, the pivot at `pi` is guaranteed to be in its final place and can be excluded from recursion.

#### The `partition()` Function (Lomuto Scheme)
This function implements the well-known **Lomuto partition scheme**. It is where the key logic of rearranging elements occurs and can be seen as the **"Conquer"** step, as it correctly places one element (the pivot) at a time.
1.  **Pivot Selection**: It selects the **last element** of the sub-array (`arr[high]`) as the **pivot**. This is the defining starting point for this version of Lomuto.
2.  **Rearranging Loop**: It maintains an index `i` (the "wall") which represents the boundary for elements smaller than the pivot. It iterates through the sub-array with another index `j` (the "scanner"). If it finds an element `arr[j]` that is smaller than the pivot, it moves the wall (`i++`) and swaps `arr[j]` with the element at the new wall position, effectively expanding the "smaller than pivot" section.
3.  **Final Pivot Placement**: After the loop finishes, all elements smaller than the pivot are at the beginning of the sub-array. The pivot (still at `arr[high]`) is then swapped with the element at `arr[i + 1]`. This places the pivot exactly where it belongs in the sorted array.
4.  **Return Index**: The function returns the new index of the pivot (`i + 1`), so the `quickSort` function knows where to split the array for its next recursive calls.