Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.