Быстрая сортировка по сравнению с сортировкой слиянием [дубликат]
Может быть еще 1 подход.
awk -v val="6" 'substr($1,1,1)>val || substr($1,2,1)>val' Input_file
Там, где я специально проверяю, является ли 1-й символ 1-го поля или 2-м символом 1-го поля больше 6, где я создал переменную с именем val, значение которой я установил в 6, ее можно изменить как по необходимости.
О подходе OP: Да, можно установить FS="", но это будет более конкретно для GNU awk ИМХО Я так не думаю, все awk с поддержите его, поэтому он может потерпеть неудачу, если FS="" НЕ поддерживается. Поэтому для этой задачи лучше использовать substr или регулярное выражение (чтобы сделать решение глобальным поддерживающим).
7 ответов
Как правило, quicksort значительно быстрее на практике, чем другой Θ (nlogn) алгоритмы, потому что его внутренний цикл может быть эффективно реализован на большей части архитектуры, и в большинстве реальных данных, возможно сделать проектные решения, которые минимизируют вероятность требования квадратичного времени.
Обратите внимание, что очень низкое требование к памяти является большим плюс также.
Для Сортировки слиянием худший случай O(n*log(n)), для Быстрой сортировки: O(n2). Для других случаев (в среднем, лучше всего) оба имеют O(n*log(n)). Однако Быстрая сортировка является пространством, постоянным, где Сортировка слиянием зависит от структуры, Вы сортируете.
Посмотрите это сравнение.
Можно также видеть его визуально.
В то время как quicksort часто является лучшим выбором, чем сортировка слиянием, существуют определенно времена, когда сортировка слиянием является thereotically лучшим выбором. Самое очевидное время - когда чрезвычайно важно что Ваш алгоритм, выполненный быстрее, чем O (n^2). Quicksort обычно быстрее, чем это, но, учитывая теоретический худший вход, он мог работать в O (n^2), который хуже, чем худшая сортировка слиянием.
Quicksort также более сложен, чем сортировка с объединением, особенно если Вы хотите записать действительно серьезную реализацию, и поэтому при стремлении к простоте и пригодности для обслуживания сортировка слиянием становится многообещающей альтернативой с очень небольшим количеством потери производительности.
В дополнение к остальным: Сортировка слиянием очень эффективна для неизменяемых структур данных, таких как связанные списки, и поэтому является хорошим выбором для (чисто) языков функционального программирования.
Плохо реализованная быстрая сортировка может представлять угрозу безопасности .
Я лично хотел проверить разницу между Quick sort и merge sort и посмотрел время работы для выборки из 1,000,000 элементов.
Quick sort смогла сделать это за 156 миллисекунд, тогда как Merge sort сделала то же самое за 247 миллисекунд
Данные Quick sort были, однако, случайными, и Quick sort работает хорошо, если данные случайны, в то время как в случае с merge sort это не так, т.е. merge sort работает независимо от того, отсортированы данные или нет. Но сортировка слиянием требует одного полного дополнительного места, а быстрая сортировка не требует, так как это сортировка на месте
Я написал исчерпывающую рабочую программу для них и иллюстративные картинки тоже.
Быстрая сортировка обычно быстрее, чем сортировка слиянием, когда данные хранятся в памяти. Однако, когда набор данных огромен и хранится на внешних устройствах, таких как жесткий диск, сортировка слиянием является явным победителем с точки зрения скорости. Это минимизирует дорогостоящие операции чтения с внешнего диска, а также хорошо подходит для параллельных вычислений.
Быстрая сортировка. Вам нужно очень мало дополнительной памяти. Что чрезвычайно важно.
Хороший выбор медианы делает его еще более эффективным, но даже плохой выбор медианы гарантирует Theta (nlogn).