Úvod do rýchlych triediacich algoritmov v Jave

Rýchle zoradenie v jave, známe tiež ako usporiadanie na výmenu oddielov, je algoritmus triedenia rozdelenia a dobývania. Rýchle zoradenie je dobrým príkladom algoritmu, ktorý najlepšie využíva vyrovnávaciu pamäť CPU, a to z dôvodu jej rozdelenia a dobývania. Algoritmus Quicksort je jedným z najpoužívanejších triediacich algoritmov, najmä na usporiadanie veľkých zoznamov a väčšina programovacích jazykov ho implementovala. V algoritme Quicksort sa pôvodné údaje rozdelia na dve časti, ktoré sa individuálne triedia a potom zlúčia, aby sa vytvorili triedené údaje.

Uvažujme, že pole (8, 6, 3, 4, 9, 2, 1, 7) je potrebné zoradiť pomocou funkcie Quick Sort.

Kroky na implementáciu algoritmov rýchleho triedenia

1. Z poľa vyberte prvok nazývaný pivot. Všeobecne je stredný prvok vybraný ako čap. Zoberme 4 ako pivot.

2. Usporiadajte zostavu na dve časti tak, aby sa prvky menšie ako čap dostali pred čap a po čapu sa objavili prvky väčšie ako čap. Nasledujú nasledujúce kroky:

  • Vyberte prvok úplne vľavo, tj 8, pretože 4 je čap a 8 je viac ako 4, 8 sa musí posúvať doprava od 4, na pravej strane nechávame 7, pretože je väčší ako 4 a vyberte 1 na výmenu s 8 teda po výmene sa pole stáva: 1, 6, 3, 4, 9, 2, 8, 7
  • Vyberte nasledujúci ľavý prvok, tj 6, pretože 4 je čap a 6 je viac ako 4, 6 je potrebné presunúť doprava od 4, na pravej strane ponecháme 7, 8, pretože sú väčšie ako 4 a vyberú 2 pre výmenu 6, teda po výmene sa pole stáva: 1, 2, 3, 4, 9, 6, 8, 7
  • Teraz, pretože všetky prvky naľavo od čapu sú menšie ako čap a všetky prvky napravo od čapu sú väčšie ako čap, urobili sme so 4 ako čapom.

3. Rekurzívne aplikujte kroky 1 a 2 pre ľavé podskupinu (pole s prvkami menšími ako otočný čap) a pre pravé podskupiny (pole s prvkami väčšími ako otočný čap). Ak pole obsahuje iba jeden alebo nulové prvky, potom sa pole považuje za najrôznejšie.

Program na implementáciu rýchlych triediacich algoritmov

Tu je program java na zoradenie celého čísla pomocou algoritmu rýchleho zoradenia.

kód:

import java.lang.*;
import java.util.*;
public class Main (
private int array();
private int length;
public void sort(int() inputArrayArr) (
if (inputArrayArr == null || inputArrayArr.length == 0) (
return;
)
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
)
private void performQuickSort(int lowerIndex, int higherIndex) (
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array(lowerIndex+(higherIndex-lowerIndex)/2);
// Divide into two subarrays
while (i <= j) (
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array(i) < pivot) (
i++;
)
while (array(j) > pivot) (
j--;
)
if (i <= j) (
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
)
)
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
)
private void swapNumbers(int i, int j) (
int temp = array(i);
array(i) = array(j);
array(j) = temp;
)
public static void main(String args())(
Main quickSort = new Main();
int() inputArray = (8, 6, 3, 4, 9, 2, 1, 7);
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
)
)

Výkon:

Výhody rýchlych triediacich algoritmov

Výhody algoritmu rýchleho zoradenia sú tieto:

  • Vynikajúca referenčná lokalita : Referenčnou lokalitou je schopnosť procesora opakovane pristupovať na rovnaké miesto v pamäti počas krátkeho časového obdobia. Rýchle triedenie v jave poskytuje vynikajúcu lokalitu referencie kvôli veľmi malému počtu chýb vyrovnávacej pamäte, ktoré sú na moderných architektúrach rozhodujúce pre výkon.
  • Rýchle zoradenie je paralelné: Po dokončení počiatočného kroku rozdelenia poľa do menších oblastí môžu byť všetky jednotlivé podskupiny zoradené nezávisle paralelne. Z tohto dôvodu má rýchle zoradenie lepšiu výkonnosť.

Analýza zložitosti rýchleho zoradenia

Quicksort je rýchly a chvost-rekurzívny algoritmus, ktorý pracuje na princípe rozdelenia a dobyť. Tu je jej analýza zložitosti v najlepších, priemerných a najhorších prípadoch:

  • Najlepšia komplexnosť prípadu: Ak pole alebo zoznam obsahuje n prvkov, pri prvom spustení bude potrebné O (n). Teraz triedenie zostávajúcich dvoch čiastkových polí trvá 2 * O (n / 2). Týmto sa v najlepšom prípade uzatvára zložitosť O (n logn).
  • Priemerná zložitosť prípadu: Priemerný prípad rýchlej voľby je O (n log n).
  • Zložitosť najhoršieho prípadu: Výber prvého alebo posledného by spôsobil výkon najhoršieho prípadu pre takmer zoradené alebo takmer spätne zoradené údaje. Rýchle zoradenie vykoná O (n 2) v najhoršom prípade.

V Java, Arrays. Metóda sort () používa na triedenie poľa algoritmus rýchleho zoradenia.

Odporúčané články

Toto je príručka pre rýchle zoradenie algoritmov v jazyku Java. Tu diskutujeme kroky na implementáciu, výhody a analýzu zložitosti algoritmu rýchleho triedenia v jave spolu s programom. Ďalšie informácie nájdete aj v nasledujúcich článkoch -

  1. Vloženie Zoradiť v Java
  2. slučka do-while v Java
  3. JComponent v Jave
  4. Štvorce v Jave
  5. Výmena v PHP
  6. Triedenie v C #
  7. Triedenie v Pythone
  8. Algoritmus C ++ Príklady algoritmu C ++

Kategórie:

Vývoj softvéru