// Quicksort con el primer elemento como pivote. Ya viene hecho: es el que van a hacer
// sufrir en la sesión 1. No lo usen para otra cosa.
#ifndef FIXED_PIVOT_H
#define FIXED_PIVOT_H

#include <cstddef>
#include <utility>
#include <vector>

template <typename T, typename Less>
void quick_first_range(std::vector<T>& items, std::size_t lo, std::size_t hi, Less& less) {
    if (hi - lo < 2) {
        return;
    }
    std::size_t boundary = lo;
    for (std::size_t scan = lo + 1; scan < hi; scan++) {
        if (less(items[scan], items[lo])) {
            boundary++;
            std::swap(items[boundary], items[scan]);
        }
    }
    std::swap(items[lo], items[boundary]);
    quick_first_range(items, lo, boundary, less);
    quick_first_range(items, boundary + 1, hi, less);
}

template <typename T, typename Less>
void quick_sort_first(std::vector<T>& items, Less less) {
    quick_first_range(items, 0, items.size(), less);
}

#endif