Kas yra greitas rūšiavimas?
Greito rūšiavimo algoritmas vadovaujasi skirstymo ir užkariavimo metodu. Jis suskirsto elementus į mažesnes dalis pagal tam tikras sąlygas ir atlikdamas rūšiavimo operacijas toms padalytoms mažesnėms dalims.
„Quick Sort“ algoritmas yra vienas iš dažniausiai naudojamų ir populiariausių algoritmų bet kuria programavimo kalba. Bet jei esate „JavaScript“ kūrėjas, galite girdėti apie rūšiavimą (), kuris jau yra pasiekiamas „JavaScript“. Tada jūs galėjote pagalvoti, koks yra šio greito rūšiavimo algoritmo poreikis. Norėdami tai suprasti, pirmiausia reikia, kas yra rūšiavimas ir koks yra numatytasis „JavaScript“ rūšiavimas.
Kas yra rūšiavimas?
Rūšiavimas yra ne kas kita, kaip elementų išdėstymas norima tvarka. Galbūt su tuo susidūrėte savo mokyklos ar kolegijos dienomis. Panašiai kaip skaičių išdėstymas iš mažesnio į didesnį (didėjantį) arba iš didesnio į mažesnį (mažėjantį) yra tai, ką matėme iki šiol, ir vadinamas rūšiavimu.
Numatytasis rūšiavimas „JavaScript“
Kaip minėta anksčiau, „JavaScript“ turi rūšiavimą () . Paimkime pavyzdį su keliais elementų masyvais, tokiais kaip [5,3,7,6,2,9] ir norime rūšiuoti šį masyvo elementus didėjimo tvarka. Tiesiog iškvieskite elementų masyvo rūšiavimą () ir jis rūšiuoja masyvo elementus didėjimo tvarka.
Kodas:
var items = [5,3,7,6,2,9];console.log(items.sort());//prints [2, 3, 5, 6, 7, 9]
Kokia priežastis „JavaScript“ pasirinkti greitąjį rūšiavimą, o ne numatytąjį ()
Nors sort () duoda norimą rezultatą, problema kyla dėl to, kaip jis rūšiuoja masyvo elementus. Numatytasis „JavaScript“ rūšiavimas () naudoja įterpimo rūšiavimą pagal „Chrome“ V8 variklį ir „ Merge“ rūšiavimą pagal „ Mozilla Firefox“ ir „ Safari“ .
Bet, kita tai netinka, jei reikia rūšiuoti daug elementų. Taigi, sprendimas yra naudoti „Quick sort“ dideliam duomenų rinkiniui.
Taigi, norėdami visiškai suprasti, turite žinoti, kaip veikia „Quick sort“, ir leiskite mums tai išsamiai pamatyti dabar.
Kas yra greitas rūšiavimas?
Greitas rūšiavimas atliekamas pagal padalijimo ir užkariavimo algoritmą. Jis dalija elementus į mažesnes dalis pagal tam tikras sąlygas ir rūšiuoja operacijas toms dalytoms mažesnėms dalims. Taigi jis gerai veikia dideliems duomenų rinkiniams. Taigi, čia pateikiami žingsniai, kaip greitas rūšiavimas veikia paprastais žodžiais.
- Pirmiausia pasirinkite elementą, kuris bus vadinamas sukamuoju elementu.
- Tada palyginkite visus masyvo elementus su pasirinktu „pivot“ elementu ir išdėstykite juos taip, kad elementai, mažesni už „pivot“ elementą, būtų kairėje, o didesni nei „pivot“ - dešinėje.
- Galiausiai atlikite tas pačias operacijas kairiajame ir dešiniajame šoniniuose elementuose.
Taigi, tai yra pagrindinis greito rūšiavimo metodas. Štai veiksmai, kuriuos reikia atlikti po vieną, kad būtų atliktas greitas rūšiavimas.
Kaip veikia „QuickSort“
- Pirmiausia masyve raskite elementą „sukimasis“ .
- Pradėkite kairįjį rodyklę pirmajame masyvo elemente.
- Pradėkite dešinįjį rodyklę paskutiniame masyvo elemente.
- Palyginkite elementą, nukreipiantį į kairįjį rodyklę, ir, jei jis yra mažesnis nei sukamasis elementas, perkelkite kairįjį rodyklę į dešinę (pridėkite 1 prie kairiosios rodyklės). Tęskite tai tol, kol kairiosios pusės elementas bus didesnis arba lygus šarnyriniam elementui.
- Palyginkite elementą, nukreipiantį į dešinįjį rodyklę, ir, jei jis yra didesnis už pasisukimo elementą, tada perkelkite dešinįjį rodyklę į kairę (atimkite 1 į dešinę rodyklę). Tęskite tai tol, kol dešiniojo šono elementas bus mažesnis arba lygus šarnyriniam elementui.
- Patikrinkite, ar kairysis rodyklė yra mažesnė ar lygi dešiniajam, tada pamatykite elementus šių rodyklių vietose.
- Padidinkite kairįjį rodyklę ir dešinįjį rodyklę.
- Jei kairiojo rodyklės rodiklis vis dar mažesnis už dešiniojo rodyklės rodyklę, pakartokite procesą; Kitu atveju grąžins kairiosios rodyklės rodyklę.
Taigi, pažiūrėkime šiuos veiksmus su pavyzdžiu. Panagrinėkime elementų, kuriuos turime rūšiuoti, masyvą yra [5,3,7,6,2,9].
Nustatykite „Pivot“ elementą
Bet prieš einant su greito rūšiavimo funkcija, pagrindinį vaidmenį atlieka sukimo elemento pasirinkimas. Jei pasirenkate pirmąjį elementą kaip sukamą elementą, jis blogiausiai veikia rūšiuojamame masyve. Taigi, visada patariama kaip vidurinį elementą pasirinkti vidurinį elementą (masyvo ilgį padalijus iš 2) ir mes darome tą patį.
Čia pateikiami veiksmai, kaip atlikti greitą rūšiavimą, kuris rodomas su pavyzdžiu [5,3,7,6,2,9].
1 ŽINGSNIS: nustatykite šarnyrą kaip vidurinį elementą. Taigi, 7 yra pagrindinis elementas.
2 ŽINGSNIS: kairės ir dešinės rodykles pradėkite atitinkamai kaip pirmąjį ir paskutinį masyvo elementus. Taigi, liko rodyklė nukreipta į 5 metu indeksą 0 ir į dešinę rodyklė nukreipta į 9 nuo 5 indeksą.
3 ŽINGSNIS: Palyginkite kairiajame rodyklėje esantį elementą su pasukamuoju elementu. Nuo tada 5 <6 perkelia kairįjį rodyklę į dešinę 1 indeksui.
4 ŽINGSNIS: Dabar vis dar 3 <6, todėl perkelkite kairįjį rodyklę į dar vieną rodyklę dešinėje. Taigi dabar 7> 6 nustoja didinti kairįjį rodyklę, o kairysis rodyklė yra 2 rodyklėje.
5 ŽINGSNIS: Dabar palyginkite vertę dešinėje rodyklėje su sukamuoju elementu. Kadangi 9> 6, dešinįjį rodyklę perkelkite į kairę. Dabar, kai 2 <6 nustoja judinti dešinįjį rodyklę.
6 ŽINGSNIS: keiskite abi vertes, esančias kairiajame ir dešiniajame rodyklėse, tarpusavyje.
7 ŽINGSNIS: Perkelkite abu rodykles dar vienu žingsniu.
8 ŽINGSNIS: Kadangi 6 = 6, perkelkite rodykles į dar vieną žingsnį ir sustokite, kai kairysis rodyklė kerta dešinįjį rodyklę ir grąžina kairiosios rodyklės rodyklę.
Taigi, remdamiesi aukščiau pateiktu požiūriu, turime parašyti kodų keitimo ir masyvo skaidymo kodą, kaip minėta aukščiau.
Kodas, kad sukeistumėte du „JavaScript“ numerius:
function swap(items, leftIndex, rightIndex){var temp = items[leftIndex];items[leftIndex] = items[rightIndex];items[rightIndex] = temp;}
Kodas, skirtas atlikti skaidinį, kaip minėta aukščiau:
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;}
Atlikite rekursinę operaciją
Kai atliksite pirmiau nurodytus veiksmus, kairės žymeklio rodyklė bus grąžinta, ir mes turime ją naudoti, kad padalytume masyvą ir atliktume tos dalies greitąjį rūšiavimą. Vadinasi, jis vadinamas „Skaldyti ir užkariauti“ algoritmu.
Taigi, greitas rūšiavimas atliekamas tol, kol bus surūšiuoti visi kairio ir dešiniojo masyvo elementai.
Pastaba: greitas rūšiavimas atliekamas tame pačiame masyve ir procese nesukuriama naujų masyvų.
Taigi, turime iškviesti šį skaidinį (), paaiškintą aukščiau, ir, remdamiesi tuo, mes padalijame masyvą į dalis. Taigi čia yra kodas, kur jūs jį naudojate,
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);
Užbaigti greito rūšiavimo kodą:
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]
PASTABA: Greitas rūšiavimas vykdomas naudojant O sudėtingumą (nlogn).
