Увод у сортирање алгоритама на Јави
Поредати информације по одређеном редоследу, често унутар оквира сличног низу, значи их сређивати. Можете користити различите захтеве за редоследом, а популарни су сортирање бројева од најмање до највећих или обрнуто или лексикографски сортирање низова. Обухватит ћемо различите алгоритме, од неефикасних, али интуитивних алтернатива до ефикасних алгоритама који се ефикасно имплементирају у Јави и на другим језицима уколико вас занима како сортирање функционира.
Различити алгоритми сортирања у Јави
Постоје различити алгоритми сортирања и нису сви подједнако ефикасни. Да бисмо их упоредили и видели који од њих су најбољи, анализираћемо њихове временске сложености.
- Инсертион Сорт
- Буббле Сорт
- Избор сортирања
- Сортирање спајањем
- Хеапсорт
1. Разврставање уметања
Концепт који стоји иза ставке Уметање распона дели на подраслове који су сортирани и несортирани. Класификовани део је на почетку трајања 1 и подудара се са првом (левом бочном) компонентом у низу. Прелазимо кроз низ и проширујемо класификовани део матрице за једну компоненту током сваке итерације. Када се проширимо, свежи елемент постављамо у сортирани под-низ. То радимо померањем свих елемената удесно док не установимо да не морамо да мењамо прву компоненту. Када је подебљани део сортиран узлазним редоследом, на пример, у следећем низу:
- 3 5 7 8 4 2 1 9 6: Размотрите 4 и убацивање овога је оно што нам треба. Смјењујемо се од 8> 4
- 2. 3 5 7 к 8 2 1 9 6
- 3 5 к 7 8 2 1 9 6
- 3 к 5 7 8 2 1 9 6
- 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+" ");
)
)
)
Излаз:
Након ове методе, једна компонента је проширила сортирани део, сада имамо пет уместо четири елемента. Свака итерација то уради и цео низ ће бити сортиран до краја.
Напомена: То је због тога што морамо да пребацимо целу тајну листу, једну по једну у свакој итерацији, што је О (н). За сваку компоненту сваке табеле то морамо учинити, што значи да је О (н 2) ограничен.2.2. Буббле Сорт
Ако мјехурић није у жељеном редослиједу, он дјелује замјеном сусједних компоненти. То се понавља све док све компоненте не буду у реду од почетка низа. Знамо да ако успемо да урадимо целокупну итерацију без замена, сви елементи у поређењу са њиховим суседним елементима били су у жељеном редоследу и, продужетак, целокупни низ. Разлог алгоритма за сортирање мехурића је тај што бројеви попут „буббле-а“ иду у „земљу“. Ако након одређеног износа поново прођете кроз инстанцу (4 је добра инстанца), приметићете да број лагано помера се удесно.
Кораци за сортирање мехурића су следећи:
- 4 2 1 5 3: Овде, прва два броја нису у исправном редоследу, стога морамо сортирати оба броја.
- 2 4 1 5 3: Након тога, наредни пар такође није у правом редоследу. Тако се сортирање поново догађа.
- 2 1 4 5 3: Ово двоје је у исправном редоследу, 4 <5, стога нема потребе да их мењате.
- 2 1 4 5 3 : Опет морамо заменити за правилан редослед.
- 2 1 4 3 5: Ево резултирајућег низа након једне итерације.
- Морамо поново да поновимо овај поступак док бројеви не буду у реду.
Шифра:
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) + " ");
)
)
)
Излаз:
3. Избор сортирања
Селецтион Сорт подели низ на низ класификација које нису сортиране. Овог пута, међутим, подврста сортирања се формира уметањем на крају сортиране матрице минимални елемент несортираног подземља, мењањем:
- 3 5 1 2 4
- 1 5 3 2 4
- 1 2 3 5 4
- 1 2 3 5 4
- 1 2 3 4 5
- 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+" ");
)
)
)
Излаз:
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. Хеап Сорт
Прво морате знати оквир на којем Хеапсорт делује - гомилу - да бисте схватили зашто делује. Ми ћемо посебно говорити о бинарној гомили, али то можете и генерализовати на друге конструкције гомиле. Копча је дрво које испуњава својство гомиле, наиме да сва деца имају односе према сваком чвору. Гомила такође мора бити готово готова. Бинарни уређај за скоро потпуну дубину има под-стабло д-1, са истим кореном, и сваки чвор има потпуно, лево подређење, с леве стране која се спушта.
Другим речима, добијате мањи и мањи број (мин-хеап) или већи и већи (мак-хеап) када се крећете низ стабло. Ево примера мак-хеап:
- 6 1 8 3 5 2 4 : Овде су бројеви обе деце мањи од матичних, па не морамо ништа да мењамо.
- 6 1 8 3 5 2 4: Ево, 5> 1, морамо их заменити. Морамо појачати за 5.
- 6 5 8 3 1 2 4: Оба броја деце су мања, све остаје исто.
- 6 5 8 3 1 2 4: Ево, 8> 6, стога бисмо их требали замијенити.
- 8 5 6 3 1 2 4: Након ове понављања, добићемо овај резултат.
Након поновљеног поступка поново ћемо добити следеће резултате:
- 8 5 6 3 1 2 4
- 4 5 6 3 1 2 8 : Замена
- 6 5 4 3 1 2 8 : Одузми се
- 2 5 4 3 1 6 8 : Замена
- 5 2 4 2 1 6 8 : Одузми се
- 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);
)
)
Излаз:
Можете је видети са тачке на ниво графикона, са леве на десно. Оно што смо овде постигли је да када имамо ктх компоненту у низу, положај њене деце је 2 \ * к + 1 и 2 \ * к + 2 (под претпоставком да индексирање почиње са 0). То можете надгледати ви. Положај родитеља је увек (к-1) / 2 за ктх компоненту. Можете лако „максимати“ било који распон, јер то знате. Проверите да ли је неко од његових деце ниже од оног за сваку компоненту. Ако је то случај, упарите једног родитеља и поновите овај корак рекурзивно са родитељем.
Напомена: Будући да итерирање петљи преко читавог низа чини хеапСорт) (очигледно О (Н), то би створило укупну сложеност Хеапсорт О-а (нлог н). Хеапсорт има тип на лицу места, што значи да захтева О ( 1) више простора од спајања сортирања, али има неке недостатке, попут тешких паралела.Закључак - Сортирање алгоритама у Јави
Разврставање је врло распрострањена процедура са скуповима података, било да се ради на даљој анализи, убрзавању претраге ефикаснијим алгоритмима који се ослањају на сортиране информације, податке о филтрирању итд. Сортирање је подржано на више језика и често сучеља затамњују оно што програмер ради.
Препоручени чланци
Ово је водич за сортирање алгоритама на Јави. Овдје разговарамо о различитим врстама сортирања на Јави, заједно са њиховим алгоритмима. Можете и да прођете кроз друге наше предложене чланке -
- Спајање алгоритам сортирања у Јави
- ЈЦомбоБок на Јави
- СтрингБуффер на Јави
- ЈТектФиелд на Јави
- Хеап Сорт ин Питхон
- Брзо сортирање алгоритама на Јави
- Комплетан водич за сортирање у Ц # са примерима
- Сортирање алгоритама у ЈаваСцрипт-у
- Водич за примере алгоритма Ц ++
- Комплетан водич за сортирање алгоритама на Питхон-у