1. C++ / Говнокод #11367

    +21

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    template <typename T> 
    void sort( T array[], size_t length ) {
    	size_t left_index = 0;
    	size_t right_index = length - 1;
    
    	while ( left_index < right_index ) {
    		size_t min_index = min( array, left_index, right_index );
    		swap( array, min_index, left_index );
    
    		size_t max_index = max( array, left_index, right_index );
    		swap( array, max_index, right_index );
    
    		left_index++;
    		right_index--;
    	}
    }

    Запостил: Fai, 05 Июля 2012

    Комментарии (13) RSS

    • какой банальный сорт говна
      Ответить
    • Инкремент из 13й строки надо бы перенести в 9ю, т.к. то, что лежит по индексу left_index всяко уже не сможет стать максимумом.

      А вообще строки 10, 11 и 14 можно с чистой совестью выкинуть - алгоритм от этого не пострадает.

      P.S. Может быть я не вижу каких-то других проблем?
      Ответить
      • Проблем нет. Исправно работает, только вот сложность меня немного пугает.
        И зачем нужен велосипед если есть быстрая сортировка стандартные алгоритмы.
        Ответить
        • Это лаба? Тогда простительно, ведь могли попросить реализовать именно этот метод.
          Ответить
      • Можно было бы сделать функцию minimax, чтобы находилось сразу и минимальное и максимальное значение. Вот это бы помогло. У алгоритма итак сложность довольно велика.
        Ответить
        • minmax, конечно, поможет, но не сильно. Во-первых асимптотика так и останется О(n²). Во-вторых хоть на части чисел будет сравнение только с min (если число выбрали как минимум, нет смысла сравнивать его с max), но на остальных все равно будут крутиться оба сравнения - и с min и с max, т.е. число сравнений от этого упадет, но не в 2 раза. Число перестановок останется прежним.

          Еще один плюс реализации с minmax - лучшее взаимодействие с кешем, что положительно скажется на эффективности при массивах больших чем кеш.

          Но лучше не заниматься задрачиванием этой сортировки, а применить другой алгоритм с нормальной асимптотикой ;)
          Ответить
          • Точно. Стоит например выпилить шаблон и сделать поразрядную сортировку.
            Во всей остальной части сортируются так только массивы int...

            Вот к чему людей приводит желание излишней общности и незнание того, что фабрика велосипедов находится через дорогу.
            Ответить
          • Почему асимптота? O(n^2) стабильно же.
            Ответить
            • Потому, что все эти О(...) это асимптотические оценки сложности, и они показывают, как будет вести себя алгоритм при больших N.
              Ответить
              • [sarcasm]Парабола, гипербола... чё там ещё было? Асимптота![/sarcasm]
                Ответить
                • Тег должен был быть чем-то вроде [petrosnya], но не [sarcasm]...
                  Ответить

    Добавить комментарий