Úvod do algoritmů rychlého třídění v Javě
Rychlé třídění v java, také známé jako třídění pro výměnu oddílů, je algoritmus třídění dělení a dobývání. Rychlé řazení je dobrým příkladem algoritmu, který nejlépe využívá mezipaměti CPU, a to z důvodu jeho rozdělení a dobytí povahy. Algoritmus Quicksort je jedním z nejpoužívanějších třídicích algoritmů, zejména pro třídění velkých seznamů a většina programovacích jazyků jej implementovala. V algoritmu Quicksort jsou původní data rozdělena do dvou částí, které jsou jednotlivě tříděny a poté sloučeny, aby vytvořily tříděná data.
Uvažujme, že pole (8, 6, 3, 4, 9, 2, 1, 7) je třeba třídit pomocí Rychlého třídění.
Kroky k implementaci algoritmů rychlého třídění
1. Z pole vyberte prvek nazvaný pivot. Obecně je prostřední prvek vybrán jako pivot. Vezměme 4 jako pivot.
2. Změňte uspořádání pole na dvě části tak, aby prvky menší než otočný čep přicházely dříve, než se otočný čep objeví, a prvky větší než otočný čep se objeví po otočném čepu. Jsou dodržovány následující kroky:
- Vyberte prvek nejvíce vlevo, tj. 8, protože 4 je otočný čep a 8 je více než 4, 8 je třeba přesunout doprava na 4, na pravé straně ponecháme 7, protože je větší než 4 a vyberte 1 pro výměnu s 8 tedy po výměně pole se stává: 1, 6, 3, 4, 9, 2, 8, 7
- Vyberte další levý prvek, tj. 6, protože 4 je otočný čep a 6 je více než 4, 6 je třeba přesunout doprava na 4, na pravé straně ponecháme 7, 8, protože jsou větší než 4 a vyzvednout 2 pro výměnu se 6, tedy po výměně se pole stává: 1, 2, 3, 4, 9, 6, 8, 7
- Nyní, protože všechny prvky nalevo od otočného čepu jsou menší než otočný čep a všechny prvky napravo od otočného čepu jsou větší než otočný čep, provedeme s otočným čepem 4.
3. Opakovaně aplikujte kroky 1 a 2 pro levé dílčí pole (pole s prvky menšími než pivot) a pro pravé dílčí pole (pole s prvky více než pivot). Pokud pole obsahuje pouze jeden nebo nula prvků, je pole považováno za nejrůznější.
Program implementace algoritmů rychlého třídění
Zde je program java pro třídění celých čísel pomocí algoritmu rychlého třídění.
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ýstup:
Výhody algoritmů rychlého třídění
Výhody algoritmu rychlého třídění jsou následující:
- Vynikající referenční lokalita : Referenční lokalita je schopnost procesoru opakovaně přistupovat ke stejnému paměťovému místu po krátkou dobu. Rychlé třídění v javě poskytuje vynikající polohu Reference díky velmi malému počtu chyb v mezipaměti, což je u moderních architektur rozhodující pro výkon.
- Rychlé třídění je rovnoběžné: Jakmile je dokončen počáteční krok rozdělení pole do menších oblastí, lze všechny jednotlivé dílčí pole řadit nezávisle paralelně. Z tohoto důvodu je rychlé řazení lepší.
Analýza složitosti rychlého třídění
Quicksort je rychlý a ocas rekurzivní algoritmus, který pracuje na principu rozdělení a dobytí. Zde je analýza složitosti v nejlepším, průměrném a nejhorším případě:
- Nejlepší složitost případu: Pokud pole nebo seznam obsahuje n prvků, bude při prvním spuštění potřeba O (n). Nyní třídění zbývajících dvou dílčích polí trvá 2 * O (n / 2). Tím se v nejlepším případě uzavírá složitost O (n logn).
- Průměrná složitost případu: Průměrný případ rychlého řazení je O (n log n).
- Složitost v nejhorším případě: Výběr prvního nebo posledního by způsobil nejhorší výkon pro téměř tříděná nebo téměř zpětně tříděná data. Rychlé řazení provádí O (n 2) v nejhorším případě.
V Javě, pole. Metoda sort () používá k třídění matic rychlý algoritmus řazení.
Doporučené články
Toto je průvodce po algoritmech rychlého třídění v Javě. Zde diskutujeme kroky k implementaci, výhodám a analýze složitosti algoritmu rychlého třídění v java spolu s programem. Další informace naleznete také v následujících článcích -
- Vložení Seřadit v Javě
- smyčka do-while v Javě
- JComponent v Javě
- Čtverce v Javě
- Výměna v PHP
- Třídění v C #
- Třídění v Pythonu
- Algoritmus C ++ | Příklady algoritmu C ++