Методы сортировки

Тема в разделе "Другие", создана пользователем Milashka, 21 фев 2004.

Статус темы:
Закрыта.
  1. Milashka

    Milashka Гость

    Скажите, какие методы сортировки на С++ и VB самые быстрые?
     
  2. deeka

    deeka Гость

    А таинственное слово "СОРТИРОВКИ" наверное, означает "Упорядочивание массивов по возрастанию (убыванию)"?
    И причем тут язык?
    И в смысле САМЫЕ БЫСТРЫЕ? Все зависит от реализации, размеров входного массива, показателя производительности/загруженности системы....
    А вообще - самый быстрый АЛГОРИТМ СОРТИРОВКИ - так называемый алгоритм быстрой сортировки...
     
  3. ????

    ???? Гость

    читать дальше...
     
  4. Гость

    Известный факт, что теоретический предел времени сортировки - это O(N*log(N)) (естественно, в среднем).

    Сортировка пузырьком (bubble sort) тратит O(N*N) времени и является примером "как не надо делать".

    Быстрая сортировка (quick sort) даёт O(N*log(N)) в среднем, но на "плохих" наборах вырождается в пузырьковую. (иначе говоря, у времени работы большая дисперсия).
    Как ни странно, самый плохой набор для быстрой сортировки - это уже упорядоченный массив.
    Чтобы избежать такой неожиданной подлянки, прибегают к ухищрениям: например, предварительно перемешивают массив случайным образом (что занимает O(N)).

    Помимо быстрой сортировки, есть и другие алгоритмы с асимптотикой O(N*log(N)).
    Сортировка слиянием (merge sort) требует O(N) дополнительной памяти.
    Пирамидальная сортировка (heap sort) в два раза медленнее средней скорости быстрой сортировки, однако её дисперсия незначительна.

    В некоторых случаях, например, для реализации очереди с приоритетами, удобно использовать именно пирамидальную сортировку, так как добавление элемента в пирамиду (размещённую в массиве) и извлечение максимального значения из пирамиды занимает O(log N), в то время как добавление в линейно упорядоченный массив - O(N): приходится сдвигать целиком хвост массива от точки вставки.

    Подробнее о сортировке - смотрите Дональда Кнута "Искусство программирования".
    Алгоритмы и немного теории - есть на сайте algolist.manual.ru
    Ну и поиск по ключевым словам в гугле, естественно...
     
  5. Milashka

    Milashka Гость

    Спасибо вам за столь подробное объяснение! :)
     
Загрузка...
Похожие Темы - Методы сортировки
  1. Seriy1994
    Ответов:
    1
    Просмотров:
    1.367
  2. kuzduk
    Ответов:
    0
    Просмотров:
    344
  3. Катюша1603
    Ответов:
    5
    Просмотров:
    1.493
  4. gardlok
    Ответов:
    0
    Просмотров:
    1.366
  5. V88
    Ответов:
    3
    Просмотров:
    3.460
Статус темы:
Закрыта.

Поделиться этой страницей