// Sigue paso a paso las dos particiones de la clase.
#include <cstddef>
#include <iostream>
#include <utility>
#include <vector>

namespace {

void print_items(const std::vector<int>& items) {
    for (std::size_t i = 0; i < items.size(); i++) {
        std::cout << (i == 0 ? "" : " ") << items[i];
    }
}

void trace_first(std::vector<int> items) {
    std::cout << "pivote = primer elemento = " << items[0] << "\n";
    int pivot = items[0];
    std::size_t boundary = 0;
    for (std::size_t scan = 1; scan < items.size(); scan++) {
        if (items[scan] < pivot) {
            boundary++;
            std::swap(items[boundary], items[scan]);
        }
        std::cout << "  scan=" << scan << " boundary=" << boundary << "  ";
        print_items(items);
        std::cout << "\n";
    }
    std::swap(items[0], items[boundary]);
    std::cout << "  pivote a su lugar ";
    print_items(items);
    std::cout << "  (posición " << boundary << ")\n";
}

void trace_three(std::vector<int> items, int pivot) {
    std::cout << "pivote = " << pivot << "\n";
    std::size_t less_end = 0;
    std::size_t scan = 0;
    std::size_t greater_start = items.size();
    while (scan < greater_start) {
        if (items[scan] < pivot) {
            std::swap(items[less_end], items[scan]);
            less_end++;
            scan++;
        } else if (pivot < items[scan]) {
            greater_start--;
            std::swap(items[scan], items[greater_start]);
        } else {
            scan++;
        }
        std::cout << "  menores_fin=" << less_end << " scan=" << scan << " mayores_inicio="
                  << greater_start << "  ";
        print_items(items);
        std::cout << "\n";
    }
}

}  // namespace

int main() {
    trace_first({5, 2, 8, 1, 9, 3, 7, 4});
    trace_three({3, 5, 3, 1, 3, 2, 5, 3}, 3);
    return 0;
}