Convenția la jumătate
Când numărul de elemente dintr-o listă este egal, înjumătățirea listei înseamnă prima jumătate literală a listei este prima jumătate, iar a doua jumătate literală a listei este a doua jumătate. Elementul mijlociu (mijlociu) al întregii liste este ultimul element al primei liste. Aceasta înseamnă că indicele de mijloc este lungimea / 2 - 1, deoarece numărarea indexului începe de la zero. Lungimea este numărul de elemente din listă. De exemplu, dacă numărul de elemente este 8, atunci prima jumătate a listei are 4 elemente, iar a doua jumătate a listei are și 4 elemente. Asta este bine. Deoarece numărarea indexului începe de la 0, indicele din mijloc este 3 = 8/2 - 1.
Cum rămâne cu cazul, când numărul de elemente din listă sau sub-listă este impar? La început, lungimea este încă împărțită la 2. Prin convenție, numărul elementelor din prima jumătate a acestei diviziuni este lungimea / 2 + 1/2. Numărarea indexului începe de la zero. Indicele de mijloc este dat de lungimea / 2 - 1/2. Acesta este considerat ca termen mediu, prin convenție. De exemplu, dacă numărul elementelor dintr-o listă este 5, atunci indicele din mijloc este 2 = 5/2 - 1/2. Și, există trei elemente în prima jumătate a listei și două elemente în a doua jumătate. Elementul de mijloc al întregii liste este al treilea element la index, 2, care este indexul de mijloc, deoarece numărarea indexului începe de la 0.
Împărțirea în acest mod este un exemplu de aritmetică întreagă.
Mediana celor trei valori
Întrebare: Care este mediana secvenței:
C B A
Soluţie:
Aranjați lista în ordine crescătoare:
A B C
Termenul mediu, B, este mediana. Este magnitudinea care se află între celelalte două magnitudini.
Căutarea medianei într-o listă nu este de acest fel. De exemplu, într-o listă de 19 elemente nesortate, poate fi necesară mediana pentru primul element, elementul de mijloc și ultimul element. Este posibil ca aceste trei valori să nu fie în ordine crescătoare; deci, indicii lor trebuie luați în considerare.
Cu Sortare rapidă, este necesară mediana pentru întreaga listă și sub-liste. Pseudocodul pentru a căuta mediana a trei valori distanțate într-o listă (matrice) este:
mijloc: =⌊(scăzut+înalt) / 2⌋dacăarr[mijloc] <arr[scăzut]
swap arr[scăzut]cu arr[mijloc]
dacăarr[înalt] <arr[scăzut]
swap arr[scăzut]cu arr[înalt]
dacăarr[mijloc] <arr[înalt]
swap arr[mijloc]cu arr[înalt]
pivot: =arr[înalt]
Termenul arr înseamnă matrice. Acest segment de cod caută mediana și, de asemenea, face o anumită sortare. Acest segment de cod arată simplu, dar poate fi destul de confuz. Deci, acordați atenție următoarei explicații:
Sortarea din acest tutorial va produce o listă în care prima valoare este cea mai mică valoare, iar ultima valoare este cea mai mare valoare. Cu alfabetul, A este mai mic decât Z.
Aici, pivotul este mediana rezultată. Low este cel mai mic indice al listei sau al sub-listei (nu neapărat pentru cea mai mică valoare); high este cel mai mare indice al listei sau al sub-listei (nu neapărat pentru cea mai mare valoare), iar mijlocul este indicele convențional mediu (nu neapărat pentru valoarea medie a întregii liste).
Deci, mediana care trebuie obținută este între valoarea celui mai mic indice, valoarea indicelui mediu și valoarea celui mai mare indice.
În cod, se obține mai întâi indicele convențional de mijloc. La acest început, lista este nesortată. Comparația și o anumită rearanjare în ordine crescătoare a celor trei valori trebuie să aibă loc în același timp. Prima afirmație if compară valoarea pentru cel mai mic indice și cea a indicelui de mijloc. Dacă cel al indicelui de mijloc este mai mic decât cel al celui mai mic indice, atunci cele două valori schimbă pozițiile. Aceasta începe sortarea și schimbă dispunerea valorilor în listă sau sub-listă. A doua afirmație if compară valoarea pentru cel mai mare indice și cea a celui mai mic indice. Dacă cel al celui mai mare indice este mai mic decât cel al celui mai mic indice, cele două valori schimbă pozițiile. Acest lucru duce la o anumită sortare și schimbare a aranjamentului valorilor în listă sau sub-listă. A treia afirmație if compară valoarea indicelui de mijloc și cea a celui mai mare indice. Dacă cel al celui mai mare indice este mai mic decât indicele din mijloc, cele două valori schimbă pozițiile. Unele sortări sau rearanjări pot apărea și aici. Această a treia condiție if nu este ca cele două precedente.
La sfârșitul acestor trei swap-uri, valoarea medie a celor trei valori în cauză ar fi A [mare], al cărei conținut original ar fi putut fi modificat în segmentul de cod. De exemplu, luați în considerare secvența nesortată:
C B A
Știm deja că mediana este B. Cu toate acestea, acest lucru ar trebui dovedit. Scopul aici este de a obține mediana acestor trei valori folosind segmentul de cod de mai sus. Prima afirmație if compară B și C. Dacă B este mai mic decât C, atunci pozițiile lui B și C trebuie schimbate. B este mai mic decât C, astfel încât noul aranjament devine:
B C A
Observați, valorile pentru cel mai mic indice și cel mediu au fost modificate. A doua afirmație if compară A și B. Dacă A este mai mic decât B, atunci pozițiile lui A și B trebuie schimbate. A este mai mic decât B, astfel încât noul aranjament devine:
A C B
Observați, valorile pentru cel mai mare indice și cel mai mic indice s-au schimbat. A treia afirmație if compară C și B. Dacă C este mai mic decât B, atunci pozițiile lui C și B trebuie schimbate. C nu este mai mic decât B, deci nu are loc nici o schimbare. Noul aranjament rămâne ca cel anterior, adică:
A C B
B este mediana, adică A [înaltă] și este pivotul. Deci, pivotul se naște la capătul extrem al listei sau al sub-listei.
Funcția de schimbare
O altă caracteristică necesară Sortării rapide este funcția de schimbare. Funcția de schimb, schimbă valorile a două variabile. Pseudocodul pentru funcția de schimb este:
definiți swap(X,și)temp: =X
X: =și
și: =temp
Aici, x și y se referă la valorile reale și nu la copii.
Sortarea din acest articol va produce o listă în care prima valoare este cea mai mică valoare, iar ultima valoare este cea mai mare valoare.
Conținutul articolului
- Algoritm de sortare rapidă
- Un pseudocod de partiție
- Ilustrarea sortării rapide
- Codare Java
- Concluzie
Algoritm de sortare rapidă
Modul normal de sortare a unei liste nesortate este de a lua în considerare primele două valori. Dacă nu sunt în ordine, puneți-le în ordine. Apoi, ia în considerare primele trei valori. Scanați primele două pentru a vedea unde se potrivește a treia valoare și potriviți-o corespunzător. Apoi, ia în considerare primele patru valori. Scanați primele trei valori pentru a vedea unde se potrivește a patra valoare și potriviți-o corespunzător. Continuați cu această procedură până când se ordonează întreaga listă.
Această procedură, cunoscută și sub denumirea de forță brută, în limbajul programării computerelor, este prea lentă. Algoritmul Sortare rapidă vine cu o procedură mult mai rapidă.
Pașii pentru algoritmul quicksort sunt după cum urmează:
- Asigurați-vă că există cel puțin 2 numere de sortat în lista nesortată.
- Obțineți o valoare centrală estimată pentru listă, numită pivot. Mediana, așa cum a fost descris mai sus, este o modalitate de a obține pivotul. Diferite moduri vin cu avantajele și dezavantajele lor. - Ne vedem mai tarziu.
- Împărțiți lista. Aceasta înseamnă, plasați pivotul în listă. În acest fel, toate elementele din stânga sunt mai mici decât valoarea pivotului și toate elementele din dreapta sunt mai mari sau egale cu valoarea pivotului. Există diferite moduri de partiționare. Fiecare metodă de partiție vine cu avantajele și dezavantajele sale. Împărțirea înseamnă împărțirea în paradigma divizării și cuceririi.
- Repetați pașii 1, 2 și 3 recursiv pentru noile perechi de sub-liste care apar până când se ordonează întreaga listă. Acest lucru este cuceritor în paradigma divizează și cucerește.
Pseudocodul Sortare rapidă este:
algoritm rapid(arr,scăzut,înalt)estedacăscăzut<mare atunci
pivot(scăzut,înalt)
p: =partiție(arr,scăzut,înalt)
sortare rapida(arr,scăzut,p- 1)
sortare rapida(arr,p+ 1,înalt)
Un pseudocod de partiție
Pseudocodul de partiție utilizat în acest tutorial este:
partiție algoritmică(arr,scăzut,înalt)estepivot: =arr[înalt]
eu: =scăzut
j: =înalt
do
do
++eu
in timp ce(arr[eu] <pivot)
do
-j
in timp ce(arr[j] >pivot)
dacă (eu<j)
swap arr[eu]cu arr[j]
in timp ce(eu<j)
swap arr[eu]cu arr[înalt]
întoarcereeu
În ilustrația Sortare rapidă de mai jos, acest cod este utilizat:
Ilustrarea sortării rapide
Luați în considerare următoarea listă (matrice) nesortate de litere alfabetice:
Q W E R T Y U I O P
Prin inspecție, lista sortată este:
E I O P Q R T U W Y
Lista sortată va fi acum dovedită, folosind algoritmul de mai sus și segmentele de pseudocod, din lista nesortată:
Q W E R T Y U I O P
Primul pivot este determinat din arr [0] = Q, arr [4] = T și arr [9] = P și este identificat ca Q și plasat în extrema dreaptă a listei. Deci, lista cu orice sortare a funcției pivot devine:
P W E R T Y U I O Q
Pivotul actual este Q. Procedura pivotului a făcut o sortare mică și a plasat P în prima poziție. Lista rezultată trebuie să fie rearanjată (partiționată), astfel încât, toate elementele din stânga să aibă o valoare mai mică, atunci pivotul și toate elementele din dreapta pivotului sunt egale sau mai mari decât pivotul. Computerul nu poate face partiționare prin inspecție. Așa se întâmplă folosind indicii și algoritmul de partiție de mai sus.
Indicii mici și mari sunt acum 0 și 9. Deci, computerul va începe prin scanarea din index 0 până când ajunge la un index, a cărui valoare este egală sau mai mare decât pivotul și se oprește temporar acolo. De asemenea, va scana de la capătul superior (dreapta), index 9, coborând, până când ajunge la un index a cărui valoare este mai mică sau egală cu pivotul și se oprește temporar acolo. Aceasta înseamnă două poziții de oprire. Dacă i, variabila indexului incremental, de la scăzut nu este încă egală cu sau mai mare decât variabila index descrescătoare, j de la mare, atunci aceste două valori sunt schimbate. În situația actuală, scanarea de la ambele capete s-a oprit la W și O. Deci lista devine:
P O E R T Y U I W Q
Pivotul este încă Q. Scanarea în direcții opuse continuă și se oprește în consecință. Dacă i nu este încă egal sau mai mare decât j, atunci cele două valori la care scanarea de la ambele capete s-au oprit sunt schimbate. De data aceasta, scanarea de la ambele capete s-a oprit la R și I. Deci, dispunerea listei devine:
P O E I T Y U R W Q
Pivotul este încă Q. Scanarea în direcții opuse continuă și se oprește în consecință. Dacă i nu este încă egal sau mai mare decât j, atunci cele două valori la care s-a oprit scanarea sunt schimbate. De data aceasta, scanarea de la ambele capete s-a oprit la T pentru i și I pentru j. i și j ne-am întâlnit sau am trecut. Deci, nu poate exista schimb. Lista rămâne aceeași ca:
P O E I T Y U R W Q
În acest moment, pivotul, Q, trebuie plasat în poziția sa finală în sortare. Acest lucru se face schimbând arr [i] cu arr [high], schimbând T și Q. Lista devine:
P O E I Q Y U R W T
În acest moment, partiționarea pentru întreaga listă sa încheiat. Pivotul = Q și-a jucat rolul. Acum există trei sub-liste, care sunt:
P O E I Q Y U R W T
Partiția este împărțirea și cucerirea (sortarea) în paradigmă. Q se află în poziția corectă de sortare. Fiecare element din stânga lui Q este mai mic decât Q și fiecare element din dreapta lui Q este mai mare decât Q. Cu toate acestea, lista din stânga nu este încă sortată; iar lista corectă încă nu este sortată. Întreaga funcție de sortare rapidă trebuie apelată recursiv pentru a sorta sub-lista din stânga și sub-lista din dreapta. Această amintire a sortării rapide trebuie să continue; se vor dezvolta noi sub-liste până când întreaga listă originală este complet sortată. Pentru fiecare reamintire a funcției de sortare rapidă, sub-lista din stânga este luată în considerare mai întâi înainte de a fi luată în considerare sub-lista din dreapta corespunzătoare. Trebuie obținut un nou pivot pentru fiecare sub-listă.
Pentru sub-listă:
P O E I
Pivotul (mediana) pentru P, O și I este determinat. Pivotul ar fi O. Pentru această sub-listă și în legătură cu lista completă, noul arr [low] este arr [0], iar noul arr [high] este ultimul arr [i-1] = arr [ 4-1] = arr [3], unde i este indicele pivot final din partiția anterioară. După ce a fost apelată funcția pivot (), noua valoare pivot, pivot = O. Nu confundați între funcția pivot și valoarea pivot. Funcția pivot poate face o sortare mică și pune pivotul în extrema dreaptă a sub-listei. Această sub-listă devine,
I P E O
Cu această schemă, pivotul se termină întotdeauna la capătul drept al sub-listei sau listei după apelul de funcție. Scanarea de la ambele capete începe de la arr [0] și arr [3] până când i și j se întâlnesc sau se încrucișează. Comparația se face cu pivot = O. Primele opriri sunt la P și E. Sunt schimbate, iar noua sub-listă devine:
I E P O
Scanarea de la ambele capete continuă, iar noile opriri sunt la P pentru i și la E pentru j. Acum eu și j ne-am întâlnit sau ne-am întâlnit. Deci, sub-lista rămâne aceeași cu:
I E P O
Partiționarea unei sub-liste sau liste se încheie când pivotul a fost pus în poziția sa finală. Deci, noile valori pentru arr [i] și arr [high] sunt schimbate. Adică, P și O sunt schimbate. Noua sub-listă devine:
I E O P
O este acum la poziția sa finală pentru întreaga listă. Rolul său de pivot s-a încheiat. Sub-lista este în prezent partiționată în alte trei liste, care sunt:
I E O P
În acest moment, trebuie sortată Sortarea rapidă a primei sub-liste din dreapta. Cu toate acestea, nu va fi chemat. În schimb, va fi notat și rezervat, pentru a fi numit mai târziu. Întrucât declarațiile funcției de partiționare erau în curs de executare, din partea de sus a funcției, Sortarea rapidă pentru sub-lista din stânga trebuie chemată acum (după ce pivotul () a fost apelat). Va fi apelat pentru listă:
Eu E
Va începe prin a căuta mediana lui I și E. Aici, arr [low] = I, arr [mid] = I și arr [high] = E. Deci, mediana, pivot, ar trebui să fie determinată de algoritmul pivot ca , I. Cu toate acestea, pseudocodul pivot de mai sus va determina pivotul ca E. Această eroare apare aici deoarece pseudocodul de mai sus este destinat pentru trei elemente și nu pentru două. În implementarea de mai jos, există o anumită ajustare a codului. Sub-lista devine,
E eu
Pivotul se termină întotdeauna la capătul din dreapta al sub-listei sau listei după apelul de funcție. Scanarea de la ambele capete începe de la arr [0] și arr [1] exclusiv până când i și j se întâlnesc sau se încrucișează. Comparația se face cu pivot = I. Primele și singurele opriri sunt la I și E: la I pentru i și la E pentru j. Acum eu și j ne-am întâlnit sau am trecut. Deci, sub-lista rămâne aceeași ca:
E eu
Partiționarea unei sub-liste sau liste se încheie când pivotul a fost pus în poziția sa finală. Deci, noile valori pentru arr [i] și arr [high] sunt schimbate. Se întâmplă aici că arr [i] = I și arr [high] = I. Deci, aceeași valoare este schimbată cu ea însăși. Noua sub-listă devine:
E eu
Acum sunt la poziția sa finală pentru întreaga listă. Rolul său de pivot s-a încheiat. Sub-lista este acum partiționată în încă două liste, care sunt,
E eu
Acum, pivotii de până acum au fost Q, O și I. Pivotii ajung la pozițiile lor finale. O listă secundară a unui singur element, cum ar fi P de mai sus, se termină, de asemenea, în poziția sa finală.
În acest moment, prima listă secundară din stânga a fost complet sortată. Și procedura de sortare este acum la:
E I O P Q Y U R W T
Prima sub-listă dreaptă:
Y U R W T
încă trebuie să fie sortat.
Cucerirea primei sub-liste din dreapta
Amintiți-vă că apelul de sortare rapidă pentru prima listă secundară din dreapta a fost notat și rezervat în loc să fie executat. În acest moment, va fi executat. Astfel, noul arr [low] = arr [5] = arr [QPivotIndex + 1], iar noul arr [high] rămâne arr [9]. Un set similar de activități care s-au întâmplat pentru prima listă secundară din stânga se va întâmpla aici. Și această primă sub-listă dreaptă este sortată după cum urmează:
R T U W Y
Și lista originală nesortată a fost sortată în:
E I O P Q R T U W Y
Codare Java
Punerea algoritmului în Java este doar pentru a pune toate segmentele de pseudocod de mai sus în metodele Java într-o singură clasă. Nu uitați că trebuie să existe o metodă main () în clasă care va apela funcția quicksort () cu matricea nesortată.
Metoda pivot ()
Metoda Java pivot () care returnează valoarea, pivot, ar trebui să fie:
nulpivot(chararr[], intscăzut, intînalt) {intmijloc= (scăzut+înalt) / 2;
dacă (arr[mijloc] <arr[scăzut])
swap(arr,scăzut,mijloc);
dacă (arr[înalt] <arr[scăzut])
swap(arr,scăzut,înalt);
dacă ((înalt-scăzut) > 2) {
dacă (arr[mijloc] <arr[înalt])
swap(arr,mijloc,înalt);
}
}
Metoda swap ()
Metoda swap () ar trebui să fie:
nulswap(chararr[], intX, intși) {chartemp=arr[X];
arr[X] =arr[și];
arr[și] =temp;
}
Metoda quicksort ()
Metoda quicksort () ar trebui să fie:
nulsortare rapida(chararr[], intscăzut, intînalt) {dacă (scăzut<înalt) {
pivot(arr,scăzut,înalt);
intp=partiție(arr,scăzut,înalt);
sortare rapida(arr,scăzut,p- 1);
sortare rapida(arr,p+ 1,înalt);
}
}
Metoda partiție ()
Metoda partition () ar trebui să fie:
intpartiție(chararr[], intscăzut, intînalt) {charpivot=arr[înalt];
inteu=scăzut;
intj=înalt;
do {
do
++eu;
in timp ce(arr[eu] <pivot);
do
-j;
in timp ce(arr[j] >pivot);
dacă (eu<j)
swap(arr,eu,j);
}in timp ce(eu<j);
swap(arr,eu,înalt);
întoarcereeu;
}
Metoda principală ()
Metoda principală () poate fi:
publicstatic nulprincipal(Şir[]argumente) {chararr[] = {„Q”, 'ÎN', 'ȘI', „R”, „T”, 'ȘI', „U”, „Eu”, 'SAU', „P”};
TheClass QuickSort= nouClasa();
Sortare rapida.sortare rapida(arr, 0, 9);
Sistem.afară.println(„Elementele sortate:”);
pentru(inteu=0;eu<10;eu++) {
Sistem.afară.imprimare(arr[eu]);Sistem.afară.imprimare('');
}
Sistem.afară.println();
}
Toate metodele de mai sus pot fi încadrate într-o singură clasă.
Concluzie
Sortarea rapidă este un algoritm de sortare care folosește paradigma împărțire și cucerire. Începe prin împărțirea unei liste nesortate în două sau trei sub-liste. În acest tutorial, Sortare rapidă a împărțit o listă în trei sub-liste: o sub-listă din stânga, o listă de mijloc a unui singur element și o sub-listă din dreapta. Cucerirea în Sortare rapidă înseamnă împărțirea unei liste sau sub-liste în timp ce o sortați, folosind o valoare pivot. Acest tutorial a explicat o implementare a Sortării rapide în limbajul computerului Java.
Despre autor
Crizanth Forcha
Descoperitor al integrării matematice din primele principii și serii conexe. Master în educație tehnică, specializată în electronică și software de calculator. BSc Electronics. De asemenea, am cunoștințe și experiență la nivel de masterat în informatică și telecomunicații. Din 20.000 de scriitori, am fost al 37-lea cel mai bun scriitor de la devarticles.com. Lucrez în aceste domenii de mai bine de 10 ani.
Vezi toate postărilePOSTURI DE LUCRU LINUX
- Compararea șirurilor în Java
- Cum se folosește HashMap în Java
- S-a explicat sortarea rapidă în Java
- Binar Preorder Traversal în Java
- Merge Sort în Java explicat
- Cum se utilizează scanerul în Java
- Scriere Java în fișier