Является ли выбор сортировки эффективным алгоритмом?

Question

Я знаю, что это алгоритм квадратичного времени, но как он сравнивается с другими алгоритмами сортировки, такими как QuickSort или Bubble Sort?

Answer 1

Алгоритмы сортировки обычно различаются в зависимости от характера имеющихся у вас данных.

Однако, хотя пузырьковая сортировка и сортировка выделения просты для понимания (и реализации) алгоритмов сортировки, их время выполнения равно O (n ^ 2), т.е. худшее время, которое вы можете получить.

Что касается быстрой сортировки в среднем, это занимает O (n log n) времени, следовательно, это отличная сортировка. Тем не менее, в некоторых случаях это также может занять O (n ^ 2).

Answer 2

Алгоритмы квадратичного времени, в зависимости от размера вашего набора данных, могут быть невероятно медленными.

n = 10e78 (о количестве атомов во вселенной)

Для квадратичного алгоритма это n * (10e78). Для алгоритма nlog (n), такого как быстрая сортировка или слияние, это n * 262. Это огромная разница.

Но если ваш набор данных относительно мал (скажем, <1000 элементов), то разница в производительности, вероятно, не будет заметна (если, возможно, сортировка не выполняется повторно). В этих случаях обычно лучше всего использовать простейший алгоритм и оптимизировать его позже, если он окажется слишком медленным. </p>

«Преждевременная оптимизация - корень всего зла». -Сэр Тони Хоар, популяризированный Дональдом Кнутом

Answer 3

Если ваши данные состоят только из натуральных чисел, вы можете посмотреть сортировку по группам. Алгоритм может иметь линейное время O (n) в правильных условиях.

Answer 4

Википедия знает все.

Сортировка выбора в значительной степени отстой.