Задача: Сортировка Шелла, оптимальный выбор приращений
Исходник: Модификация базовой сортировки Шелла с приращениями для больших N, язык: C++ [code #23, hits: 7354]
автор: this [добавлен: 31.01.2006]
  1. template<class T>
  2. void swap(T* x, int i, int j) {
  3. T tmp;
  4. tmp = x[i]; x[i] = x[j]; x[j] = tmp;
  5. }
  6.  
  7. /* Рассчитывает последовательность
  8. приращений рекомендуюмую при больших
  9. размерах сортируемой последовательности */
  10. int DForBig2(int d[], long n) {
  11. int i = 0;
  12. d[i] = 1;
  13.  
  14. do {
  15. i++;
  16. d[i] = 3*d[i-1] + 1;
  17. } while (d[i] < n);
  18.  
  19. return (i < 2) ? 0 : i-2;
  20. }
  21.  
  22. /* Сортировка Шелла */
  23. template<class T>
  24. void BaseShellSortDForBigN(T* x) {
  25. /* максимальное количество рассчитываемых
  26. приращений = 20 */
  27. int d, i, j, dseq[20];
  28. int di;
  29.  
  30. /* Рассчитываем последовательность
  31. приращений */
  32. di = DForBigN(dseq, n);
  33. while (di > 0) {
  34. /* Приращение на данной итерации */
  35. d = dseq[di--];
  36. int i = 0, j = 0;
  37.  
  38. /* Делает проход пузырька для групп
  39. пока расстояние между сортируемыми
  40. элементами не станет = 1 */
  41. while (j = i + d < n) {
  42. if (x[i] > x[j]) {
  43. swap(x, i, j);
  44. }
  45. i++;
  46. }
  47. }
  48. /* Заключительная элементарная сортировка
  49. полученной последовательности из 2-х
  50. отсортированных групп */
  51. InsertSort(x);
  52. }
Модификация базового алгоритма сортировки Шелла.
Значения приращений рассчитываются методом, рекомендуемым при больших размерностях сортируемой последовательности.

Производительность: точно не определена, но значительно быстрее чем ~ O(n2)
Расход памяти: ~ O(n), тратится на хранение последовательности рассчитанных значений приращений конечно.
Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

+добавить реализацию