Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/yeremyacuna/LYNX/llms.txt

Use this file to discover all available pages before exploring further.

LYNX organizes its sorting logic into two distinct layers. The first layer, AdvancedSorts<T> (in include/AdvancedSorts.h), provides fully generic HeapSort and ShellSort that operate on any raw array T* arr and accept optional lambda comparators. The second layer, AdvancedOrders<T> (in include/AdvancedOrders.h), provides domain-specific algorithms — QuickSort, MergeSort, TimSort, and CountingSort — that work directly on LinkedList<T>* of passengers, drivers, or raw Trip[] arrays, handling the extract-sort-rebuild cycle internally. Together, these two classes cover every sorting need in the system without relying on the C++ Standard Library.

​
Generic Algorithms (AdvancedSorts<T>)

AdvancedSorts<T> lives in include/AdvancedSorts.h. Every method is static and operates on a raw C-style array T* arr of a given size. A private swapTo helper handles all element exchanges. Two algorithms are available: HeapSort and ShellSort, each in a default form and a custom-comparator form.

​
HeapSort

static void heapSort(T* arr, int size);

template<typename Compare>
static void heapSort(T* arr, int size, Compare compare);
HeapSort runs in O(n log n) time in all cases and uses O(1) extra space. The default overload builds a max-heap using operator>, then repeatedly swaps the root (the current maximum) to the end of the unsorted region and calls heapify to restore the heap property. The comparator overload passes compare down into heapify, where it replaces the > check. Inside heapify, the condition compare(arr[root], arr[child]) triggers a swap if true — meaning the child is treated as the heap’s “larger” node and migrates toward the root, while the root element migrates toward the end of the array. Because heap extraction places the root at the tail on each pass, the elements that compare never selects as “larger” end up at the front. In practice: compare(a, b) = true means a should appear before b in the final sorted array. To sort descending by rating, pass a.getRating() > b.getRating(). HeapSort comparator signature: 
bool compare(const T& a, const T& b); // returns true if a should appear before b

​
ShellSort

static void shellSort(T* arr, int size);

template<typename Compare>
static void shellSort(T* arr, int size, Compare compare);
ShellSort uses a halving gap sequence (gap = size/2, then gap /= 2 each pass) and runs in O(n log²n) average time with O(1) space. The default overload uses operator> to compare; the comparator overload passes compare into the inner while-loop condition.
ShellSort and HeapSort use opposite comparator conventions. In shellSort, compare(a, b) replaces the > guard in the shift loop: when compare(a, b) returns true, element a is shifted rightward past b, so b ends up at the lower index — meaning b comes before a in the output. This is the opposite of heapSort, where compare(a, b) = true means a comes before b. To sort descending by rating with shellSort, pass a.getRating() < b.getRating(); with heapSort, pass a.getRating() > b.getRating().
ShellSort comparator signature: 
bool compare(const T& a, const T& b); // returns true if a should appear AFTER b (b comes first)

​
Usage Examples

Driver* arr = driverList->toArray();
int n = driverList->getSize();

// heapSort: compare(a,b)=true means a comes BEFORE b
// Sort drivers by rating descending with heapSort
AdvancedSorts<Driver>::heapSort(arr, n, [](const Driver& a, const Driver& b) {
    return a.getRating() > b.getRating(); // higher rating first
});

// shellSort: compare(a,b)=true means a is shifted right — b comes BEFORE a
// Sort drivers by rating descending with shellSort
AdvancedSorts<Driver>::shellSort(arr, n, [](const Driver& a, const Driver& b) {
    return a.getRating() < b.getRating(); // shift lower ratings right → higher ratings first
});

driverList->fromArray(arr, n);
delete[] arr;

​
Domain-Specific Algorithms (AdvancedOrders<T>)

AdvancedOrders<T> lives in include/AdvancedOrders.h. Every method is static. The LinkedList<T>* overloads extract the list into a heap-allocated array, perform the sort in-place, then call list->clear() and rebuild with pushBack. The Trip* overload operates directly on the caller-provided raw array. All sort orders are descending.
MethodAlgorithmInputSort KeyOrder
shellSortDriverssByEarnings(LinkedList<Driver>*)Shell SortLinkedList<Driver>totalEarningsDescending
quickSortPassengersBySpent(LinkedList<Passenger>*)Quick SortLinkedList<Passenger>totalSpentDescending
mergeSortTripsByPrice(Trip* arr, int n)Merge SortRaw Trip[]priceDescending
timSortPassengersByTrips(LinkedList<Passenger>*)Tim Sort (Insertion + Merge)LinkedList<Passenger>totalTripsDescending
countingSortDriversByTrips(LinkedList<Driver>*)Counting SortLinkedList<Driver>totalTripsDescending
The method name shellSortDriverssByEarnings contains a double-s (Driverss) — this is a typo in the source file (AdvancedOrders.h) that has been preserved as-is. Call sites must use the exact name shellSortDriverssByEarnings with two s’s or the code will not compile.

​
QuickSort — passengers by total spent

Pivot is the last element of the current partition. The particionar helper reorders elements in-place: anything with getTotalSpent() >= pivote moves to the left side, placing larger spenders first. Recursion continues on the two sub-partitions.
  • Best / Average: O(n log n) — balanced splits
  • Worst: O(n²) — already-sorted or reverse-sorted input
  • Space: O(log n) stack frames

​
MergeSort — trips by price

Classic divide-and-conquer. mergeSortHelper recursively splits the Trip array to single-element subarrays, then fusionarTrips merges adjacent halves using a temporary left and right buffer, placing higher-priced trips first (izq[i].getPrice() >= der[j].getPrice()).
  • Time: O(n log n) in all cases
  • Space: O(n) — temporary merge buffers allocated per merge step
  • Stable: Yes — equal prices preserve original order

​
TimSort — passengers by trip count

A hybrid algorithm combining Insertion Sort with Merge Sort. The array is first divided into blocks of 32 elements (RUN = 32), each sorted individually by insertionSortBloque (descending by getTotalTrips()). The sorted runs are then merged in doubling passes using fusionarPasajeros, identical in structure to the MergeSort merge step.
  • Best: O(n) — nearly sorted input
  • Average / Worst: O(n log n)
  • Space: O(n) — merge buffers
  • Stable: Yes

​
CountingSort — drivers by trip count

CountingSort is an integer-key, non-comparison sort. It finds maxViajes (the maximum getTotalTrips() across all drivers), allocates a zero-initialized count array of size maxViajes + 1, then fills a result array by iterating from maxViajes down to 0 — producing a descending sort. The count array is decremented on each placement to handle duplicate trip counts correctly.
  • Time: O(n + k) where k = maxViajes
  • Space: O(k) — count array + result buffer
  • Stable: Yes (preserves relative order of drivers with equal trip counts)

​
Usage Example

// Sort all drivers by earnings (highest first)
AdvancedOrders<Driver>::shellSortDriverssByEarnings(&driverList);

// Sort passengers by number of trips
AdvancedOrders<Passenger>::timSortPassengersByTrips(&passengerList);

// Sort a raw array of trips by price
Trip* trips = new Trip[n];
// ... fill trips ...
AdvancedOrders<Trip>::mergeSortTripsByPrice(trips, n);
delete[] trips;

​
Complexity Summary

AlgorithmBestAverageWorstSpaceStable
HeapSortO(n log n)O(n log n)O(n log n)O(1)No
ShellSortO(n log n)O(n log²n)O(n²)O(1)No
QuickSortO(n log n)O(n log n)O(n²)O(log n)No
MergeSortO(n log n)O(n log n)O(n log n)O(n)Yes
TimSortO(n)O(n log n)O(n log n)O(n)Yes
CountingSortO(n+k)O(n+k)O(n+k)O(k)Yes

Build docs developers (and LLMs) love

Get started for freeTalk to us