Когда бы вы использовали сортировку выбором или сортировку слиянием?

Эффективность сортировки слиянием (nlogn) всегда выше, чем сортировка выбором (n^2). Когда бы вы предпочли выбор сортировке слиянием?


sorting algorithm big-o mergesort selection-sort
person instabiliity    schedule 23.04.2020    source источник
comment
Вы бы редко выбирали, есть лучшие алгоритмы сортировки общего назначения.   -  person Zabuzard    schedule 23.04.2020
comment
@Zabuza Но настоящий вопрос заключается в том, почему вы выбрали алгоритм O (n ^ 2), а не алгоритм O (n log n). И если слияние и выделение - единственные, которые у вас есть. . .   -  person Jim Mischel    schedule 24.04.2020
comment
см. также stackoverflow.com/a/19639780/56778   -  person Jim Mischel    schedule 24.04.2020
comment
Конечно, именно поэтому я разместил это только как комментарий.   -  person Zabuzard    schedule 24.04.2020

Ответы (1)


arrow_upward
5
arrow_downward

Поскольку время выполнения сортировки выбором равно (n2), а время выполнения сортировки слиянием равно O(n log n), для достаточно больших входных данных сортировка слиянием превзойдет сортировку выбором. Однако есть две области, в которых сортировка выбором может быть лучше:

  1. Сортировка выбором в массиве может быть реализована с O(1) вспомогательной памятью, тогда как (большинство) реализаций сортировки слиянием в массивах используют (n) вспомогательную память. В результате, если памяти очень мало, сортировка выбором будет лучшим выбором, чем сортировка слиянием. (Однако это был бы худший выбор, чем, скажем, пирамидальная или быстрая сортировка!)

  2. Сортировка выбором может быть быстрее, чем сортировка слиянием на небольших входных массивах, потому что это более простой алгоритм с меньшими постоянными коэффициентами, чем те, которые скрыты сортировкой слиянием. Если вы сортируете, скажем, массивы из 16 или около того элементов, то сортировка выбором может быть быстрее, чем сортировка слиянием. (Однако, вероятно, это был бы худший выбор, чем, скажем, сортировка вставками).

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

person templatetypedef    schedule 23.04.2020