Algoritmus QuickSort v JavaScriptu

Co je Rychlé řazení?

Algoritmus Quick Sort sleduje přístup Divide and Conquer. Rozděluje prvky na menší části na základě určitých podmínek a provádění operací třídění na těchto rozdělených menších částech.

Algoritmus Quick Sort je jedním z nejpoužívanějších a nejpopulárnějších algoritmů v jakémkoli programovacím jazyce. Pokud jste ale vývojářem JavaScriptu, možná jste slyšeli o sort (), který je již v JavaScriptu k dispozici. Pak jste si možná mysleli, co tento algoritmus rychlého řazení potřebuje. Abychom tomu porozuměli, nejprve potřebujeme, co je třídění a jaké je výchozí třídění v JavaScriptu.

Co je třídění?

Třídění není nic jiného než uspořádání prvků v pořadí, které chceme. Možná jste na to narazili ve školních nebo vysokoškolských dnech. Stejně jako uspořádání čísel od menších k větším (vzestupně) nebo od větších k menším (sestupně) je to, co jsme viděli až dosud a nazývá se třídění.

Výchozí řazení v JavaScriptu

Jak již bylo zmíněno dříve, JavaScript má sort () . Vezměme si příklad s několika poli prvků jako [5,3,7,6,2,9] a chceme seřadit tyto prvky pole ve vzestupném pořadí. Stačí zavolat sort () na pole items a seřadí prvky pole ve vzestupném pořadí.

Kód:

var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]

Jaký je důvod zvolit v JavaScriptu Rychlé řazení před výchozím řazení ()

Ačkoli sort () dává požadovaný výsledek, problém spočívá v tom, jak seřadí prvky pole. Výchozí řazení () v JavaScriptu používá třídění vložením podle V8 Engine prohlížeče Chrome a sloučení třídění podle Mozilla Firefox a Safari .

Jiné to ale není vhodné, pokud potřebujete řadit velké množství prvků. Řešením je tedy použití rychlého řazení pro velkou datovou sadu.

Abychom to úplně pochopili, musíte vědět, jak funguje rychlé třídění, a nechte nás to nyní vidět podrobně.

Co je rychlé řazení?

Rychlé řazení sleduje algoritmus Divide and Conquer . Rozděluje prvky na menší části na základě určitých podmínek a provádí operace třídění na těchto rozdělených menších částech. Funguje tedy dobře pro velké datové sady. Tady jsou kroky, jak rychlé řazení funguje jednoduchými slovy.

Nejprve vyberte prvek, který má být nazýván jako otočný prvek.
Dále porovnejte všechny prvky pole s vybraným otočným prvkem a uspořádejte je tak, aby prvky menší než otočný prvek byly nalevo a větší než otočný čep byly vpravo.
Nakonec proveďte stejné operace s levými a pravými bočními prvky otočného prvku.

To je tedy základní osnova rychlého řazení. Zde jsou kroky, které je třeba postupovat jeden po druhém, aby bylo možné provést rychlé třídění.

Jak funguje QuickSort

Nejprve v poli najděte prvek „pivot“ .
Spusťte levý ukazatel na první prvek pole.
Spusťte pravý ukazatel na posledním prvku pole.
Porovnejte prvek ukazující levým ukazatelem a pokud je menší než otočný prvek, posuňte levý ukazatel doprava (přidejte 1 do levého indexu). Pokračujte tak dlouho, dokud prvek na levé straně nebude větší nebo roven prvku otáčení.
Porovnejte prvek ukazující s pravým ukazatelem a pokud je větší než otočný prvek, posuňte pravý ukazatel doleva (odečtěte 1 do pravého indexu). Pokračujte v tom, dokud prvek na pravé straně není menší nebo roven prvku otáčení.
Zkontrolujte, zda je levý ukazatel menší nebo rovný pravému ukazateli, a pak viděl prvky v umístěních těchto ukazatelů.
Zvýšení levého ukazatele a snížení pravého ukazatele.
Pokud je index levého ukazatele stále menší než index pravého ukazatele, opakujte postup; else vrátí index levého ukazatele.

Podívejme se tedy na tyto kroky s příkladem. Uvažujme řadu prvků, které musíme seřadit [5,3,7,6,2,9].

Určete prvek Pivot

Ale než se pustíte do rychlého řazení, hraje hlavní roli výběr prvku otočení. Pokud vyberete první prvek jako otočný prvek, bude mít nejhorší výkon v seřazeném poli. Vždy je tedy vhodné vybrat jako otočný prvek prostřední prvek (délku pole děleno 2) a uděláme totéž.

Tady jsou kroky k provedení rychlého řazení, které je ukázáno na příkladu [5,3,7,6,2,9].

KROK 1: Určete pivot jako střední prvek. Takže, 7 je otočný prvek.

KROK 2: Spusťte levý a pravý ukazatel jako první a poslední prvek pole. Takže levý ukazatel ukazuje na 5 v indexu 0 a pravý ukazatel ukazuje na 9 v indexu 5.

KROK 3: Porovnejte prvek u levého ukazatele s otočným prvkem. Protože 5 <6 posune levý ukazatel doprava na index 1.

KROK 4: Nyní stále 3 <6, takže posuňte levý ukazatel na jeden další index doprava. Takže nyní 7> 6 zastaví zvyšování levého ukazatele a nyní je levý ukazatel na indexu 2.

KROK 5: Nyní porovnejte hodnotu u pravého ukazatele s otočným prvkem. Protože 9> 6 posuňte pravý ukazatel doleva. Nyní jako 2 <6 zastavte pohyb pravého ukazatele.

KROK 6: Zaměňte obě hodnoty přítomné v levém a pravém ukazateli navzájem.

KROK 7: Posuňte oba ukazatele o další krok.

KROK 8: Protože 6 = 6, přesuňte ukazatele na další krok a zastavte se, když levý ukazatel prochází pravým ukazatelem a vrací index levého ukazatele.

Takže zde na základě výše uvedeného přístupu musíme napsat kód pro výměnu prvků a rozdělení pole, jak je uvedeno ve výše uvedených krocích.

Kód pro výměnu dvou čísel v JavaScriptu:

function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}

Kód pro provedení oddílu, jak je uvedeno ve výše uvedených krocích:

function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //swap two elementsi++;j--;}}return i;}

Proveďte rekurzivní operaci

Jakmile provedete výše uvedené kroky, index levého ukazatele bude vrácen a my ho musíme použít k rozdělení pole a provedení rychlého řazení v této části. Proto se nazývá algoritmus Divide and Conquer.

Rychlé řazení se tedy provádí, dokud nejsou seřazeny všechny prvky v levém a pravém poli.

Poznámka: Rychlé řazení se provádí na stejném poli a v procesu se nevytváří žádná nová pole.

Takže musíme zavolat tento oddíl () vysvětlený výše a na základě toho rozdělíme pole na části. Tady je kód, kde jej používáte,

function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar result = quickSort(items, 0, items.length - 1);

Vyplňte kód rychlého řazení:

var items = [5,3,7,6,2,9];function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}function partition(items, left, right) {var pivot = items[Math.floor((right + left) / 2)], //middle elementi = left, //left pointerj = right; //right pointerwhile (i <= j) {while (items[i] < pivot) {i++;}while (items[j]> pivot) {j--;}if (i <= j) {swap(items, i, j); //sawpping two elementsi++;j--;}}return i;}function quickSort(items, left, right) {var index;if (items.length> 1) {index = partition(items, left, right); //index returned from partitionif (left < index - 1) { //more elements on the left side of the pivotquickSort(items, left, index - 1);}if (index < right) { //more elements on the right side of the pivotquickSort(items, index, right);}}return items;}// first call to quick sortvar sortedArray = quickSort(items, 0, items.length - 1);console.log(sortedArray); //prints [2,3,5,6,7,9]