C++ partial_sort

Table of contents

Introduction

std::partial_sort algorithms are intended to be used for small constant numbers of [first, middle) selected elements.

::: Note The order of the remaining elements in the range [middle, last) is unspecified.

@startpikchr images/partial_sort_01.pikchr /til/cpp_partial_sort_01.svg boxht = 0.3 boxwid = 0.3 B5: box “5” fill yellow B7: box “7” fill yellow B4: box “4” fill yellow B2: box “2” fill blue B8: box “8” fill green B6: box “6” fill green B1: box “1” fill blue B9: box “9” fill green B0: box “0” fill blue B3: box “3” fill green move from 3rd box.s down box “2” fill blue arrow from 4th box.s to 11th box.n move from 1st box.s down 1.2 B20: box “0” fill blue right; B21: box “1” fill blue B22: box “2” fill blue move from B2.s down 1.5 B27: box “7” fill yellow; right B28: box “8” fill green B26: box “6” fill green B25: box “5” fill yellow B29: box “9” fill green B24: box “4” fill yellow B23: box “3” fill green arrow from 11th box to B22 chop arrow from B3 to B23 chop arrow from B9 to B29 chop arrow from B6 to B26 chop arrow from B8 to B28 chop arrow <- from 11th box.w left “3rd” “position” text “3rd element” with .s at B2.n + (0,0.2) arrow from last text to B2.n chop text “[0, 3)” big big at B20.w - (0.5,0) @endpikchr

  auto print = [](auto label, auto numbers) {
    fmt::print("{:20} ", label);
    for (const auto& number : numbers) {
      fmt::print("{:2} ", number);
    }
    fmt::print("\n");
  };

  std::vector<int> numbersRef{5,  7,  4,  2,  8,  6,  1,  9,  0, 3,
                              18, 15, 14, 10, 13, 11, 12, 17, 16};
  print("numbersRef", numbersRef);

  // Ascendent order
  auto numbers = numbersRef;
  std::partial_sort(begin(numbers), begin(numbers) + 2, end(numbers));
  print("partial_sort [0, 2)", numbers);

  numbers = numbersRef;
  std::partial_sort(begin(numbers), begin(numbers) + 3, end(numbers));
  print("partial_sort [0, 3)", numbers);

  numbers = numbersRef;
  std::partial_sort(begin(numbers), begin(numbers) + 4, end(numbers));
  print("partial_sort [0, 4)", numbers);

  // Descendent order
  numbers = numbersRef;
  std::partial_sort(begin(numbers), begin(numbers) + 3, end(numbers),
                    std::greater<>{});
  print("partial_sort [0, 3)D", numbers);

  numbers = numbersRef;
  std::partial_sort(begin(numbers) + 3, begin(numbers) + 8, end(numbers));
  print("partial_sort [3, 8)", numbers);

Possible output

numbersRef            5  7  4  2  8  6  1  9  0  3 18 15 14 10 13 11 12 17 16 
partial_sort [0, 2)   0  1  7  5  8  6  4  9  2  3 18 15 14 10 13 11 12 17 16 
partial_sort [0, 3)   0  1  2  7  8  6  5  9  4  3 18 15 14 10 13 11 12 17 16 
partial_sort [0, 4)   0  1  2  3  8  7  6  9  5  4 18 15 14 10 13 11 12 17 16 
partial_sort [0, 3)D 18 17 16  2  4  5  1  6  0  3  7  8  9 10 13 11 12 14 15 
partial_sort [3, 8)   5  7  4  0  1  2  3  6  9  8 18 15 14 10 13 11 12 17 16 

References

• title
• title
• title