shell_short_variants.cc

template<typename T>
void ShellSortFibonacci(vector<T> &list) {
  vector<int> gap_sequence;
  int exponent = 2;

  while (fibonacci(exponent) < list.size()) {
    int result = fibonacci(exponent);
    exponent++;
    gap_sequence.push_back(result);
  }

  // Iterate downwards through each of the potential gap sequences.
  for (int gap_index = sizeof(gap_sequence) / sizeof(gap_sequence[0]) - 1; gap_index >= 0; --gap_index) {
    int gap = gap_sequence[gap_index];

    // Do the movement, if the gap == 1, performs an ordinary insertion sort.
    for (int index = gap; index < list.size(); index++) {
      T temp = move(list[index]);

      int move_index = index;

      for (;
          move_index >= gap && temp < list[move_index - gap];
          move_index -= gap) {
        list[move_index] = move(list[move_index - gap]);
      }
      list[move_index] = move(temp);
    }
  }
}

template<typename T>
void ShellSortPapernov(vector<T> &list) {
  int gap = 1;
  int exponent = 0;
  while (pow(2, exponent) + 1 < list.size()) ++exponent;
  gap = static_cast<int>(pow(2, exponent) + 1);

  while (gap >= 1) {
    for (int index = gap; index < list.size(); index++) {
      T temp = move(list[index]);

      int move_index = index;

      for (;
          move_index >= gap && temp < list[move_index - gap];
          move_index -= gap) {
        list[move_index] = move(list[move_index - gap]);
      }
      list[move_index] = move(temp);
    }
    gap = static_cast<int>(pow(2, --exponent)); // Prefix with 1: Just remove + 1 because we already prefixed it.
  }
}

template<typename T>
void ShellSortHibbard(vector<T> &list) {
  int gap = 0;
  int exponent = 0;
  while (pow(2, exponent) - 1 < list.size()) ++exponent;
  gap = static_cast<int>(pow(2, exponent) - 1);

  while (gap >= 1) {
    for (int index = gap; index < list.size(); index++) {
      T temp = move(list[index]);

      int move_index = index;

      for (;
          move_index >= gap && temp < list[move_index - gap];
          move_index -= gap) {
        list[move_index] = move(list[move_index - gap]);
      }
      list[move_index] = move(temp);
    }

    gap = static_cast<int>(pow(2, --exponent) - 1);
  }
}

template<typename T>
void ShellSortKnuth(vector<T> &list) {
  int gap = 1;
  while (gap < list.size() / 3) gap = (3 * gap) + 1;

  while (gap >= 1) {
    for (int index = gap; index < list.size(); index++) {
      T temp = move(list[index]);

      int move_index = index;

      for (;
          move_index >= gap && temp < list[move_index - gap];
          move_index -= gap) {
        list[move_index] = move(list[move_index - gap]);
      }
      list[move_index] = move(temp);
    }

    gap = gap / 3;
  }
}

// Ciura (1, 4, 10, 23, 57, 132, 301, 701)
template<typename T>
void ShellSortCiura(vector<T> &list) {
  const int gap_sequence[] = { 1, 4, 10, 23, 57, 132, 301, 701 };

  // Iterate downwards through each of the potential gap sequences.
  for (int gap_index = sizeof(gap_sequence) / sizeof(gap_sequence[0]) - 1; gap_index >= 0; --gap_index) {
    int gap = gap_sequence[gap_index];

    // Do the movement, if the gap == 1, performs an ordinary insertion sort.
    for (int index = gap; index < list.size(); index++) {
      T temp = move(list[index]);

      int move_index = index;

      for (;
          move_index >= gap && temp < list[move_index - gap];
          move_index -= gap) {
        list[move_index] = move(list[move_index - gap]);
      }
      list[move_index] = move(temp);
    }
  }
}