sort.hpp

Go to the documentation of this file.

// Copyright (c) 2024 Simons Foundation
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0.txt
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// Authors: Thomas Hahn, Olivier Parcollet, Nils Wentzell, chuffa

 
#ifndef _ITERTOOLS_SORT_HPP
#define _ITERTOOLS_SORT_HPP
 
#include <algorithm>
#include <cstddef>
#include <functional>
#include <iterator>
#include <ranges>
 
namespace itertools {


  template <std::forward_iterator ForwardIt, class Compare = std::less<>>
  std::size_t bubble_sort(ForwardIt first, ForwardIt last, Compare comp = {}) {
    if (first == last) { return 0; }
    std::size_t n_swaps = 0;
    for (ForwardIt sorted = first; first != last; last = sorted) {
      sorted = first;
      for (ForwardIt curr = first, prev = first; ++curr != last; ++prev) {
        if (comp(*curr, *prev)) {
          std::iter_swap(curr, prev);
          sorted = curr;
          ++n_swaps;
        }
      }
    }
    return n_swaps;
  }

  template <std::bidirectional_iterator BidirIt, class Compare = std::less<>>
  std::size_t insertion_sort(BidirIt first, BidirIt last, Compare comp = {}) {
    if (first == last) { return 0; }
    std::size_t swaps = 0;
    for (BidirIt i = std::next(first); i != last; ++i) {
      for (BidirIt j = i; j != first && comp(*j, *std::prev(j)); --j) {
        std::iter_swap(std::prev(j), j);
        ++swaps;
      }
    }
    return swaps;
  }

  template <std::ranges::forward_range Range, class Compare = std::less<>>
  std::size_t bubble_sort(Range &&rng, Compare comp = {}) { // NOLINT (ranges need not be forwarded)
    return bubble_sort(std::ranges::begin(rng), std::ranges::end(rng), comp);
  }

  template <std::ranges::bidirectional_range Range, class Compare = std::less<>>
  std::size_t insertion_sort(Range &&rng, Compare comp = {}) { // NOLINT (ranges need not be forwarded)
    return insertion_sort(std::ranges::begin(rng), std::ranges::end(rng), comp);
  }

 
} // namespace itertools
 
#endif // _ITERTOOLS_SORT_HPP