Является ли выбор подходящим алгоритмом?

Question

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

Answer 1

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

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

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

Answer 2

Wikipedia знает все.

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

Answer 3

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

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

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

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

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

Answer 4

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