Colectarea în baloane a matricei unidimensionale: algoritm, cod de program în limba C

În lucrul cu informațiile, cele mai profitabile modalități de stocare a acestora sunt structurile și tablourile. Acesta din urmă poate conține orice date de tip unic, care este convenabil de utilizat în activitatea programului. Acestea sunt adesea folosite în activitatea magazinelor online și în dezvoltarea jocurilor. Prin urmare, datele conținute în ele sunt sortate și schimbate în mod repetat și se efectuează operații logice sau matematice. O modalitate de a aduce ordinea la matrice este sortarea bulelor. Această publicație va studia codul său C și logica permutărilor.

Array Algoritmul de sortare

Dificultățile tehnice pentru programator nu sunt o sortare cu bule a unei matrice unidimensionale, deși este folosită destul de rar datorită eficienței sale scăzute. Este mai des considerat în stadiul de formare ca cel mai simplu. Cu toate acestea, este departe de a fi cel mai eficient. Algoritmul său constă în compararea alternativă a cifrelor și a suprapunerii celulelor în cazul în care condiția este îndeplinită.

Descrierea de sortare pas cu pas

La prima repetare, două numere adiacente sunt comparate treptat. Dacă stânga este mai mare, atunci este rescrisă în locurile cu cea dreaptă. Minusurile 8 și 0 nu satisfac condițiile. De aceea nu se schimbă în locuri. Zero și 5, de asemenea, nu se potrivesc. 5 și 3 sunt potrivite. Cu toate acestea, la această iterație, cadrul de citire nu se încadrează în topul cinci, ci se schimbă spre dreapta, de la 5 înainte ca acesta să fie comparat cu zero. Aceasta înseamnă că următoarea pereche este interschimbat - 3 și 9. În plus, toate cititor de înlocuire este invitat să revizuiască propria lor, fără comentarii ale autorului și studia algoritmul de sortare cu bule.

Ca urmare a tuturor iterațiilor, matricea este sortată treptat, iar acest lucru este în esență cazul în care: numerele pozitive mari se mișcă repede spre dreapta, în timp ce cele mai mici și cele negative sunt ușor rearanjate spre stânga. Se pare că bulele de gaz dintr-un lichid se ridică rapid. Din cauza acestei analogii, algoritmul a fost numit sortarea bulelor.

Estimarea complexității computaționale

Algoritmul ideal de sortare ar trebui să fie cât mai rapid posibil. În același timp, ar trebui să ia o cantitate mică de resurse CPU și de memorie. Și un astfel de proces ca o sortare a unui șir de baloane nu poate fi cea mai eficientă din punct de vedere energetic și profitabilă. Din cauza aplicării largi, nu a găsit-o. Dacă există mai puține probleme cu memoria în momentul respectiv, atunci resursele procesorului ar trebui să fie îngrijorate. Dat fiind că matricele digitale nu pot fi doar mari, dar uriașe, atunci consumul de resurse informatice va fi imprevizibil.

În cazul în genul balon, în principiu, pentru a face față rapid lucrurile în ordine într-o matrice relativ mică, cea mai mare poate fi intreruperi din cauza cheltuielile în exces a resurselor. Aceasta înseamnă că proprietatea universală inerentă algoritmului va fi încălcată. și sortarea bulei are o complexitate N-pătrat și este foarte departe de logaritmul complexității N. În plus, riscul de eșec în procesarea unei matrice mari crește șansele de pierdere a datelor datorită suprascrierii celulelor. Mai mult profitabil în această privință va fi sortarea inserției sau algoritmul Shell.

Codul de software

Codul computerului pentru limbajul C de mai jos în aplicația grafică vă permite să efectuați sortarea bulelor. Este redat ca o funcție separată de tipul void. Nu returnează nici o valoare, dar folosind indicii swap elementele în funcție de condițiile de sortare. În acest caz, codul rezolvă problema sortării cu bule a unei serii de numere întregi în ordine ascendentă.

Pentru a efectua această funcție, utilizatorul trebuie să creeze o matrice, care trebuie umplută cu valorile necesare. Acest lucru se poate face manual, prin setarea dimensiunii și a numărului de elemente la începutul programului. Apoi puteți umple matricea cu valori constante. A doua opțiune este de a crea un program universal prin declararea unei serii mari de dimensiuni unice de 100 de elemente.

Declarația și inițializarea unui tablou

Prin specificarea unei variabile întregi și atribuirea acesteia unei valori citite de la tastatură, puteți limita numărul de celule care vor fi completate. De asemenea, puteți implementa funcția de introducere a elementelor dintr-o matrice de către utilizator din tastatură folosind funcția scanf ("% d", " valoare). În acest exemplu, "% d" este un șir de modificare care îi spune compilatorului că va primi o valoare întregă după scanare. Valoarea variabilă va stoca o valoare care este dimensiunea unei serii întregi unidimensionale.

Pentru a utiliza algoritmul de sortare, trebuie să treci numele matricei și dimensiunea acesteia la funcție. În situația prezentată în aplicația grafică, apelul către funcția de sortare va arăta astfel: BubleSort (dataArray, sizeDataArray). Desigur, la sfârșitul liniei după funcție, ar trebui să puneți punct și virgulă în loc de o perioadă, așa cum se cere de regulile de sintaxă ale programului. Deci, dataArray este numele matricei pe care doriți să o sortați și sizeDataArray este dimensiunea sa.

Transmiterea acestor parametri la funcția BubleSort () va determina efectuarea operațiilor cu sizeDataArray în loc să folosească sizeArray, așa cum se vede în figură, într-un program real. Acest lucru înseamnă, de asemenea, că funcția BubleSort () va folosi un întreg dataArray. În mod similar, funcția printArrayFunction () și ArrayIntegerInputFunction () sunt numite. Primul este responsabil pentru imprimare, adică pentru ieșirea în consola elementelor. Și a doua este necesară pentru ao umple cu elemente introduse de utilizator de la tastatură.

Acest stil de programare, atunci când operațiile izolate sunt redate sub formă de funcții, mărește semnificativ lizibilitatea codului și accelerează dezvoltarea lui. Într-un astfel de program, matricea este completat separat de tastatură, tipărit și cu bule de sortare. Acesta din urmă poate fi utilizat pentru a organiza datele sau ca o funcție secundară proiectată pentru a găsi minimul și maximul matricei.

Introducerea sortimentului

În sortare prin inserție, se presupune că fiecare element este comparat la rândul său și este construit un lanț de elemente deja sortate în funcție de condiție. Ca rezultat, rezultatul fiecărei comparații ulterioare este căutarea unei celule în care poate fi plasată o nouă valoare. Dar introducerea fiecăruia dintre ele se face în partea deja sortată a matricei.

O astfel de prelucrare este mai rapidă și are o complexitate computațională mai mică. Codul C este prezentat în aplicația grafică.

Este, de asemenea, redat ca o funcție în care numele matricei care urmează a fi ordonată și dimensiunea matricei sunt transmise ca argumente. Aici puteți vedea cât de încet este sortarea bulelor. Inserțiile de lucru similare sunt mult mai rapide și au un cod compact.