Самый быстрый вид сортировки массива

[rpy3uH]

Сообщение от Altera

Если бы это был такой хороший метод, то, наверное, не разрабатывали-бы алгоритм быстрой сортировки:

алгоритм быстрй сортировки несомненно хорош. повторяю. я не говорю что приведённый мной алгоритм самый лучший, я говорю что он лучший из простых алгоритмов, а алгоритм быстрой сортировки в простым алгоритмам не относится, так же как и алгоритм шелла. И тем более алгоритм быстрой сортировки не всегда подходит, и к тому же всегда есть вероятность переполнения, так как есть рекурсия.

[Altera]

Алгоритм быстрой сортировки не всегда работает так, как надо. К тому-же он относиться к не устойчивый, что в моём случае смотрится не очень красиво....

[Warnes]

Ого. Неделю тут не был,а тут уже из-за моего вопросса дискуссия кипит=)

[LeBron]

Сообщение от Altera

Алгоритм быстрой сортировки не всегда работает так, как надо. К тому-же он относиться к не устойчивый, что в моём случае смотрится не очень красиво....

Неустойчивость - это да, а вот сортирует правильно всегда (что легко доказать математически).
Я бы советовал в таких случаях или хэш+быстрая по хэшу, или просто быструю юзать.

[Levsha100]

Че вы паритесь, сортируйте пузырьком! (с)

[bullvinkle]

Я всегда использую біструю сортировку.
http://www.sorting-algorithms.com/ ресурс интересній и полезній для єтой темі.

[Ozerich]

Есть еще сортировка подсчетом.Время работы равняется максимальному числу в массиве.
Принцип работы:

создается массив на n элементов где n максимальное число в массиве
Пробегаем по массиву и инкрементируем ms[i] где i текущее элемент массива.Потом просто идем по нашему массиву ms и ms[i] раз выводим число i.

Время работы сортировки пузырьком и вставками равняется n*n где n кол-во элементов.Компьютер в среднем за секунду выполняет 10^8 операций.

Время работы быстрой сортировки N * log(N) где N кол-во элементов в массиве.НО эта сложность рассчитана в среднем.Худший случай,когда например массив 1 2 3 4 5 ... и так далее сортировка будет работать за n*n но доказано что алгоритм в большинстве случаев эффективней чем N * Log N.

Есть еще сортировка на куче,черпачная сортировка(очень тяжелая в реализации но работает за n)

[Arigato]

Ozerich
Уже было в этой теме.

[LeBron]

Сообщение от Ozerich

Есть еще сортировка подсчетом.Время работы равняется максимальному числу в массиве.
Принцип работы:

создается массив на n элементов где n максимальное число в массиве
Пробегаем по массиву и инкрементируем ms[i] где i текущее элемент массива.Потом просто идем по нашему массиву ms и ms[i] раз выводим число i.

Время работы сортировки пузырьком и вставками равняется n*n где n кол-во элементов.Компьютер в среднем за секунду выполняет 10^8 операций.

Время работы быстрой сортировки N * log(N) где N кол-во элементов в массиве.НО эта сложность рассчитана в среднем.Худший случай,когда например массив 1 2 3 4 5 ... и так далее сортировка будет работать за n*n но доказано что алгоритм в большинстве случаев эффективней чем N * Log N.

Есть еще сортировка на куче,черпачная сортировка(очень тяжелая в реализации но работает за n)

Исправления: время работы O(N+M), фактически, чуть иначе, но само считывание и заполнение массива заберет именно столько, а вывод в отсортированный массив - еще О(N) (edit - протупил, тоже O(N+M)). Небольшой минус - памяти много надо. При этом M - это не максимум массива, а количество различных возможных значений в массиве. Быстрая сортировка при рандомизированной реализации хоть и может работать за О(n*n), но вероятность не очень большая. Да и при нерандомизированной главное, что бы не был набор информации специально для завала. Вероятность случая расписывается через логарифмы, и получается, что самый худший случай возможный только в 1 наборе, то есть для 1000 чисел самый худший случай возможен лиш с веротностью в 0.000.. (примерно 300 нолей )..01. Ну и вообще с отклонением в сторону квадрата не все так страшно. Вообще-то доказано, что отсортировать массив быстрее, чем N * log(N) без дополнительной информации невозможно. Есть некоторые более быстрые сортировки с большой константой (та же сортировка Хана), которые просто получают эту информацию перед сортировкой довольно быстро, и потом довольно быстро сортируют с помощью этой информации. Но на практике такое использовать не выгодно. Там маленькая сложность перекрывает большую константу при очень больших наборах данных.

[Arigato]

Всё же сортировка подсчётом (или линейная сортировка) самая быстрая.
Простой пример. Дан массив, состоящий из 1 000 000 элементов. Заполняем случайными числами от 0 до 999.
Отсортируйте его пузырьком или даже быстрой сортировкой, замерьте время работы алгоритма.
Теперь отсортируйте его линейной сортировкой и тоже замерьте время.
Сделайте выводы