Задача: сортировка пузырьком
Исходник: Сортировка пузырьком с признаком отсортированности массива. Версия #2, язык: C++ [code #27, hits: 8387]
автор: this [добавлен: 02.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 BubbleSort2(T* x) {
  9. for (int i = 0; i < n; i++) {
  10. bool sorted = true;
  11. for (int j = n-1; j > i; j-- ) {
  12. if (x[j-1] > x[j]) {
  13. swap(x, j-1, j);
  14. sorted = false;
  15. }
  16. }
  17. if (sorted) break;
  18. }
  19. }
Модификация базового метода. Если массив после какого-то шага уже получился отсортированным - то процедура завершается, предотвращая холостые проходы.

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

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