Я понимаю, что большие значения O для сортировки пузырьком и сортировки выбором одинаковы, (n) ^ 2, но когда я пытаюсь запустить оба с массивом размером 1000, сортировка пузырьком требует 962037 свопов для сортировки массива, в то время как выборка Сортировка занимает всего 988 свопов для сортировки массива. Почему они разные?
Эффективность пузырьковой сортировки по сравнению с сортировкой выбором
Ответы (2)
Потому что сложность относится к количеству сравнений, а не к количеству свопов. Оба требуют O (n ^ 2) сравнений, но для сортировки выбором требуется только n-1 обменов в худшем случае (O (n)), тогда как для пузырьковой сортировки может потребоваться до n*(n-1)/2 обменов (O (n ^ 2)).
И даже если сложность будет относиться к количеству свопов - поскольку нотация игнорирует константы (одна на самом деле может быть 1000*n^2 + 500*n*log(n) + 100*n + 10, а другая может быть n^2), оба числа все равно могут отличаться на произвольно большое значение.
person
MikeMB
schedule
16.02.2016
А? Оба этих алгоритма работают за O(n^2), независимо от того, считаете ли вы свопы, сравнения или операции в целом.
- person Louis Wasserman; 16.02.2016
@Louis Wasserman: сортировка выбором требует (в худшем случае) одного обмена для каждого числа, которое не находится в правильной позиции (O (n)). Для пузырьковой сортировки это зависит от фактической позиции, но для обратного списка вам нужно n * (n + 1)/2 свопа (O (n ^ 2))
- person MikeMB; 16.02.2016
Нотация Big O обеспечивает бессимптомную стоимость, однако все аддитивные значения и константы опущены. Кроме того, для реалистичного сравнения при небольших числах нужно смотреть на среднее количество сравнений. В частности, для пузырьковой сортировки требуется в среднем n/4 замены на запись, а для сортировки выбором требуется только 1, см. это post для получения дополнительной информации. Количество сравнений также будет зависеть от начального распределения, например, от того, являются ли данные частично отсортированными или полностью случайными.
person
Alex
schedule
16.02.2016
