Программа сортировки слиянием в Java: разница между сортировкой слиянием и быстрой сортировкой

Введение в программу сортировки слиянием в JAVA

Как следует из названия, программа сортировки слиянием в JAVA представляет собой алгоритм сортировки. Он был классически концептуализирован как алгоритм «разделяй и властвуй» в JAVA. Программа сортировки слиянием в Java работает путем рекурсивного разбиения входного массива на две или более составляющих его подзадач до тех пор, пока они не станут достаточно простыми для непосредственного решения.

Составляющие подзадачи могут быть либо похожими, либо в чем-то связанными с исходной проблемой. Затем отдельные решения каждой подзадачи объединяются для получения решения исходной родительской проблемы.

Как работает программа сортировки слиянием в Java?

Как упоминалось ранее, программа сортировки слиянием в JAVA представляет собой алгоритм «разделяй и властвуй». Это стабильная сортировка, означающая, что элементы массива сохраняют свое исходное положение относительно друг друга на протяжении всего процесса сортировки.

• Делить: На этом шаге входной массив делится на две составляющие его половины. Этот шаг постоянно повторяется для всех полученных полумассивов до тех пор, пока не останется половинных массивов для дальнейшего деления.
• Conquer: на этом этапе разделенные массивы сортируются и объединяются снизу вверх, чтобы получить окончательный отсортированный массив.

Разница между быстрой сортировкой и программой сортировки слиянием в Java

Несмотря на функциональное сходство, следует уделить особое внимание фундаментальному различию между быстрой сортировкой и сортировкой слиянием в JAVA.

• Механизм : быстрая сортировка — это внутренний алгоритм сортировки на месте, а сортировка слиянием — внешний алгоритм сортировки вне места. В быстрой сортировке элементы сортируются по ключевому элементу, известному как сводная точка. Опорой обычно является среднее значение во входном массиве. Элементы с меньшим значением, чем опорная точка, перемещаются в левую сторону от опорной точки, а элементы с большим значением — в правую сторону от нее. Здесь левая сторона называется левым разделом, а правая сторона называется правым разделом. Наоборот, сортировка слиянием многократно разбивает массив на два подмассива (n/2), пока не останется только один элемент. Затем он объединяет подмассивы, чтобы сформировать отсортированный массив.
• Применение: хотя быстрая сортировка подходит для небольших массивов, сортировка слиянием работает с любым массивом, независимо от его размера.
• Скорость : в случае быстрой сортировки чем меньше набор данных, тем быстрее алгоритм. С другой стороны, сортировка слиянием работает с одинаковой скоростью для всех наборов данных.
• Требования к пространству и использование памяти: как упоминалось ранее, сортировка слиянием — это внешний, неуместный алгоритм сортировки. Его пространственная сложность равна O (n). Следовательно, для сортировки вспомогательного массива требуется дополнительное хранилище (O (n)).

Читайте также: Типы литералов в Java с примерами

Анализ временной сложности программы сортировки слиянием в JAVA

Программа сортировки слиянием в JAVA имеет временную сложность O (n*log n). Согласно бинарному поиску, всякий раз, когда число делится пополам на каждом шаге, оно может быть представлено логарифмической функцией «log n». Количество шагов (не более) может быть представлено как log n +1. Середина любого подмассива равна O (1).

Таким образом, для объединения подмассивов потребуется время работы O (n). Следовательно, общее время для программы сортировки слиянием в JAVA становится n (log n +1). Это составляет временную сложность O (n * log n) во всех трех случаях (худший, средний и лучший), поскольку сортировка слиянием всегда требует линейного времени для слияния двух половин.

Изучайте онлайн-курсы по программному обеспечению от лучших университетов мира. Участвуйте в программах Executive PG, Advanced Certificate Programs или Master Programs, чтобы ускорить свою карьеру.

Подводя итоги

Точно так же, как отсортированные данные для людей являются логически обоснованными и более легкими для понимания, отсортированные массивы более удобны для работы с компьютерами. Именно здесь программа сортировки слиянием в JAVA оказывается полезной. Это эффективный алгоритм сортировки общего назначения на основе сравнения.

Если вам интересно узнать больше о Java, разработке программного обеспечения с полным стеком, ознакомьтесь с программой Executive PG upGrad и IIIT-B по разработке программного обеспечения с полным стеком, которая предназначена для работающих профессионалов и предлагает более 500 часов тщательного обучения, 9+ проекты и задания, статус выпускника IIIT-B, практические практические проекты и помощь в трудоустройстве в ведущих фирмах.