99 lines
3.8 KiB
C++
99 lines
3.8 KiB
C++
/*
|
|
* Copyright (C) 2015 Apple Inc. All Rights Reserved.
|
|
*
|
|
* Redistribution and use in source and binary forms, with or without
|
|
* modification, are permitted provided that the following conditions
|
|
* are met:
|
|
* 1. Redistributions of source code must retain the above copyright
|
|
* notice, this list of conditions and the following disclaimer.
|
|
* 2. Redistributions in binary form must reproduce the above copyright
|
|
* notice, this list of conditions and the following disclaimer in the
|
|
* documentation and/or other materials provided with the distribution.
|
|
*
|
|
* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
|
|
* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
|
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
|
* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
|
|
* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
|
|
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
|
|
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
|
|
* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
|
|
* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
|
|
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
|
|
* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
|
|
*/
|
|
|
|
#pragma once
|
|
|
|
namespace WTF {
|
|
|
|
// Why would you want to use bubble sort? When you know that your input is already mostly
|
|
// sorted! This sort is guaranteed stable (it won't reorder elements that were equal), it
|
|
// doesn't require any scratch memory, and is the fastest available sorting algorithm if your
|
|
// input already happens to be sorted. This sort is also likely to have competetive performance
|
|
// for small inputs, even if they are very unsorted.
|
|
|
|
// We use this sorting algorithm for compiler insertion sets. An insertion set is usually very
|
|
// nearly sorted. It shouldn't take more than a few bubbles to make it fully sorted. We made
|
|
// this decision deliberately. Here's the performance of the testb3 Complex(64, 384) benchmark
|
|
// with the Air::InsertionSet doing no sorting, std::stable_sorting, and bubbleSorting:
|
|
//
|
|
// no sort: 8.8222 +- 0.1911 ms.
|
|
// std::stable_sort: 9.0135 +- 0.1418 ms.
|
|
// bubbleSort: 8.8457 +- 0.1511 ms.
|
|
//
|
|
// Clearly, bubble sort is superior.
|
|
//
|
|
// Note that the critical piece here is that insertion sets tend to be small, they must be
|
|
// sorted, the sort must be stable, they are usually already sorted to begin with, and when they
|
|
// are unsorted it's usually because of a few out-of-place elements.
|
|
|
|
template<typename IteratorType, typename LessThan>
|
|
void bubbleSort(IteratorType begin, IteratorType end, const LessThan& lessThan)
|
|
{
|
|
for (;;) {
|
|
bool changed = false;
|
|
ASSERT(end >= begin);
|
|
size_t limit = end - begin;
|
|
for (size_t i = limit; i-- > 1;) {
|
|
if (lessThan(begin[i], begin[i - 1])) {
|
|
std::swap(begin[i], begin[i - 1]);
|
|
changed = true;
|
|
}
|
|
}
|
|
if (!changed)
|
|
return;
|
|
// After one run, the first element in the list is guaranteed to be the smallest.
|
|
begin++;
|
|
|
|
// Now go in the other direction. This eliminates most sorting pathologies.
|
|
changed = false;
|
|
ASSERT(end >= begin);
|
|
limit = end - begin;
|
|
for (size_t i = 1; i < limit; ++i) {
|
|
if (lessThan(begin[i], begin[i - 1])) {
|
|
std::swap(begin[i], begin[i - 1]);
|
|
changed = true;
|
|
}
|
|
}
|
|
if (!changed)
|
|
return;
|
|
// Now the last element is guaranteed to be the largest.
|
|
end--;
|
|
}
|
|
}
|
|
|
|
template<typename IteratorType>
|
|
void bubbleSort(IteratorType begin, IteratorType end)
|
|
{
|
|
bubbleSort(
|
|
begin, end,
|
|
[](auto& left, auto& right) {
|
|
return left < right;
|
|
});
|
|
}
|
|
|
|
} // namespace WTF
|
|
|
|
using WTF::bubbleSort;
|