Самый быстрый способ сортировки 10 номеров? (цифры 32 бит)
Я решаю проблему и очень быстро сортирую 10 чисел (int32). Мое приложение должно сортировать 10 номеров в миллионы раз как можно быстрее. Я беру выборку набора данных из миллиардов элементов и каждый раз, когда мне нужно выбрать из него 10 номеров (упростить) и отсортировать их (и сделать выводы из списка отсортированных 10 элементов).
В настоящее время я использую сортировку вставки, но я предполагаю, что смогу реализовать очень быстрый алгоритм выборочной сортировки для моей конкретной задачи из 10 чисел, которые будут бить сортировку вставки.
Кто-нибудь имеет представление о том, как подойти к этой проблеме?
Ответы
Ответ 1
(Следуя предложению HelloWorld для поиска в сортировочных сетях.)
Кажется, что 29-сравнение/swap-сеть - это самый быстрый способ сделать сортировку с 10 входами. Я использовал сеть, обнаруженную Ваксманом в 1969 году для этого примера в Javascript, который должен перевести непосредственно на C, поскольку это всего лишь список операторов if, сравнений и свопов.
function sortNet10(data) { // ten-input sorting network by Waksman, 1969
var swap;
if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
return(data);
}
alert(sortNet10([5,7,1,8,4,3,6,9,2,0]));
Ответ 2
Когда вы занимаетесь этим фиксированным размером, просмотрите Сортировочные сети. Эти алгоритмы имеют фиксированное время выполнения и не зависят от их ввода. Для вашего прецедента у вас нет таких накладных расходов, которые имеют некоторые алгоритмы сортировки.
Bitonic sort - это реализация такой сети. Это лучше всего работает с len (n) <= 32 на процессоре. На больших входах вы можете подумать о переходе на GPU.
https://en.wikipedia.org/wiki/Sorting_network
Btw, хорошая страница для сравнения алгоритмов сортировки - вот здесь (хотя отсутствует bitonic sort.
http://www.sorting-algorithms.com
Ответ 3
Используйте сортировочную сеть, которая имеет сравнения в группах по 4, поэтому вы можете сделать это в регистрах SIMD. Пара упакованных инструкций min/max реализует функцию упакованного компаратора. Извините, у меня нет времени прямо сейчас, чтобы найти страницу, которую я помню, про это, но, надеюсь, поиск в сетях сортировки SIMD или SSE превратит что-то в дело.
x86 У SSE есть сжатые и 32-разрядные минимальные и максимальные инструкции для векторов из четырех 32-битных int. AVX2 (Haswell и позже) имеют то же самое, но для 256b векторов 8 ints. Существуют также эффективные инструкции по тасованию.
Если у вас много независимых небольших родов, возможно, можно будет делать 4 или 8 сортировок параллельно с использованием векторов. Особенно если вы произвольно выбираете элементы (так что данные, которые будут отсортированы, в любом случае не будут смежными в памяти), вы можете избежать перетасовки и просто сравнить в том порядке, в котором вы нуждаетесь. 10 регистров для хранения всех данных из 4 (AVX2: 8) списков из 10 объектов по-прежнему оставляют 6 регистров для пространства царапин.
Сети сортировки изображений менее эффективны, если вам также нужно сортировать связанные данные. В этом случае наиболее эффективным способом является использование упакованного сравнения для получения маски, элементы которой были изменены, и использовать эту маску для смешивания векторов (ссылок на) связанных данных.
Ответ 4
Как насчет разворачиваемого, нераспределенного выбора сортировки?
#include <iostream>
#include <algorithm>
#include <random>
//return the index of the minimum element in array a
int min(const int * const a) {
int m = a[0];
int indx = 0;
#define TEST(i) (m > a[i]) && (m = a[i], indx = i );
//see http://stackoverflow.com/a/7074042/2140449
TEST(1);
TEST(2);
TEST(3);
TEST(4);
TEST(5);
TEST(6);
TEST(7);
TEST(8);
TEST(9);
#undef TEST
return indx;
}
void sort( int * const a ){
int work[10];
int indx;
#define GET(i) indx = min(a); work[i] = a[indx]; a[indx] = 2147483647;
//get the minimum, copy it to work and set it at max_int in a
GET(0);
GET(1);
GET(2);
GET(3);
GET(4);
GET(5);
GET(6);
GET(7);
GET(8);
GET(9);
#undef GET
#define COPY(i) a[i] = work[i];
//copy back to a
COPY(0);
COPY(1);
COPY(2);
COPY(3);
COPY(4);
COPY(5);
COPY(6);
COPY(7);
COPY(8);
COPY(9);
#undef COPY
}
int main() {
//generating and printing a random array
int a[10] = { 1,2,3,4,5,6,7,8,9,10 };
std::random_device rd;
std::mt19937 g(rd());
std::shuffle( a, a+10, g);
for (int i = 0; i < 10; i++) {
std::cout << a[i] << ' ';
}
std::cout << std::endl;
//sorting and printing again
sort(a);
for (int i = 0; i < 10; i++) {
std::cout << a[i] << ' ';
}
return 0;
}
http://coliru.stacked-crooked.com/a/71e18bc4f7fa18c6
Единственными соответствующими строками являются первые два #define.
Он использует два списка и полностью перепроверяет первый из них в течение десяти раз, что будет плохо реализованным выбором сортировки, однако он избегает ветвей и циклов переменной длины, которые могут компенсироваться современными процессорами и таким небольшим набором данных.
Benchmark
Я сравнивал сеть сортировки, и мой код кажется медленнее. Однако я попытался удалить разворачивание и копию. Запуск этого кода:
#include <iostream>
#include <algorithm>
#include <random>
#include <chrono>
int min(const int * const a, int i) {
int m = a[i];
int indx = i++;
for ( ; i<10; i++)
//see http://stackoverflow.com/a/7074042/2140449
(m > a[i]) && (m = a[i], indx = i );
return indx;
}
void sort( int * const a ){
for (int i = 0; i<9; i++)
std::swap(a[i], a[min(a,i)]); //search only forward
}
void sortNet10(int * const data) { // ten-input sorting network by Waksman, 1969
int swap;
if (data[0] > data[5]) { swap = data[0]; data[0] = data[5]; data[5] = swap; }
if (data[1] > data[6]) { swap = data[1]; data[1] = data[6]; data[6] = swap; }
if (data[2] > data[7]) { swap = data[2]; data[2] = data[7]; data[7] = swap; }
if (data[3] > data[8]) { swap = data[3]; data[3] = data[8]; data[8] = swap; }
if (data[4] > data[9]) { swap = data[4]; data[4] = data[9]; data[9] = swap; }
if (data[0] > data[3]) { swap = data[0]; data[0] = data[3]; data[3] = swap; }
if (data[5] > data[8]) { swap = data[5]; data[5] = data[8]; data[8] = swap; }
if (data[1] > data[4]) { swap = data[1]; data[1] = data[4]; data[4] = swap; }
if (data[6] > data[9]) { swap = data[6]; data[6] = data[9]; data[9] = swap; }
if (data[0] > data[2]) { swap = data[0]; data[0] = data[2]; data[2] = swap; }
if (data[3] > data[6]) { swap = data[3]; data[3] = data[6]; data[6] = swap; }
if (data[7] > data[9]) { swap = data[7]; data[7] = data[9]; data[9] = swap; }
if (data[0] > data[1]) { swap = data[0]; data[0] = data[1]; data[1] = swap; }
if (data[2] > data[4]) { swap = data[2]; data[2] = data[4]; data[4] = swap; }
if (data[5] > data[7]) { swap = data[5]; data[5] = data[7]; data[7] = swap; }
if (data[8] > data[9]) { swap = data[8]; data[8] = data[9]; data[9] = swap; }
if (data[1] > data[2]) { swap = data[1]; data[1] = data[2]; data[2] = swap; }
if (data[3] > data[5]) { swap = data[3]; data[3] = data[5]; data[5] = swap; }
if (data[4] > data[6]) { swap = data[4]; data[4] = data[6]; data[6] = swap; }
if (data[7] > data[8]) { swap = data[7]; data[7] = data[8]; data[8] = swap; }
if (data[1] > data[3]) { swap = data[1]; data[1] = data[3]; data[3] = swap; }
if (data[4] > data[7]) { swap = data[4]; data[4] = data[7]; data[7] = swap; }
if (data[2] > data[5]) { swap = data[2]; data[2] = data[5]; data[5] = swap; }
if (data[6] > data[8]) { swap = data[6]; data[6] = data[8]; data[8] = swap; }
if (data[2] > data[3]) { swap = data[2]; data[2] = data[3]; data[3] = swap; }
if (data[4] > data[5]) { swap = data[4]; data[4] = data[5]; data[5] = swap; }
if (data[6] > data[7]) { swap = data[6]; data[6] = data[7]; data[7] = swap; }
if (data[3] > data[4]) { swap = data[3]; data[3] = data[4]; data[4] = swap; }
if (data[5] > data[6]) { swap = data[5]; data[5] = data[6]; data[6] = swap; }
}
std::chrono::duration<double> benchmark( void(*func)(int * const), const int seed ) {
std::mt19937 g(seed);
int a[10] = {10,11,12,13,14,15,16,17,18,19};
std::chrono::high_resolution_clock::time_point t1, t2;
t1 = std::chrono::high_resolution_clock::now();
for (long i = 0; i < 1e7; i++) {
std::shuffle( a, a+10, g);
func(a);
}
t2 = std::chrono::high_resolution_clock::now();
return std::chrono::duration_cast<std::chrono::duration<double>>(t2 - t1);
}
int main() {
std::random_device rd;
for (int i = 0; i < 10; i++) {
const int seed = rd();
std::cout << "seed = " << seed << std::endl;
std::cout << "sortNet10: " << benchmark(sortNet10, seed).count() << std::endl;
std::cout << "sort: " << benchmark(sort, seed).count() << std::endl;
}
return 0;
}
Я последовательно получаю лучший результат для сортировки выбора без учета ветвей по сравнению с сортировочной сетью.
$ gcc -v
gcc version 5.2.0 (GCC)
$ g++ -std=c++11 -Ofast sort.cpp && ./a.out
seed = -1727396418
sortNet10: 2.24137
sort: 2.21828
seed = 2003959850
sortNet10: 2.23914
sort: 2.21641
seed = 1994540383
sortNet10: 2.23782
sort: 2.21778
seed = 1258259982
sortNet10: 2.25199
sort: 2.21801
seed = 1821086932
sortNet10: 2.25535
sort: 2.2173
seed = 412262735
sortNet10: 2.24489
sort: 2.21776
seed = 1059795817
sortNet10: 2.29226
sort: 2.21777
seed = -188551272
sortNet10: 2.23803
sort: 2.22996
seed = 1043757247
sortNet10: 2.2503
sort: 2.23604
seed = -268332483
sortNet10: 2.24455
sort: 2.24304
Ответ 5
Вопрос не говорит, что это какое-то веб-приложение. Единственное, что привлекло мое внимание, было:
Я беру выборку набора данных из миллиардов элементов и каждый раз, когда мне нужно выбрать из него 10 номеров (упростить) и отсортировать их (и сделать выводы из списка отсортированных 10 элементов).
Как разработчик программного обеспечения и аппаратного обеспечения, это абсолютно кричит "FPGA" для меня. Я не знаю, какие выводы вам нужно извлечь из отсортированного набора чисел или откуда берутся данные, но я знаю, что было бы почти тривиально обрабатывать где-то между сто миллионов и миллиардом из этих операций сортировки и анализа в секунду. В прошлом я выполнял секвенирование ДНК с помощью FPGA. Почти невозможно превзойти мощную вычислительную мощность ПЛИС, когда проблема хорошо подходит для такого типа решения.
На каком-то уровне единственным ограничивающим фактором становится то, как быстро вы можете перекопать данные в FPGA и как быстро вы сможете его получить.
В качестве отправной точки я разработал высокопроизводительный графический процессор реального времени, который получил 32-битные данные изображения RGB со скоростью около 300 миллионов пикселей в секунду. Данные передаются через КИХ-фильтры, матричные умножители, таблицы поиска, блоки обнаружения пространственного края и ряд других операций перед выходом на другой конец. Все это на относительно небольшой FPGA Xilinx Virtex2 с внутренним тактовым импульсом от 33 МГц до, если я правильно помню, 400 МГц. О, да, он также имел реализацию контроллера DDR2 и запускал два банка памяти DDR2.
FPGA может выводить своего рода десять 32-разрядных чисел на каждый такт при работе на сотнях МГц. В начале операции будет небольшая задержка, так как данные заполняют конвейер обработки /s. После этого вы сможете получить один результат за такт. Или больше, если обработка может быть распараллелена путем репликации конвейера сортировки и анализа. Решение, в принципе, почти тривиально.
Дело в том, что если приложение не привязано к ПК, а поток данных и обработка "совместимы" с решением FPGA (автономным или в качестве сопроцессорной карты в аппарате), нет способа вы сможете превзойти достижимый уровень производительности с помощью программного обеспечения, написанного на любом языке, независимо от алгоритма.
EDIT:
Просто запустил быстрый поиск и нашел бумагу, которая может вам пригодиться. Похоже, что это относится к 2012 году. Сегодня вы можете сделать LOT лучше в производительности (и даже тогда). Вот он:
Сортировка сетей на FPGA
Ответ 6
Недавно я написал маленький класс, который использует алгоритм Бозе-Нельсона для создания сортировочной сети во время компиляции.
Его можно использовать для создания очень быстрого сортировки для 10 чисел.
/**
* A Functor class to create a sort for fixed sized arrays/containers with a
* compile time generated Bose-Nelson sorting network.
* \tparam NumElements The number of elements in the array or container to sort.
* \tparam T The element type.
* \tparam Compare A comparator functor class that returns true if lhs < rhs.
*/
template <unsigned NumElements, class Compare = void> class StaticSort
{
template <class A, class C> struct Swap
{
template <class T> inline void s(T &v0, T &v1)
{
T t = Compare()(v0, v1) ? v0 : v1; // Min
v1 = Compare()(v0, v1) ? v1 : v0; // Max
v0 = t;
}
inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
};
template <class A> struct Swap <A, void>
{
template <class T> inline void s(T &v0, T &v1)
{
// Explicitly code out the Min and Max to nudge the compiler
// to generate branchless code.
T t = v0 < v1 ? v0 : v1; // Min
v1 = v0 < v1 ? v1 : v0; // Max
v0 = t;
}
inline Swap(A &a, const int &i0, const int &i1) { s(a[i0], a[i1]); }
};
template <class A, class C, int I, int J, int X, int Y> struct PB
{
inline PB(A &a)
{
enum { L = X >> 1, M = (X & 1 ? Y : Y + 1) >> 1, IAddL = I + L, XSubL = X - L };
PB<A, C, I, J, L, M> p0(a);
PB<A, C, IAddL, J + M, XSubL, Y - M> p1(a);
PB<A, C, IAddL, J, XSubL, M> p2(a);
}
};
template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 1>
{
inline PB(A &a) { Swap<A, C> s(a, I - 1, J - 1); }
};
template <class A, class C, int I, int J> struct PB <A, C, I, J, 1, 2>
{
inline PB(A &a) { Swap<A, C> s0(a, I - 1, J); Swap<A, C> s1(a, I - 1, J - 1); }
};
template <class A, class C, int I, int J> struct PB <A, C, I, J, 2, 1>
{
inline PB(A &a) { Swap<A, C> s0(a, I - 1, J - 1); Swap<A, C> s1(a, I, J - 1); }
};
template <class A, class C, int I, int M, bool Stop = false> struct PS
{
inline PS(A &a)
{
enum { L = M >> 1, IAddL = I + L, MSubL = M - L};
PS<A, C, I, L, (L <= 1)> ps0(a);
PS<A, C, IAddL, MSubL, (MSubL <= 1)> ps1(a);
PB<A, C, I, IAddL, L, MSubL> pb(a);
}
};
template <class A, class C, int I, int M> struct PS <A, C, I, M, true>
{
inline PS(A &a) {}
};
public:
/**
* Sorts the array/container arr.
* \param arr The array/container to be sorted.
*/
template <class Container> inline void operator() (Container &arr) const
{
PS<Container, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
};
/**
* Sorts the array arr.
* \param arr The array to be sorted.
*/
template <class T> inline void operator() (T *arr) const
{
PS<T*, Compare, 1, NumElements, (NumElements <= 1)> ps(arr);
};
};
#include <iostream>
#include <vector>
int main(int argc, const char * argv[])
{
enum { NumValues = 10 };
// Arrays
{
int rands[NumValues];
for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
std::cout << "Before Sort: \t";
for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
std::cout << "\n";
StaticSort<NumValues> staticSort;
staticSort(rands);
std::cout << "After Sort: \t";
for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
std::cout << "\n";
}
std::cout << "\n";
// STL Vector
{
std::vector<int> rands(NumValues);
for (int i = 0; i < NumValues; ++i) rands[i] = rand() % 100;
std::cout << "Before Sort: \t";
for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
std::cout << "\n";
StaticSort<NumValues> staticSort;
staticSort(rands);
std::cout << "After Sort: \t";
for (int i = 0; i < NumValues; ++i) std::cout << rands[i] << " ";
std::cout << "\n";
}
return 0;
}
Обратите внимание, что вместо оператора if (compare) swap мы явно кодируем тройные операторы для min и max. Это поможет подтолкнуть компилятор к использованию нераспределенного кода.
Бенчмарки
Следующие тесты собираются с помощью clang -O3 и запускаются в моем macbook в середине 2012 года.
Сортировка случайных данных
Сравнивая его с кодом DarioP, вот количество миллисекунд, принятых для сортировки 1 миллиона 32-битных внутренних массивов размером 10:
Hardcoded Sort Net 10: 88,774 ms
Templated Bose-Nelson sort 10: 27.815 мс
Используя этот шаблонный подход, мы можем также генерировать сортировочные сети во время компиляции для другого количества элементов.
Время (в миллисекундах) для сортировки 1 миллиона массивов различных размеров.
Количество миллисекунд для массивов размером 2, 4, 8 равно 1.943, 8.655, 20.246 соответственно.
![C++ Templated Bose-Nelson Static Sort timings]()
Кредиты Glenn Teitelbaum для разворачиваемого сортировки вставки.
Здесь приведены средние часы в сортировке для небольших массивов из 6 элементов. Базовый код и примеры можно найти по этому вопросу:
Самый быстрый тип фиксированной длины 6 int array
Direct call to qsort library function : 326.81
Naive implementation (insertion sort) : 132.98
Insertion Sort (Daniel Stutzbach) : 104.04
Insertion Sort Unrolled : 99.64
Insertion Sort Unrolled (Glenn Teitelbaum) : 81.55
Rank Order : 44.01
Rank Order with registers : 42.40
Sorting Networks (Daniel Stutzbach) : 88.06
Sorting Networks (Paul R) : 31.64
Sorting Networks 12 with Fast Swap : 29.68
Sorting Networks 12 reordered Swap : 28.61
Reordered Sorting Network w/ fast swap : 24.63
Templated Sorting Network (this class) : 25.37
Он работает так же быстро, как самый быстрый пример в вопросе для 6 элементов.
Производительность для сортировки отсортированных данных
Часто входные массивы могут быть уже отсортированы или в основном отсортированы.
В таких случаях сортировка вставки может быть лучшим выбором.
![введите описание изображения здесь]()
Вы можете выбрать соответствующий алгоритм сортировки в зависимости от данных.
Код, используемый для эталонных тестов, можно найти здесь.
Ответ 7
Несмотря на то, что у сети есть хорошие шансы быть быстрыми на небольших массивах, иногда вы не можете победить сортировку вставки, если ее правильно оптимизировать. Например, пакетная вставка с двумя элементами:
{
final int a=in[0]<in[1]?in[0]:in[1];
final int b=in[0]<in[1]?in[1]:in[0];
in[0]=a;
in[1]=b;
}
for(int x=2;x<10;x+=2)
{
final int a=in[x]<in[x+1]?in[x]:in[x+1];
final int b=in[x]<in[x+1]?in[x+1]:in[x];
int y= x-1;
while(y>=0&&in[y]>b)
{
in[y+2]= in[y];
--y;
}
in[y+2]=b;
while(y>=0&&in[y]>a)
{
in[y+1]= in[y];
--y;
}
in[y+1]=a;
}
Ответ 8
Вы можете полностью развернуть insertion sort
Чтобы сделать это проще, рекурсивный template можно использовать без каких-либо служебных накладных расходов. Поскольку он уже является template, int может быть параметром template. Это также делает размеры массива кодирования отличными от 10 тривиальных.
Обратите внимание, что для сортировки int x[10] вызов insert_sort<int, 9>::sort(x);, поскольку класс использует индекс последнего элемента. Это может быть завернуто, но это будет больше кода для чтения.
template <class T, int NUM>
class insert_sort;
template <class T>
class insert_sort<T,0>
// stop template recursion
// sorting 1 item is a no-op
{
public:
static void place(T *x) {}
static void sort(T * x) {}
};
template <class T, int NUM>
class insert_sort
// use template recursion to do insertion sort
// NUM is the index of the last item, eg. for x[10] call <9>
{
public:
static void place(T *x)
{
T t1=x[NUM-1];
T t2=x[NUM];
if (t1 > t2)
{
x[NUM-1]=t2;
x[NUM]=t1;
insert_sort<T,NUM-1>::place(x);
}
}
static void sort(T * x)
{
insert_sort<T,NUM-1>::sort(x); // sort everything before
place(x); // put this item in
}
};
В моем тестировании это было быстрее, чем примеры сортировки.
Ответ 9
Для сортировки вставки требуется в среднем 29,6 сравнений для сортировки 10 входов с лучшим случаем 9 и худшим из 45 (с учетом ввода, который находится в обратном порядке).
A {9,6,1} shellsort потребует в среднем 25,5 сравнений с сортировкой 10 входов. Наилучший случай - 14 сравнений, худшее - 34, а для сортировки обратного ввода требуется 22.
Поскольку вы, похоже, знакомы с сортировкой вставки, вы можете реализовать алгоритм как сортировочную сеть для {9,6}, а затем придерживаться сортировки вставки ({1}) после этого:
i[0] with i[9] // {9}
i[0] with i[6] // {6}
i[1] with i[7] // {6}
i[2] with i[8] // {6}
i[3] with i[9] // {6}
i[0 ... 9] // insertion sort
Ответ 10
По причинам, сходным с тем, что я описал здесь здесь, следующие функции сортировки sort6_iterator() и sort10_iterator_local() должны хорошо выполняться, когда была выбрана сортировочная сеть от здесь:
template<class IterType>
inline void sort10_iterator(IterType it)
{
#define SORT2(x,y) {if(data##x>data##y)std::swap(data##x,data##y);}
#define DD1(a) auto data##a=*(data+a);
#define DD2(a,b) auto data##a=*(data+a), data##b=*(data+b);
#define CB1(a) *(data+a)=data##a;
#define CB2(a,b) *(data+a)=data##a;*(data+b)=data##b;
DD2(1,4) SORT2(1,4) DD2(7,8) SORT2(7,8) DD2(2,3) SORT2(2,3) DD2(5,6) SORT2(5,6) DD2(0,9) SORT2(0,9)
SORT2(2,5) SORT2(0,7) SORT2(8,9) SORT2(3,6)
SORT2(4,9) SORT2(0,1)
SORT2(0,2) CB1(0) SORT2(6,9) CB1(9) SORT2(3,5) SORT2(4,7) SORT2(1,8)
SORT2(3,4) SORT2(5,8) SORT2(6,7) SORT2(1,2)
SORT2(7,8) CB1(8) SORT2(1,3) CB1(1) SORT2(2,5) SORT2(4,6)
SORT2(2,3) CB1(2) SORT2(6,7) CB1(7) SORT2(4,5)
SORT2(3,4) CB2(3,4) SORT2(5,6) CB2(5,6)
#undef CB1
#undef CB2
#undef DD1
#undef DD2
#undef SORT2
}
Чтобы вызвать эту функцию, я передал ей итератор std::vector.
