Введение в алгоритмы сортировки в Java

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

Различные алгоритмы сортировки в Java

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

  1. Сортировка вставки
  2. Пузырьковая сортировка
  3. Выбор сортировки
  4. Сортировка слиянием
  5. Пирамидальная сортировка

1. Вставка сортировки

Концепция сортировки вставкой делит диапазон на подмассивы, которые отсортированы и не отсортированы. Секретная часть находится в начале продолжительности 1 и соответствует первому (левому) компоненту в массиве. Мы перемещаемся по массиву и расширяем классифицированную часть массива на один компонент во время каждой итерации. Когда мы расширяемся, мы помещаем свежий элемент в отсортированный подмассив. Мы делаем это, перемещая все элементы вправо, пока не обнаружим, что нам не нужно менять первый компонент. Когда часть, выделенная жирным шрифтом, сортируется в порядке возрастания, например, в следующем массиве, это происходит:

  1. 3 5 7 8 4 2 1 9 6: рассмотрим 4, и вставка это то, что нам нужно. Мы сдвигаемся с 8> 4
  2. 2. 3 5 7 x 8 2 1 9 6
  3. 3 5 x 7 8 2 1 9 6
  4. 3 х 5 7 8 2 1 9 6
  5. 3 4 5 7 8 2 1 9 6

Код:

public class InsertionSortEx (
public static void insertionSort(int() arr) (
for (int x = 1; x < arr.length; x++) (
int current = arr(x);
int y = x - 1;
while(y >= 0 && current < arr(y)) (
arr(y+1) = arr(y);
y--;
)
arr(y+1) = current;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 7, 8, 4, 2, 1, 9, 6);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
insertionSort(arr1);//sorting array using insertion sort
System.out.println("After Insertion Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Выход:

Следуя этому методу, один компонент расширил отсортированную часть, теперь у нас есть пять вместо четырех элементов. Каждая итерация делает это, и весь массив будет отсортирован к концу.

Примечание: это потому, что нам нужно передавать весь классифицированный список один за другим в каждой итерации, что равно O (n). Для каждого компонента в каждой таблице мы должны сделать это, что означает, что он ограничен O (n 2).

2. Пузырьковая сортировка

Если пузырек находится не в нужном порядке, он работает путем замены соседних компонентов. Это повторяется до тех пор, пока все компоненты не будут в порядке с начала массива. Мы знаем, что если нам удастся выполнить всю итерацию без перестановок, все элементы по сравнению со смежными элементами будут в желаемом порядке и, соответственно, весь массив. Причиной использования алгоритма Bubble Sort является то, что числа типа «пузыриваются» в «землю». Если после определенного количества вы снова пройдете экземпляр (4 - хороший пример), вы заметите, что число медленно движется вправо.

Шаги к пузырьковой сортировке следующие:

  1. 4 2 1 5 3: Здесь первые два числа расположены не в правильном порядке, поэтому мы должны отсортировать оба числа.
  2. 2 4 1 5 3: После этого следующая пара номеров также не в правильном порядке. Так что сортировка происходит снова.
  3. 2 1 4 5 3: Эти два находятся в правильном порядке, 4 <5, следовательно, нет необходимости менять их.
  4. 2 1 4 5 3 : Снова мы должны поменяться местами для правильного порядка.
  5. 2 1 4 3 5: Вот результирующий массив после одной итерации.
  6. Мы должны повторить этот процесс снова, пока числа не будут в правильном порядке.

Код:

public class BubbleSortExample (
public static void bubbleSort(int() arr) (
int n = arr.length;
int tmp = 0;
for(int x=0; x < n; x++)(
for(int y=1; y < (nx); y++)(
if(arr(y-1) > arr(y))(
//swap elements
tmp = arr(y-1);
arr(y-1) = arr(y);
arr(y) = tmp;
)
)
)
)
public static void main(String() args) (
int arr() =(4, 2, 1, 5, 3);
System.out.println("Array Before Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
System.out.println();
bubbleSort(arr);
System.out.println("Array After Bubble Sort");
for(int x=0; x < arr.length; x++)(
System.out.print(arr(x) + " ");
)
)
)

Выход:

Примечание: это могло бы закончиться в бесконечном цикле, если бы я использовал a (i)> = a (i + 1), потому что это соединение все еще было бы допустимо с эквивалентными компонентами и таким образом всегда меняло их с одного элемента на другой.

3. Выбор сортировки

Сортировка выбора разбивает массив на массив классификаций, которые не отсортированы. Однако на этот раз подмассив сортировки формируется путем вставки в конец отсортированного массива минимального элемента несортированного подмассива путем замены:

  1. 3 5 1 2 4
  2. 1 5 3 2 4
  3. 1 2 3 5 4
  4. 1 2 3 5 4
  5. 1 2 3 4 5
  6. 1 2 3 4 5

Код:

public class SelectionSortEx (
public static void selectionSort(int() arr)(
for (int x = 0; x < arr.length - 1; x++)
(
int indx = x;
for (int y = x + 1; y < arr.length; y++)(
if (arr(y) < arr(indx))(
indx = y;
)
)
int smallNumber = arr(indx);
arr(indx) = arr(x);
arr(x) = smallNumber;
)
)
public static void main(String a())(
int() arr1 = (3, 5, 1, 2, 4);
System.out.println("Before Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
System.out.println();
selectionSort(arr1);
System.out.println("After Selection Sorting");
for(int x:arr1)(
System.out.print(x+" ");
)
)
)

Выход:

Примечание . Минимальное значение O (n) для размера массива, поскольку все компоненты должны быть проверены. Для каждого элемента массива мы должны найти минимум и ограничить весь процесс O (n 2).

4. Объединить сортировку

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

Это дерево показывает, как функционируют рекурсивные вызовы. Массивы, отмеченные стрелкой вниз, - это массивы, для которых мы вызываем функцию, а мы сливаем массивы со стрелками вверх. Затем вы следуете за стрелкой к краю дерева, а затем возвращаетесь и сливаетесь. У нас есть диапазон 3 5 3 1, поэтому мы разбиваем его на 3 5 4 и 2 1. Мы разбиваем их на части, чтобы отсортировать. Мы начинаем объединять и сортировать их, когда идем ко дну.

Код:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class MergeSort (
static void merge(int() array, int lowval, int midval, int highval)(
int x, y, k;
int() c= new int(highval-lowval+1);
k = 0;
x=lowval;
y=midval+1;
while(x<=midval && y<=highval)(
if(array(x)<=array(y))(
c(k++) = array(x++);
)
else(
c(k++) = array(y++);
)
)
while(x<=midval)(
c(k++) = array(x++);
)
while(y<=highval)(
c(k++) = array(y++);
)
k=0;
for(x = lowval; x<=highval; x++)(
array(x) = c(k++);
)
)
static void mergeSort(int() array, int lowval, int highval)(
if(highval-lowval+1>1)(
int midval = (lowval+highval)/2;
mergeSort(array, lowval, midval);
mergeSort(array, midval+1, highval);
merge(array, lowval, midval, highval);
)
)
public static void main(String() args) (
BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
int size;
System.out.println("Enter the array");
try (
size = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("Please Enter valid Input");
return;
)
int() array = new int(size);
System.out.println("Enter array elements");
int x;
for (x = 0; x < array.length; x++) (
try (
array(x) = Integer.parseInt(r.readLine());
) catch (Exception e) (
System.out.println("An error Occurred");
)
)
System.out.println("After Sorting");
System.out.println(Arrays.toString(array));
mergeSort(array, 0, array.length-1);
System.out.println("Before Merge Sorting");
System.out.println(Arrays.toString(array));
)
)

В этой программе мы попросили пользователя ввести ввод. Вывод будет в отсортированном порядке на основе ввода пользователя.

Выход:

5. Сортировка кучи

Сначала вы должны знать структуру, на которой работает Heapsort - куча, - чтобы понять, почему он работает. Мы будем конкретно говорить о двоичной куче, но вы также можете обобщить это на другие конструкции кучи. Куча - это дерево, которое выполняет свойство кучи, а именно то, что все его дочерние элементы имеют отношения с каждым узлом. Куча также должна быть почти закончена. Почти полный двоичный файл d-глубины имеет поддерево d-1 с тем же корнем, а каждый узел имеет полное левое поддерево с нисходящим левым.

Другими словами, вы получаете меньшее и меньшее число (min-heap) или большее и большее (max-heap) при движении вниз по дереву. Вот пример max-heap:

  1. 6 1 8 3 5 2 4 : Здесь номера обоих детей меньше, чем у родителей, поэтому нам не нужно ничего менять.
  2. 6 1 8 3 5 2 4: Здесь, 5> 1, мы должны поменять их местами. Нам нужно сложить на 5.
  3. 6 5 8 3 1 2 4: оба номера детей меньше, все остаются одинаковыми.
  4. 6 5 8 3 1 2 4: Здесь 8> 6, поэтому мы должны поменять их местами.
  5. 8 5 6 3 1 2 4: После этой итерации мы получим этот результат.

После повторения этого процесса мы получим следующие результаты:

  • 8 5 6 3 1 2 4
  1. 4 5 6 3 1 2 8 : обмен
  2. 6 5 4 3 1 2 8 : Heapify
  3. 2 5 4 3 1 6 8 : обмен
  4. 5 2 4 2 1 6 8 : Heapify
  5. 1 2 4 2 5 6 8 : обмен

Код:

public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
) public class HeapSort
(
public void sort(int arr())
(
int n = arr.length;
for (int x = n / 2 - 1; x >= 0; x--)
heapify(arr, n, x);
for (int x=n-1; x>=0; x--)
int tmp = arr(0);
arr(0) = arr(x);
arr(x) = tmp;
heapify(arr, x, 0);
)
)
void heapify(int arr(), int n, int x)
(
int largest = x;
int L = 2*x + 1;
int r = 2*x + 2;
if (L arr(largest))
largest = L;
if (r arr(largest))
largest = r;
if (largest != x)
(
int swap = arr(x);
arr(x) = arr(largest);
arr(largest) = swap;
heapify(arr, n, largest);
)
)
static void printArray(int arr())
(
int n = arr.length;
for (int x=0; x System.out.print(arr(x)+" ");
System.out.println();
)
public static void main(String args())
(
int arr() = (6, 1, 8, 3, 5, 2, 4);
int n = arr.length;
System.out.println("Before Sorting:");
printArray(arr);
HeapSort ob = new HeapSort();
ob.sort(arr);
System.out.println("After Heap Sorting:");
printArray(arr);
)
)

Выход:

Вы можете просматривать его от точки к уровню графика, слева направо. Здесь мы добились того, что когда у нас есть k-й компонент в массиве, позиция его дочерних элементов равна 2 \ * k + 1 и 2 \ * k + 2 (при условии, что индексирование начинается с 0). Это может контролироваться вами. Положение родителя всегда (k-1) / 2 для k-го компонента. Вы можете легко «максимизировать кучу» любого диапазона, потому что вы это знаете. Проверьте, ниже ли один из его дочерних элементов для каждого компонента. Если это так, соедините одного родителя и повторите этот шаг с родителем.

Примечание: поскольку итерация циклов for по всему массиву делает heapSort) (очевидно, O (N), это создаст общую сложность Heapsort O (nlog n). Heapsort имеет тип «на месте», что означает, что он требует O ( 1) больше места, чем сортировка слиянием, но у нее есть некоторые недостатки, такие как параллели, которые сложны.

Заключение - Алгоритмы сортировки в Java

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

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

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

  1. Алгоритмы сортировки слиянием в Java
  2. JComboBox в Java
  3. StringBuffer в Java
  4. JTextField в Java
  5. Сортировка кучи в Python
  6. Алгоритмы быстрой сортировки в Java
  7. Полное руководство по сортировке в C # с примерами
  8. Алгоритмы сортировки в JavaScript
  9. Руководство по примерам алгоритма C ++
  10. Полное руководство по сортировке алгоритмов в Python

Категория:

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