QuickSort algoritms JavaScript

Kas ir ātrā kārtošana?

Ātrās kārtošanas algoritms ievēro dalīšanas un iekarošanas pieeju. Tas sadala elementus mazākās daļās, pamatojoties uz kādu nosacījumu un veicot šķirošanas darbības tām sadalītajām mazākām daļām.

Ātrās šķirošanas algoritms ir viens no visbiežāk izmantotajiem un populārākajiem algoritmiem jebkurā programmēšanas valodā. Bet, ja esat JavaScript izstrādātājs, jūs, iespējams, dzirdējāt par sort (), kas jau ir pieejams JavaScript. Tad jūs varētu domāt, kāda ir šī ātrās šķirošanas algoritma nepieciešamība. Lai to saprastu, vispirms mums ir nepieciešams kārtošana un noklusējuma kārtošana JavaScript.

Kas ir šķirošana?

Šķirošana nav nekas cits kā elementu kārtošana vēlamajā secībā. Jūs, iespējams, esat saskāries ar to skolas vai koledžas dienās. Līdzīgi skaitļu sakārtošanai no mazāka līdz lielākam (augšupejošam) vai no lielāka līdz mazākam (lejupejošam) ir tas, ko mēs redzējām līdz šim, un to sauc par šķirošanu.

Noklusējuma šķirošana JavaScript

Kā minēts iepriekš, JavaScript ir sort () . Ņemsim piemēru ar dažiem elementu masīviem, piemēram, [5,3,7,6,2,9], un vēlēsimies kārtot šo masīvu elementus augošā secībā. Vienkārši izsauciet sort () vienumu masīvā, un tas sakārto masīva elementus augošā secībā.

Kods:

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

Kāds ir iemesls, kāpēc JavaScript izvēlēties ātru kārtošanu, nevis noklusēto kārtojumu ()

Lai gan sort () dod vēlamo rezultātu, problēma ir tajā, kā tā kārto masīva elementus. JavaScript noklusējuma kārtojums () izmanto ievietošanas kārtošanu pēc Chrome V8 dzinēja un apvienošanas kārtojumu pēc Mozilla Firefox un Safari .

Bet, tas nav piemērots, ja jums ir jāšķiro liels skaits elementu. Tātad, risinājums ir izmantot ātru kārtošanu lielai datu kopai.

Tātad, lai pilnībā saprastu, jums jāzina, kā darbojas ātrā kārtošana, un ļaujiet mums to tagad redzēt detalizēti.

Kas ir ātrā kārtošana?

Ātra šķirošana seko sadalīšanas un iekarošanas algoritmam. Tas ir elementu sadalīšana mazākās daļās, pamatojoties uz kādu nosacījumu, un šķirošanas darbību veikšana sadalītajās mazākās daļās. Tādējādi tas labi darbojas lielām datu kopām. Tātad, šeit ir norādīti soļi, kā ātra šķirošana darbojas vienkāršos vārdos.

Vispirms atlasiet elementu, kas jāsauc par pagrieziena elementu.
Pēc tam salīdziniet visus masīva elementus ar izvēlēto šarnīra elementu un sakārtojiet tos tā, lai elementi, kas ir mazāki par šarnīra elementu, būtu pa kreisi un lielāki par pagrieziena punktu - pa labi.
Visbeidzot, veiciet tās pašas darbības ar pagrieziena elementa kreiso un labo sānu elementiem.

Tātad, tas ir ātrās kārtošanas pamats. Lai veiktu ātro kārtošanu, ir jāveic sekojošās darbības.

Kā darbojas QuickSort

Vispirms atrodiet masīvā elementu "šarnīrsavienojums" .
Sāciet kreiso rādītāju pie masīva pirmā elementa.
Sāciet pareizo rādītāju masīva pēdējā elementā.
Salīdziniet elementu, kas norāda uz kreiso rādītāju, un, ja tas ir mazāks par pagrieziena elementu, tad pārvietojiet kreiso rādītāju pa labi (kreisajam rādītājam pievienojiet 1). Turpiniet to, līdz kreisās puses elements ir lielāks vai vienāds ar pagrieziena elementu.
Salīdziniet elementu, kas norāda uz labo rādītāju, un, ja tas ir lielāks par pagrieziena elementu, tad pārvietojiet labo rādītāju pa kreisi (atņemiet 1 labajā rādītājā). Turpiniet to, līdz labās puses elements ir mazāks vai vienāds ar pagrieziena elementu.
Pārbaudiet, vai kreisais rādītājs ir mazāks vai vienāds ar labo rādītāju, pēc tam redzēja elementus šo rādītāju vietās.
Palieliniet kreiso rādītāju un samaziniet labo rādītāju.
Ja kreisā rādītāja rādītājs joprojām ir mazāks nekā labā rādītāja indekss, atkārtojiet procesu; pretējā gadījumā atgriež kreisā rādītāja indeksu.

Apskatīsim šīs darbības ar piemēru. Apskatīsim elementu masīvu, kas mums jāšķiro [5,3,7,6,2,9].

Nosakiet pagrieziena elementu

Bet pirms turpināt ātro kārtošanu, galvenā loma ir pagrieziena elementa izvēlei. Ja kā pagrieziena elementu izvēlaties pirmo elementu, tas nodrošina sliktāko veiktspēju sakārtotajā masīvā. Tāpēc vienmēr ieteicams izvēlēties pagrieziena elementu vidējo elementu (masīva garums dalīts ar 2), un mēs darām to pašu.

Šeit ir norādītas darbības, lai veiktu ātro šķirošanu, kas tiek parādīta ar piemēru [5,3,7,6,2,9].

1. SOLIS: Nosakiet šarnīru kā vidējo elementu. Tātad, 7 ir pagrieziena elements.

2. SOLIS: Sāciet kreiso un labo rādītāju attiecīgi kā masīva pirmo un pēdējo elementu. Tātad kreisais rādītājs norāda uz 5 indeksā 0 un labais rādītājs norāda uz 9 indeksā 5.

3. SOLIS: Salīdziniet elementu kreisajā rādītājā ar pagrieziena elementu. Tā kā 5 <6 novirzīt kreiso rādītāju pa labi, lai indeksētu 1.

4. SOLIS: Tagad joprojām 3 <6, tāpēc pārvietojiet kreiso rādītāju uz vēl vienu rādītāju pa labi. Tātad tagad 7> 6 apstājas palielināt kreiso rādītāju, un tagad kreisais rādītājs atrodas 2. indeksā.

5. SOLIS: Tagad salīdziniet vērtību labajā rādītājā ar pagrieziena elementu. Tā kā 9> 6 pārvietojiet labo rādītāju pa kreisi. Tagad, kad 2 <6 pārtrauc labā rādītāja pārvietošanu.

6. SOLIS: Apmaini abas vērtības, kas atrodas kreisajā un labajā rādītājā, savā starpā.

7. SOLIS: Pārvietojiet abus rādītājus vēl par vienu soli.

8. SOLIS: Tā kā 6 = 6, pārvietojiet rādītājus vēl uz vienu soli un apstājieties, kad kreisais rādītājs šķērso labo rādītāju un atgriež kreisā rādītāja indeksu.

Tātad, pamatojoties uz iepriekš minēto pieeju, mums ir jāuzraksta kods elementu maiņai un masīva sadalīšanai, kā minēts iepriekšējās darbībās.

Kods, lai JavaScript apmainītu divus ciparus:

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

Kods nodalījuma veikšanai, kā minēts iepriekš minētajās darbībās:

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;}

Veiciet rekursīvo darbību

Kad būsiet veicis iepriekš minētās darbības, kreisā rādītāja indekss tiks atgriezts, un mums tas jāizmanto, lai sadalītu masīvu un veiktu ātro kārtošanu šajā daļā. Tādējādi to sauc par dalīšanas un iekarošanas algoritmu.

Tātad ātrā kārtošana tiek veikta, līdz tiek sakārtoti visi kreisā un labā masīva elementi.

Piezīme: Ātrā kārtošana tiek veikta tajā pašā masīvā, un procesā netiek izveidoti jauni masīvi.

Tātad, mums ir jāsauc šis nodalījums (), kas paskaidrots iepriekš, un, pamatojoties uz to, mēs sadalām masīvu daļās. Tātad šeit ir kods, kur jūs to izmantojat,

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);

Pilnīgs ātrās šķirošanas kods:

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]