Вопрос собеседования - Какой из следующих вариантов будет лучшим для сортировки массива из 1000 INTEGERS. 1. Быстрая сортировка 2.Tim Сортировка 3. Слияние Сортировка 4. Подсчет сортировки.Лучший алгоритм сортировки для 1000 целых чисел
Я выбрал быструю сортировку, но я думаю, что это неправильно. Может ли кто-нибудь сказать, какой правильный ответ и как?
Если вы ищете наиболее быстрое, что было бы, Merge Sort.
Почему бы не подсчитать сортировку? – user2946079
Поскольку сложность наихудшего случая сортировки сортировки - O (n log n) –
Сортировка сортировки использует значения ключей в качестве индексов в массиве, это не сортировка сортировки, а нижняя граница Ω (n log n) для сортировки сравнения не применяется к Это. –
для 1000 целые сложность пространства не имеет значения, что, следовательно, mergesort лучше, потому что это дает O(nlogn) в то время как быстрая сортировка дает худший случай O(n^2). Сортировка сортировки предполагает, что целые числа находятся в определенном диапазоне, что не относится к вашему вопросу. Я мог бы также ссылаться на bubble sort на то пошло из-за малого размера ввода и его простоты кодирования.
Timsort - это, как правило, лучший алгоритм. Он использует эвристику для определения того, какой алгоритм сортировки следует использовать (слияние или сортировка вставки). Сортировка только будет хорошей опцией, если разница между максимумом и минимумом мала. В некоторых случаях Quicksort может быть O (n^2).
Худший случай Timsort - это O (n log n), но в лучшем случае O (n).
Согласно записи Wikipedia для Timsort, это было бы «лучшим» в реальных данных.
Я попытался воспроизвести таблицу здесь, но моего foo не хватает.
В следующей таблице приведена временная сложность timsort с другими сортировками сравнения.
Timsort Merge Quicksort Insertion Selection Smoothsort Best case O(n) O(n log n) O(n log n) O(n) O(n^2) O(n) Average case O(n log n) O(n log n) O(n log n) O(n^2) O(n^2) O(n log n) Worst case O(n log n) O(n log n) O(n^2) O(n^2) O (n^2) O(n log n)
Where O is theta.
Я не знаю, как counting sort сравнивает.
Подсчет сортировки O (n + k), где k - размер диапазона. В этом случае O (2^32 -1 + 1000).Другое дело, что Quicksort быстрее, чем Mergesort в среднем случае. – rdllopes
Это зависит от множества контрастов, разрешено ли вам использовать дополнительное пространство? Вам нужно предоставить лучший случай, худший случай или средний случай? – DhruvPathak
Умм ... ну вопрос был именно так. – user2946079
@ user2946079 Большинство интервьюеров будут искать вас, чтобы задавать такие вопросы, которые нужно уточнить, прежде чем погрузиться в ответ. – MooseBoys