Введение в быструю сортировку в Java

В следующей статье «Быстрая сортировка в Java» приведена схема алгоритма быстрой сортировки в Java. Алгоритм быстрой сортировки является одним из алгоритмов сортировки, который эффективен и аналогичен алгоритму сортировки слиянием. Это один из широко используемых алгоритмов для сортировки в реальном времени. Временная сложность этого алгоритма в наихудшем случае составляет O (n 2), временная сложность в среднем случае составляет O (n log n), а временная сложность в лучшем случае - O (n log n).

Сложность пространства, если O (n log n), где n - это размер ввода. Процесс сортировки включает в себя разбиение входных данных, рекурсивные итерации и маркировку ключевого элемента для каждой рекурсии. Тип сортировки в этом алгоритме включает сравнение соседних элементов итеративным способом.

Как Quick Sort работает в Java?

Алгоритм быстрой сортировки может быть реализован в Java путем формирования псевдокода с последовательностью шагов, разработанных и выполняемых эффективным образом.

  1. Основной принцип алгоритма быстрой сортировки, который он работает, основан на подходе «разделяй и властвуй», а также является эффективным алгоритмом сортировки.
  2. Входной массив делится на подмассивы, и деление основано на элементе центра, который является центральным элементом. Подмассивы по обе стороны от элемента поворота являются основными областями, где фактически происходит сортировка.
  3. Центральный элемент поворота является основой для разделения массива на два раздела, где левая половина элементов массива меньше, чем элемент поворота, а правая половина элементов массива больше, чем элемент поворота.
  4. Перед рассмотрением элемента pivot это может быть любой из элементов массива. Это обычно рассматривается как средний или первый или последний для простоты понимания. Элемент pivot может быть случайным из любого элемента массива.
  5. В нашем примере последний элемент массива рассматривается как сводный элемент, где разбиение подмассивов начинается с правого конца массива.
  6. Наконец, элемент pivot будет находиться в своей фактической отсортированной позиции после завершения процесса сортировки, где основной процесс сортировки заключается в логике разбиения алгоритма сортировки.
  7. Эффективность алгоритма зависит от размера подмассивов и их сбалансированности. Чем больше несбалансированы под-массивы, тем больше временная сложность приведет к сложности в худшем случае.
  8. Выбор элементов поворота случайным образом приводит к лучшей временной сложности во многих случаях вместо того, чтобы выбирать конкретные начальный, конечный или средний индексы в качестве элементов поворота.

Примеры реализации быстрой сортировки в Java

Алгоритм быстрой сортировки был реализован с использованием языка программирования Java, как показано ниже, и выходной код был отображен под кодом.

  1. Код изначально принимает входные данные, используя метод quickSortAlgo () с массивом, начальным индексом и конечным индексом, т. Е. Длиной массива в качестве аргументов.
  2. После вызова метода quickSortAlgo () он проверяет, меньше ли начальный индекс, чем конечный индекс, а затем вызывает метод arrayPartition (), чтобы получить значение элемента pivot.
  3. Элемент partition содержит логику размещения меньших и больших элементов вокруг элемента pivot на основе значений элемента.
  4. После получения индекса сводного элемента после выполнения метода секционирования метод quickSortAlgo () вызывается сам по себе рекурсивно, пока все подмассивы не будут разбиты на разделы и полностью отсортированы.
  5. В логике разбиения последний элемент назначается как элемент поворота, а первый элемент сравнивается с элементом поворота, т.е. последним, в котором элементы меняются местами на основе того, меньше они или больше.
  6. Этот процесс рекурсии происходит до тех пор, пока все элементы массива не будут разделены и отсортированы, где конечным результатом будет объединенный отсортированный массив.
  7. Элементы меняются внутри итерации цикла for только в том случае, если элемент меньше или равен элементу pivot.
  8. После завершения итерационного процесса последний элемент заменяется, т. Е. Значение элемента pivot перемещается в левую сторону, так что создаются новые разделы, и тот же процесс повторяется в форме рекурсии, что приводит к серии операций сортировки на разных возможных разделах. как формирование подмассивов из заданных элементов массива.
  9. Приведенный ниже код может быть запущен в любой среде IDE, а вывод можно проверить, изменив значение массива в main (). Метод main используется только для получения вывода в консоли. Как часть стандартов Java-кодирования, основной метод может быть удален ниже, и объект может быть создан, и ниже методы могут быть вызваны, делая их нестатичными.

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

/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm (
public static void main(String() args) (
int() array = ( 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 );
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) (
System.out.print(ar + " ");
)
)
public static int arrayPartition(int() array, int start, int end) (
int pivot = array(end);
int i = (start - 1);
for (int ele = start; ele < end; ele++) (
if (array(ele) <= pivot) (
i++;
int swap = array(i);
array(i) = array(ele);
array(ele) = swap;
)
)
// Swapping the elements
int swap = array(i + 1);
array(i + 1) = array(end);
array(end) = swap;
return i + 1;
)
public static void quickSortAlgo(int() arrayTobeSorted, int start, int end) (
if (start < end) (
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
)
)
)

Выход:

Вывод

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

Рекомендуемые статьи

Это руководство по быстрой сортировке в Java. Здесь мы обсудим, как Quick Sort работает в Java вместе с примером и реализацией кода. Вы также можете просмотреть наши другие предлагаемые статьи, чтобы узнать больше -

  1. Сортировка кучи в Java
  2. Что такое двоичное дерево в Java?
  3. Битовая манипуляция в Java
  4. Обзор сортировки слиянием в JavaScript
  5. Обзор быстрой сортировки в JavaScript
  6. Сортировка кучи в Python
  7. Топ 6 Алгоритм сортировки в JavaScript

Категория:

Разработка программного обеспечения