Этот блог дает вам краткий обзор необходимости наиболее часто используемых методов сортировки с учетом их реальных приложений и сложностей.
Алгоритм сортировки используется для переупорядочивания заданного массива или элементов списка в соответствии с оператором сравнения элементов. Оператор сравнения используется для определения нового порядка элементов в соответствующей структуре данных.
Набор записей называется списком, в котором каждая запись имеет одно или несколько полей. Например, каталог телефонных номеров можно представить себе как список, в котором каждая запись имеет три поля - «имя» человека, «адрес» этого человека и их «номера телефонов». Уникальный номер телефона может работать как ключ к поиску любой записи в списке. Сортировка - это операция, выполняемая для упорядочивания записей таблицы или списка в соответствии с определенным критерием упорядочения. Сортировка производится по некоторому значению ключа каждой записи. Записи сортируются в цифровом или буквенно-цифровом порядке. Затем записи располагаются в порядке возрастания или убывания в зависимости от числового значения ключа.
Типы:
1. Сортировка по месту и сортировка по месту
2. Стабильная и нестабильная сортировка
3. Адаптивный и неадаптивный алгоритм сортировки.
Важность:
Расположение данных в предпочтительном порядке называется сортировкой в структуре данных. Сортировка данных упрощает поиск в них быстро и легко. Самый простой пример сортировки - словарь. До эпохи Интернета, когда вы хотели найти слово в словаре, вы делали это в алфавитном порядке. Это облегчило задачу. Представьте себе панику, если бы вам пришлось просматривать большую книгу со всеми английскими словами мира в беспорядочном порядке! Это та же паника, которую испытает инженер, если его данные не будут отсортированы и структурированы. Короче говоря, сортировка упрощает нашу жизнь.
В образовательном плане алгоритмы сортировки - отличная возможность для обучения, поскольку они демонстрируют множество различных подходов к решению проблемы, иллюстрируют различные типы вычислительной сложности, иллюстрируют различные второстепенные свойства, такие как нахождение на месте и стабильность.
Коммерческое использование:
- Коммерческие вычисления. Государственные организации, финансовые учреждения и коммерческие предприятия систематизируют большую часть этой информации путем ее сортировки. Независимо от того, должны ли информационные счета быть отсортированы по имени или номеру, транзакции будут отсортированы по времени или месту, почта будет отсортирована по почтовому индексу или адресу, файлы, которые будут отсортированы по имени или дате, или что-то еще, обработка таких данных обязательно потребует алгоритм сортировки где-то в пути.
- Поиск информации. Сохранение данных в отсортированном порядке позволяет эффективно выполнять поиск с помощью классического алгоритма двоичного поиска.
- Численные вычисления. Научные вычисления часто связаны с точностью (насколько мы близки к истинному ответу?). Точность чрезвычайно важна, когда мы выполняем миллионы вычислений с оценочными значениями, такими как представление вещественных чисел с плавающей запятой, которое мы обычно используем на компьютерах. Некоторые численные алгоритмы используют очереди приоритетов и сортировку для контроля точности вычислений.
Распространенные методы сортировки:
Быстрая сортировка: когда вам не нужна стабильная сортировка, и производительность в среднем случае имеет большее значение, чем производительность в наихудшем случае. Быстрая сортировка составляет в среднем O (N log N), в худшем случае - O (N²). В хорошей реализации для рекурсии используется вспомогательная память O (log N) в виде пространства стека.
Сортировка слиянием: когда вам нужна стабильная сортировка O (N log N), это единственный вариант. Единственным недостатком этого метода является то, что он использует дополнительное пространство O (N) и имеет немного большую константу, чем быстрая сортировка.
Introsort: это быстрая сортировка, которая переключается на сортировку по куче после определенной глубины рекурсии, чтобы обойти наихудший случай быстрой сортировки O (N²).
Пузырьковая сортировка, сортировка по выбору: когда вы делаете что-то быстрое и грязное и по какой-то причине вы не можете просто использовать алгоритм сортировки стандартной библиотеки. Единственное преимущество, которое они имеют перед сортировкой вставкой, - это немного проще реализовать.
Пузырьковая сортировка
Пузырьковая сортировка - это алгоритм сортировки, что по сути означает, что это алгоритм, используемый для взятия неупорядоченного списка и его размещения в определенном порядке. Пузырьковая сортировка работает на основе заданных списков, меняя местами соседний элемент или данные по порядку, пока все списки элементов или данных не будут получены в последовательности, основанной на их ключевых значениях. Этот метод популярен и прост для обработки данных, не требующих дополнительного места для хранения.
Пузырьковая сортировка - не самый эффективный алгоритм сортировки, но у нее есть два основных преимущества перед многими другими алгоритмами сортировки.
- Во-первых, это один из самых простых алгоритмов сортировки, особенно для новичков, поэтому он служит очень удобным инструментом обучения и простым способом сортировки относительно небольших списков.
2. Во-вторых, мы можем легко определить, когда список уже отсортирован с помощью пузырьковой сортировки, и преждевременно завершить наш код, что делает его полезным, когда нам предоставляется отсортированный список, но мы не знаем заранее, что список отсортирован.
Алгоритм:
Шаг 1. Рассмотрите набор элементов, которые могут быть любыми данными для заданных списков.
Шаг 2. Поменяйте местами первые два данных для заданных списков рядом друг с другом, используя одну за другой пару.
Шаг 3. Повторите процесс для всех элементов или данных в данном списке.
Шаг 4. Верните результат для того же самого.
Компенсация времени и места:
Временная сложность пузырьковой сортировки составляет O (n2).
Главное преимущество пузырьковой сортировки - простота алгоритма.
Сложность пространства для пузырьковой сортировки составляет O (1), потому что требуется только одно дополнительное пространство памяти, то есть для временной переменной.
Кроме того, наилучшая временная сложность случая будет O (n), когда список уже отсортирован.
Временная сложность пузырьковой сортировки:
- Наилучший сценарий. Наилучший сценарий возникает, когда массив уже отсортирован. В этом случае на первой итерации подкачки не произойдет (переменная подкачки будет ложной). Итак, когда это происходит, мы прерываем цикл после самой первой итерации. Следовательно, временная сложность в лучшем случае составляет O (n), потому что она должна пройти через все элементы один раз.
- Сценарий наихудшего и среднего случая. В пузырьковой сортировке сравнения n-1 выполняются на 1-м проходе, n-2 - на 2-м, n-3 - на 3-м и т. д. Итак, общее количество сравнений будет:
Сумма = (n-1) + (n-2) + (n-3) +… .. + 3 + 2 + 1
Сумма = n (n-1) / 2
- Следовательно, временная сложность имеет порядок n2 или O (n2).
Космическая сложность пузырьковой сортировки
Сложность пространства для алгоритма составляет O (1), потому что требуется только одно дополнительное пространство памяти, то есть для временной переменной, используемой для подкачки.
Приложение
Все мы прошли через этот процесс на протяжении всего детства. Позвольте мне вернуть вас к ностальгическим воспоминаниям о ваших уроках физкультуры или спорте в школе. Выстроились в случайном порядке перед учителем, который поставил задачу выстроить вас всех в порядке возрастания роста. Здесь пригодится алгоритм пузырьковой сортировки. В этом случае рост каждого человека является элементом списка. С каждым проходом, которым учитель проходит над учениками, они постепенно начинают стоять более упорядоченно, пока все не встанут в соответствии с ростом.
Быстрая сортировка
Как и MergeSort, QuickSort представляет собой алгоритм разделяй и властвуй. Он выбирает элемент как опорный элемент и разбивает данный массив вокруг выбранной опорной точки. Существует множество различных версий quickSort, которые выбирают точку поворота по-разному.
Алгоритм
- Всегда выбирайте первый элемент как точку опоры.
- Всегда выбирайте последний элемент в качестве опорного (реализовано ниже)
- Выберите случайный элемент в качестве точки поворота.
- Выберите медианное значение в качестве точки поворота.
Time Comp и Space Comp
- Лучший случай: лучший случай возникает, когда процесс разделения всегда выбирает средний элемент в качестве опорного. Ниже приводится повторение в лучшем случае. Т (п) = 2Т (п / 2) + (п)
- Наихудший случай : Наихудший случай возникает, когда процесс разделения всегда выбирает наибольший или наименьший элемент в качестве точки поворота. Если мы рассмотрим приведенную выше стратегию разделения, в которой последний элемент всегда выбирается в качестве точки поворота, наихудший случай будет иметь место, когда массив уже отсортирован в порядке возрастания или убывания. Ниже приводится повторение в худшем случае.
- T(n) = T(n-1) + (n)
- Средний случай: чтобы провести анализ среднего случая, нам нужно рассмотреть все возможные перестановки массива и вычислить время, затрачиваемое на каждую перестановку, что выглядит непросто.
- Мы можем получить представление о среднем случае, рассматривая случай, когда раздел помещает O (n / 9) элементов в один набор и O (9n / 10) элементов в другие наборы. Ниже приводится повторение этого случая.
Хотя наихудшая временная сложность QuickSort составляет O (n2), что больше, чем у многих других алгоритмов сортировки, таких как MergeSort и HeapSort, QuickSort на практике работает быстрее, потому что его внутренний цикл может быть эффективно реализован на большинстве архитектур, и в большинстве реальных данных. QuickSort можно реализовать по-разному, изменив выбор точки поворота, чтобы наихудший случай редко возникал для данного типа данных. Однако сортировка слиянием обычно считается лучше, когда данные огромны и хранятся во внешнем хранилище.
Приложение
Он используется в операционных исследованиях и событийном моделировании. В численных вычислениях и в научных исследованиях для точности вычислений в большинстве эффективно разработанных алгоритмов используется очередь приоритетов, а для сортировки используется быстрая сортировка.
Сортировка вставкой
Сортировка вставкой - это простой алгоритм сортировки, который работает аналогично тому, как вы сортируете игральные карты в руках. Массив виртуально разделен на отсортированную и несортированную части. Значения из неотсортированной части выбираются и помещаются в правильное положение в отсортированной части.
Сортировка вставкой - это эффективный алгоритм сортировки, так как он не работает в заданных условиях с использованием циклов for, а вместо этого использует один цикл while, что позволяет избежать дополнительных шагов после сортировки массива.
Алгоритм
Чтобы отсортировать массив размера n в порядке возрастания:
1. Перейдите от arr [1] к arr [n] по массиву.
2. Сравните текущий элемент (ключ) с его предшественником.
3. Если ключевой элемент меньше своего предшественника, сравните его с предыдущими элементами. Переместите большие элементы на одну позицию вверх, чтобы освободить место для замененного элемента.
Time Comp и Space Comp
Сложность времени наихудшего случая [Big-O]: O (n²)
Лучшая временная сложность [Big-omega]: O (n)
Средняя временная сложность [Big-theta]: O (n²)
Космическая сложность: O (1)
Приложение
Основное различие между пузырьковой сортировкой и сортировкой вставкой заключается в том, что пузырьковая сортировка выполняет сортировку, проверяя соседние элементы данных и меняя их местами, если они находятся в неправильном порядке, в то время как сортировка вставкой выполняет сортировку, передавая по одному элементу в частично отсортированный массив за раз.
Вы помните, как в детстве раскладывали руку в карты? Сначала вы выбираете одну карту, затем выбираете следующую карту и кладете ее после первой карты, если она больше, или перед первой картой, если она меньше; затем вы берете другую карту и вставляете ее на свое место.
Еще один реальный пример сортировки вставкой - это то, как портные раскладывают рубашки в шкафу, они всегда хранят их в отсортированном порядке по размеру и, таким образом, очень быстро вставляют новую рубашку в нужное место, перемещая другие рубашки вперед, чтобы сохранить нужное место для новая рубашка.
Сортировка вставкой более эффективна на практике для небольших массивов, чем асимптотически быстрые алгоритмы, такие как QuickSort и HeapSort, из-за лучшей константы. Вот почему он фактически используется в реализации функции сортировки std :: sort C ++, по крайней мере, в GCC, а std :: sort - это функция, которая, вероятно, используется более чем в 90% нетривиальных программ на C ++ - практически везде. .
Сортировка выбора
Выборочная сортировка - это простой алгоритм сортировки. Этот алгоритм сортировки представляет собой алгоритм на основе сравнения на месте, в котором список делится на две части: отсортированная часть на левом конце и несортированная часть на правом конце. Изначально отсортированная часть пуста, а несортированная часть - это весь список.
Наименьший элемент выбирается из несортированного массива и заменяется крайним левым элементом, и этот элемент становится частью отсортированного массива. Этот процесс продолжает перемещение границы несортированного массива на один элемент вправо.
Алгоритм
- Шаг 1 - Установите минимальное значение для местоположения 0
- Шаг 2 - Найдите минимальный элемент в списке
- Шаг 3 - Поменяйте местами значение в позиции MIN
- Шаг 4 - Увеличьте MIN, чтобы указать на следующий элемент
- Шаг 5 - Повторяйте, пока список не будет отсортирован
Анализ сложности времени-
- Алгоритм сортировки выбора состоит из двух вложенных циклов.
- Благодаря двум вложенным циклам он имеет временную сложность O (n2).
Приложение
- Основное преимущество сортировки по выбору заключается в том, что она хорошо работает с небольшим списком. Поскольку это алгоритм сортировки на месте, дополнительное временное хранилище не требуется, помимо того, что необходимо для хранения исходного списка. Недостатком сортировки по выбору является ее низкая эффективность при работе с огромным списком элементов.
- Сортировку выбора можно рассматривать как любой выбор, который происходит на макроуровне. То есть мы можем визуально увидеть максимальный или минимальный элемент из всех элементов несортированного списка, выбрать его и поместить в отсортированный список. Например, собирать яблоки с дерева. Мы можем увидеть все яблоки на дереве, найти и сорвать самое большое и бросить его в нашу корзину (которая, как мы можем предположить, всегда содержит отсортированные яблоки).
- Теперь рассмотрим другой пример, если у вас есть 200 стаканов разного объема: 100 мл, 110 мл, 120 мл, 130 мл,…., 2080 мл и 2090 мл. Вы находите их на полу комнаты и хотите разместить их так, чтобы стекло 2090, затем стекло 2080 внутри него, затем стекло 2070 внутри него и так далее. Этот метод сортировки неэффективен для больших списков, потому что поиск точного размера займет много времени, но именно так работает сортировка по выбору.
Сортировка слиянием
Сортировка слиянием - это метод сортировки, основанный на методе «разделяй и властвуй». Сортировка слиянием сначала делит массив на равные половины, а затем объединяет их в отсортированном порядке.
Алгоритм
- В подходе «разделяй и властвуй» рассматриваемая проблема делится на более мелкие подзадачи, а затем каждая проблема решается независимо.
2. Когда мы продолжаем разделять подзадачи на еще более мелкие подзадачи, мы, в конечном итоге, можем достичь стадии, когда дальнейшее деление невозможно.
3. Решены эти «атомарные» наименьшие возможные подзадачи (дроби). Решение всех подзадач окончательно объединяется, чтобы получить решение исходной проблемы.
Time Comp и Space Comp
Сложность времени наихудшего случая [Big-O]: O (n * log n)
Сложность наилучшего времени [Big-omega]: O (n * log n)
Средняя временная сложность [Big-theta]: O (n * log n)
Космическая сложность: O (n)
Временная сложность MergeSort составляет O (n * Log n) во всех трех случаях (худшем, среднем и лучшем), поскольку сортировка слиянием всегда делит массив на две половины и для объединения двух половин требуется линейное время.
Приложение
- Реальным случаем сортировки слиянием может быть такой сценарий: за одну ночь ваш офис был полностью разгромлен какими-то ворами или тому подобным, и все ваши многочисленные картотеки с папками и содержимым разбросаны повсюду. Сейчас 9 часов утра, а в 11 утра аудиторы готовы к важной проверке. Вы должны вернуть все эти файлы в порядок к 11 часам. Вы бежите по коридору и просите всех, кого можете найти, прийти и отсортировать большой файл аналогичного размера в алфавитном порядке, чтобы вы могли ОБЪЕДИНЯТЬ файлы обратно в том виде, в котором они были, когда вы повернули. выключил свет прошлой ночью.
- Приложение электронной коммерции Вы когда-нибудь замечали на любом веб-сайте электронной коммерции, что у них есть этот раздел «Вам может понравиться», они поддерживают массив для всех учетных записей пользователей, а затем тот, который имеет наименьшее количество инверсий с вашим массивом варианты, они начинают рекомендовать то, что они купили или что им нравится. А некоторые веб-сайты электронной коммерции, такие как policybazaar.com, trivago.com и т. Д., Используют свою поисковую систему для сбора данных с другого веб-сайта, чтобы обеспечить минимальную стоимость бронирования номера в отеле или покупки продукта.
- Если вы хотите разделить батон хлеба на 8 или 16 равных частей, обычно люди сначала разрезают его на две равные половины, а затем снова разрезают каждую половину на две равные половины, повторяя процесс, пока вы не получите столько кусочков, сколько захотите - 8, 16, 32 или что угодно. Практически никто не пытается разделить буханку сразу на 8 частей - люди угадывают половинки намного лучше, чем восьмые. Или мы склонны разбивать вещи на полезные части.
Шаблоны использования памяти и сортировка индексов
Когда размер сортируемого массива приближается к доступной первичной памяти или превышает ее, так что необходимо использовать (гораздо более медленный) диск или пространство подкачки, становится важным шаблон использования памяти алгоритма сортировки, и алгоритм, который мог бы быть справедливым. эффективен, когда массив легко помещается в ОЗУ, может стать непрактичным. В этом сценарии общее количество сравнений становится (относительно) менее важным, и количество раз, когда разделы памяти должны быть скопированы или заменены на диск и с диска, может доминировать над характеристиками производительности алгоритма. Таким образом, количество проходов и локализация сравнений могут быть более важными, чем необработанное количество сравнений, поскольку сравнения соседних элементов друг с другом происходят на скорости системной шины (или, при кэшировании, даже на скорости ЦП), что при сравнении к скорости диска, практически мгновенно.
Например, популярный алгоритм рекурсивной быстрой сортировки обеспечивает вполне разумную производительность при достаточном объеме ОЗУ, но из-за рекурсивного способа копирования частей массива он становится гораздо менее практичным, когда массив не помещается в ОЗУ, поскольку это может вызвать ряд ошибок. медленное копирование или перемещение на диск и с диска. В этом сценарии другой алгоритм может быть предпочтительнее, даже если он требует более полных сравнений.
Заключение
Результаты показывают, что быстрая сортировка эффективна как для малых, так и для больших целых чисел. На практике быстрая сортировка значительно быстрее, чем другие алгоритмы O (n log n). Что касается обмена, то пузырьковая сортировка выполняет наибольшее количество обменов, потому что каждый элемент будет сравниваться с соседними элементами и заменяться только в том случае, если они не в порядке. Сортировка вставкой быстро сортирует небольшой массив, а большой - очень медленно. Все методы сортировки очень важны для эффективного функционирования кода при управлении памятью.
Благодарю вас!
Авторы:
· Адити Кумари
· Шивам Агаркар
· Махи Амбекар
· Сиддхи Амилкантхвар
· Амит Радж
