mirror of
https://github.com/SerenityOS/serenity.git
synced 2025-01-22 09:21:57 -05:00
4f6f65d1f9
Previously, it ignored 'start', sorting from the array's beginning. This caused unintended changes and slower performance. Fix ensures sorting stays within 'start' and 'end' indices only. (cherry picked from commit 356016c626546aeb51722fe9ca5bb6a769bfe762)
45 lines
1.3 KiB
C++
45 lines
1.3 KiB
C++
/*
|
|
* Copyright (c) 2022, Marc Luqué <marc.luque@outlook.com>
|
|
*
|
|
* SPDX-License-Identifier: BSD-2-Clause
|
|
*/
|
|
|
|
#pragma once
|
|
|
|
#include <AK/Concepts.h>
|
|
#include <AK/StdLibExtras.h>
|
|
|
|
namespace AK {
|
|
|
|
// Standard Insertion Sort, with `end` inclusive!
|
|
template<typename Collection, typename Comparator, typename T = decltype(declval<Collection>()[declval<int>()])>
|
|
void insertion_sort(Collection& col, ssize_t start, ssize_t end, Comparator comparator)
|
|
requires(Indexable<Collection, T>)
|
|
{
|
|
for (ssize_t i = start + 1; i <= end; ++i) {
|
|
for (ssize_t j = i; j > start && comparator(col[j], col[j - 1]); --j)
|
|
swap(col[j], col[j - 1]);
|
|
}
|
|
}
|
|
|
|
template<typename Collection, typename Comparator, typename T = decltype(declval<Collection>()[declval<int>()])>
|
|
void insertion_sort(Collection& collection, Comparator comparator)
|
|
requires(Indexable<Collection, T>)
|
|
{
|
|
if (collection.size() == 0)
|
|
return;
|
|
insertion_sort(collection, 0, collection.size() - 1, move(comparator));
|
|
}
|
|
|
|
template<typename Collection, typename T = decltype(declval<Collection>()[declval<int>()])>
|
|
void insertion_sort(Collection& collection)
|
|
requires(Indexable<Collection, T>)
|
|
{
|
|
if (collection.size() == 0)
|
|
return;
|
|
insertion_sort(collection, 0, collection.size() - 1, [](auto& a, auto& b) { return a < b; });
|
|
}
|
|
|
|
}
|
|
|
|
using AK::insertion_sort;
|