Задача: Шейкер-сортировка
Исходник: Шейкер-сортировка, язык: C++ [code #25, hits: 14964]
автор: this [добавлен: 01.02.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. template<class T>
  8. void ShakerSort(T* x) {
  9. int last = n-1;
  10. int left = 1, right = n-1;
  11.  
  12. /* основной цикл до тех пор пока границы
  13. отсортированных с разных сторон отрезков
  14. не пересекутся */
  15. do {
  16. /* проход снизу вверх */
  17. for (int j = right; j > 0; j--) {
  18. if (x[j-1] > x[j]) {
  19. swap(x, j-1, j);
  20. last = j;
  21. }
  22. }
  23.  
  24. /* Корректируем нижнюю границу
  25. до которой уже все элементы получились
  26. отсортироваными */
  27. left = last + 1;
  28.  
  29. /* проход сверху вниз */
  30. for (int j = 1; j <= right; j++) {
  31. if (x[j-1] > x[j]) {
  32. swap(x, j-1, j);
  33. last = j;
  34. }
  35. }
  36.  
  37. /* Корректируем верхнюю границу
  38. после которой уже все элементы получились
  39. отсортироваными */
  40. right = last - 1;
  41. } while (left < right);
  42. }
Является окончательной оптимизацией пузырькового подхода сортировки.
Но в целом, алгоритм один из самых медленных.

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

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