Astăzi vom vorbi despre un astfel de lucru aparent trivial ca sortarea. Foarte adesea puteți vedea că este învățat și predat, precum și subiectul recursivității, adică practic nu învățați și nu învățați :). Și în cărțile din seria "pentru ceainice" și, în general, în majoritatea cărților nu se acordă nici o atenție absolută niciunei probleme, deoarece totul are drept scop un efect rapid.
Se pare un lucru interesant, oamenii pot colecta structuri de baze de date complexe, pot folosi multi-șabloane și așa mai departe. dar sortarea, gestionarea cozilor, stive, matrice de date pentru ele este ceva arhisomatic. Mulți vor argumenta cu cele de mai sus, dar pot să vă întreb, ați văzut cum se utilizează sortarea atunci când programul se blochează? De exemplu, în contextul evoluțiilor slab dezvoltate, nu este ceva neobișnuit. Toată lumea sa obișnuit cu modele la nivel înalt, iar în unele cazuri oamenii folosesc metode pre-pregătite, deși structura lor internă este greu de imaginat. Între timp, trebuie cunoscute principiile de sortare, în special programatorii AI.
În general, viața arată lucruri interesante. La mijlocul anilor 90, când executam ordine, am stocat baze de date în fișiere text (cu sau fără delimitatori de simboluri), iar gestionarea acestei structuri a fost implementată datorită funcțiilor unei anumite limbi. Apoi m-am uitat atent la HTML, și am decis că etichetele html sunt foarte convenabile de utilizat ca delimitatori de caractere. Și numai în câțiva ani a existat un astfel de standard ca XML. Adică, gândurile s-au converg și se pare că am dezvoltat și am folosit tehnologia viitorului. Acum stochez baze de date în fișiere Lua executabile, care conțin nu numai datele în sine, ci și toate metodele care le pot fi aplicate, precum și structurile interdependente. Conținutul lor poate fi schimbat dinamic.
Crearea unei structuri de baze de date proprii și punerea în aplicare a unui sistem de management la toate nu este dificil de fapt, dar utilizatorii de calculatoare sunt obișnuiți să-și petreacă mult timp studiind și folosind tehnologii gata făcute.
Să vorbim despre sortare. Au fost dezvoltate multe modele algoritmice, adică tema a fost studiată temeinic, dar merită remarcat momentul în care trebuie să cunoașteți principiile de bază și, în fiecare caz în parte, puteți gestiona aceeași sortare.
Înainte de a rezolva întrebările de sortare, trebuie să știți cantitatea de date care trebuie procesată. Există metode care sunt cele mai eficiente cu un număr mic de elemente, dar ele devin destul de greoaie atunci când sunt mari. Există, de asemenea, metode speciale, dintre care una vom lua în considerare la sfârșitul materialului.
O metodă simplă - sortarea bulelor
Selectarea cu bule. a este matricea originală; b - al patrulea element "plutește" la suprafață.
Numele acestei metode este descriptiv, adică înseamnă un balon de aer plutitor pe suprafața apei. În principiu, aceasta este o comparație bună și ușor de înțeles.
Imaginați-vă o matrice întregă care constă, de exemplu, din cinci elemente. Trebuie să le aranjați în ordinea ascendentă a numerelor, adică datele [0] vor conține numărul minim și datele [4] maximul disponibil. Ce se întâmplă în cadrul acestui algoritm. Inițial, datele elementului superior [4] sunt comparate cu datele anterioare [3], iar dacă valoarea sa este mai mică, elementele sunt schimbate. Și așa mai departe, până când elementul minim apare ca un balon de aer. De fapt, tot ceea ce se spune va fi mai ușor de descris prin cod:
dacă (array [i-1]> array [j]) swap (array, i-1, j);
dimensiunea este dimensiunea matricei, dar în interiorul buclei, luăm valoarea dimensiunii-1 deoarece elementul maxim își ia poziția automată. Latura interioară pentru bucla trece în direcția opusă față de direcția exterioară, deși se poate face în direcția înainte.
Metoda de sortare a bulelor are un dezavantaj - un număr mare de acțiuni, adică este intensivă din punct de vedere al resurselor. În același timp, după ce ați analizat, puteți spune care este principala problemă - mișcarea elementelor într-o singură poziție.
O metodă simplă este sortarea selectivă
Sortare personalizată. Aceasta arată modul în care ultimul element al matricei schimbă locurile cu primul.
Este posibil să facem compararea elementului cu toate cele disponibile, iar atunci când condițiile sunt îndeplinite, acesta devine datele de poziție [0], făcând doar un singur schimb? Da, așa funcționează modul de selecție selectivă. Este o versiune îmbunătățită a bulei. Aceasta înseamnă că, inițial, valoarea minimă se găsește din întreaga matrice, indicele acesteia fiind determinat. După aceasta, datele [0] și datele [indexul valorii minime] se schimbă. Apoi este luată următoarea subarray, în care datele [0] nu mai sunt luate în considerare și umplem cu valoarea minimă a datelor [1] și așa mai departe.
În cod, acesta este un pic cam voluminoasă (pentru care mass-media IT de multe ori scold :)), deci să spunem că avem nevoie de o bucla internă, în care găsim valoarea indexului elementului care conține numărul minim și apoi facem o permutare. Apoi efectuăm aceeași căutare în subarray și așa mai departe, care se face în bucla exterioară. În acest caz, codul este optimizat prin restricția că permutarea este efectuată în cazul în care elementul permutabil nu conține valoarea minimă, adică dacă (min_index! = I).
Metoda complexă - sortarea rapidă
Sortarea rapidă este una dintre metodele cele mai eficiente și, în esență, acestea sunt două tipuri interdependente. Metoda constă în faptul că gama de ales orice element care va acționa ca o valoare de separare. Separarea (!) - înseamnă că se va separa. Și ce anume? De fapt, se înțelege traficul în două sensuri de la începutul matrice și sfârșitul acesteia, în terminologia mai ușor de utilizat șefului nume (cap) și coadă (de coadă). Asta este, dacă vorbim despre balanța numerelor în ordine crescătoare, algoritmul de sortare în capul va compara numerele cu condiția> împărțirea valorii (dacă este „da“, atunci aceasta este o mare schimbări de valoare cu partajare), iar coada algoritmul de sortare va compara numărul de pe condiția <разделяющего значения (если «да», то это большое значение меняется с разделяющим). В момент когда Head и Tail сходится на одном элементе (место пересечения указателей), мы можем сказать, что все что справа (или ниже) меньше разделяющего значения, а все, что слева(сверху) — больше.
Apoi, aceste două părți sunt sortate separat în același mod (funcția de sortare se recurge în mod recursiv).
Sortarea rapidă. Ca valoare de separare, 3 (valoarea cea mai din stânga) este selectată. Coada, ajungând la o unitate (b) întâlnește condiția "valoarea curentă <разделяющего», Происходит обмен. Потом идет проверка со стороны Head, так как ситуация изменилась, указатели пересекаются на элементе массива a[2]. Следующим этапом будет идентичная обработка правой и левой частей.
Un algoritm rapid este adesea însoțit de fraza: "divide și cuceri". Acest lucru este valabil, dar depinde foarte mult de alegerea elementului / valorii de separare. De exemplu, o matrice care conține -3,5,0,7,2. Încercați să alegeți valoarea pe care va oferi sortarea cea mai rapidă (cel mai convenabil pentru primul ciclu de sortare va fi 0 sau 2) și cel mai lent (în cazul în care primul ciclu de sortare selectați ca separarea valoarea maximă sau minimă, adică, -3 sau 7 ). Cea mai avantajoasă situație va fi și atunci când matricea este împărțită în două părți egale.
De asemenea, dacă vă uitați atent, veți observa că, în unele cazuri, sortarea rapidă nu câștigă în comparație cu metodele simple despre care am scris. Și cel mai mare dezavantaj este atunci când aplicăm o sortare rapidă unei serii deja sortate.
În general, există mai multe metode de sortare rapidă, diferența principală constând în algoritmul de selectare a valorii de separare (procedura de partiționare), optimizarea recursului.
Sortarea rapidă are încă un merus minus - care intră în infinit. Adică, matricea 3,2,3 va conduce la o situație critică, deoarece este necesară procedura de procesare a valorilor repetate, care nu este prevăzută în algoritmii standard.
O metodă sofisticată este îmbunătățită pentru sortarea rapidă
Îmbunătățirea sorții rapide se potrivește mai bine cu selecția valorii de separare. Este necesar să se determine mediana matricei, adică valoarea medie în spectrul global. Definiția sa este destul de costisitoare, dar cu cât mai multe valori trebuie să procesați, cu atât este mai bine echilibrul resurselor.
Pentru a determina valoarea mediană, de obicei, există o valoare medie între cele două elemente extreme și medii. Pentru a rezolva situația cu valori repetate, există o procedură specială care folosește construcțiile de ...<=… или …>= ...) sau pur și simplu a jucat situația în cazul egalității.
O metodă complexă este sortarea fuziunii
Sortarea îmbinării înseamnă funcția de sortare prin împărțirea matricei într-o jumătate - în două subarraje, după ce funcția de sortare se recurge recursiv pentru fiecare jumătate și apoi combină subarrajele sortate într-un singur matrice. Toate lucrările de sortare se efectuează pe măsură ce stivele de apeluri sunt dezactivate. Pentru a opera algoritmul, aveți nevoie de o matrice temporară suplimentară de aceeași dimensiune ca cea originală, care este apoi copiată la cea principală.
Sortarea prin îmbinare este mai bună decât o îmbunătățire rapidă de sortare datorită simplității (fără elemente de divizare și traversare a indicatoarelor) și nu are cea mai proastă problemă care poate apărea atunci când se sortează rapid.
O metodă sofisticată este "sortarea discretă"
În memoria mea, am întâlnit-o de câteva ori. Cu toate acestea, el a avut nevoie de mine, așa că am dezvoltat-o eu însumi. În esență, acest algoritm funcționează ca ... ADC și câțiva alți algoritmi bine-cunoscuți. Aceasta este, inițial, valorile maxime și minime sunt căutate în matrice. Apoi se calculează media acestora, adică intervalul de valori de / 2. După aceea, toate elementele sunt comparate cu această valoare și cele care mai sunt introduse pe partea stângă, cele mai multe - la dreapta. Se creează o matrice temporară de aceeași dimensiune ca originalul, în care elementele sunt plasate pe stânga sunt indicii, pornind de la zero, iar cei care au rămas - cu [numărul total de e-ing - indicele curent pentru partea dreaptă].
Apoi, (pentru fiecare dintre cele două jumătăți, am văzut mediile lor variază de 1/4 și 3/4 din intervalul de valori, precum și numărul de elemente din fiecare jumătate), vom oferi, de asemenea o comparație cu valorile medii ale jumătate, și așa mai departe, până când vom ajunge la un element. Apoi, există un ansamblu cu dispunerea adecvată a indicilor. "Sortarea discretă", precum și sortarea fuzionării necesită prezența unei matrice suplimentare, adică, așa cum se spune, nu este efectuată "în poziție".
Să nu spunem că algoritmul de sortare discret este laborios în execuție, deși există și variante complexe de execuție. El este de încredere, dar suficient de resurse. Ei bine, aplicabile cazurilor matrice neuniforme în care există „goale“, adică, de exemplu, intervalul de la 0 la 100, iar valorile în vrac ale elementelor sunt concentrate în intervalul 80-90. În general, farmecul principal al discrete de sortare și metodele sale este prezentată în cazurile în care este necesar să se monitorizeze valorile rotunde pentru anumite zone reaprovizionate dinamic matrice și așa mai departe.
După cum puteți vedea, nimic special nu a fost inventat în procesul de sortare. Trebuie doar să te uiți atent. Algoritmii înșiși sunt destul de bine facilitați în condiții când sunteți bine familiarizați cu structura internă a problemei. De exemplu, în cazul în care, în general, un anumit algoritm este descris ca resursă-solicitante și eliminarea erorilor în privat, poate fi cel mai eficient atunci când constrângerile corespunzătoare de aliniere.
În următoarea parte a materialului, vom vorbi despre stiva și recursiunea, optimizând recursiunea.
Articole similare
-
Pături de lână de oaie descriere a calităților, producători populare, produse foto
-
Semnificația sensului tatuaj țintă, istoric, fotografie, schițe, fapte, desene populare în modern
Trimiteți-le prietenilor: