15 Ordenação

OBS: questões de estabilidade na ordenação são omitidas neste livro.

15.1 Bubble sort

template <std::forward_iterator It>
void bubblesort(It begin, It end)
{
  for (; begin != end; --end)
    for (auto left = begin, right = std::next(left);
         right != end;
         left = right++)
      if (*left > *right)
        std::iter_swap(left, right);
}

---

Exercícios:

1. Altere o código da função bubblesort para interromper as passagens quando não houver mais trocas.
2. Compare o tempo de execução das duas versões da função bubblesort para vetores muito grandes.

15.2 Shaker sort

template <std::bidirectional_iterator It>
void shakersort(It begin, It end)
{
  while (true)
  {
    for (auto left = begin, right = std::next(left);
         right != end;
         left = right++)
      if (*left > *right)
        std::iter_swap(left, right);
    if (begin == --end)
      return;

    for (auto right = std::prev(end), left = std::prev(right);
         right != begin;
         right = left--)
      if (*left > *right)
        std::iter_swap(left, right);
    if (++begin == end)
      return;
  }
}

---

Exercícios:

1. Altere o código da função shakersort para interromper as passagens quando não houver mais trocas.
2. Compare o tempo de execução das duas versões da função shakersort para vetores muito grandes. Qual algoritmo se beneficia mais desta interrupção: bubble sort ou shaker sort?

15.3 Selection sort

template <std::forward_iterator It>
void selectionsort(It begin, It end)
{
  for (auto it = begin; it != end; ++it)
    std::iter_swap(it, std::min_element(it, end));
}

15.4 Insertion sort

template <std::bidirectional_iterator It>
void insertionsort(It begin, It end)
{
  for (auto it = std::next(begin); it != end; ++it)
    for (auto right = it, left = std::prev(right);
         right != begin && *left > *right;
         right = left--)
      std::iter_swap(left, right);
}

15.5 Shell sort

template <std::integral T> auto knuth_seq_last(T length) {
  T h = 1;
  while (h < length)
    h = 3 * h + 1;
  return h / 3;
}

template <std::random_access_iterator It>
void shellsort(It begin, It end)
{
  const auto length = std::distance(begin, end);
  for (auto h = knuth_seq_last(length); h > 0; h = h / 3)
    for (auto it = std::next(begin, h); it != end; ++it)
      for (auto right = it, left = std::prev(right, h);
           std::distance(begin, right) >= h && *left > *right;
           right = std::exchange(left, std::prev(left, h)))
        std::iter_swap(left, right);
}

Exercícios:

1. Ignorando questões de desempenho, a função shellsort poderia ser implementada para iteradores bidirecionais (e sem acesso aleatório). Justifique a necessidade de acesso aleatório para manter as vantagens do shell sort em comparação com o insertion sort.

15.6 Quick sort

template <std::bidirectional_iterator It>
void quicksort(It begin, It end)
{
  if (begin == end)
    return;

  auto left = begin;
  auto right = std::prev(end);

  const auto pivot_value = *left;

  while (true)
  {
    while (left != right && *right >= pivot_value)
      --right;
    if (left == right)
      break;
    std::iter_swap(left++, right);

    while (left != right && *left <= pivot_value)
      ++left;
    if (left == right)
      break;
    std::iter_swap(left, right--);
  }

  quicksort(begin, left);
  quicksort(std::next(left), end);
}

15.7 Merge sort

template <std::forward_iterator It>
void merge(It begin, It mid, It end)
{
  std::vector<std::iter_value_t<It>> tmp;

  auto it1 = begin, it2 = mid;
  while (it1 != mid && it2 != end)
    tmp.push_back(std::move(*it1 < *it2 ? *it1++ : *it2++));

  std::move(it1, mid, back_inserter(tmp));
  std::move(it2, end, back_inserter(tmp));
  std::move(tmp.begin(), tmp.end(), begin);
}

template <std::random_access_iterator It>
void mergesort(It begin, It end)
{
  const auto length = std::distance(begin, end);
  if (length < 2)
    return;

  const auto mid = std::next(begin, length / 2);

  merge_sort(begin, mid);
  merge_sort(mid, end);

  merge(begin, mid, end);
}

Exercícios:

1. Discuta as desvantagens de permitir que a função mergesort aceite iteradores unidirecionais ao invés de requerer acesso aleatório.
2. Implemente o algoritmo merge sort evitando as inúmeras alocações de memória temporária.