Algoritmul de sortare cu bule a matricei unidimensionale pe c

Bună ziua, dragă oaspete. În acest articol voi discuta algoritmul de sortare a unei matrice folosind metoda bubble.

Elementele matricei, cum ar fi bulele

Algoritmul de sortare a bulei este un algoritm destul de simplu pentru sortarea matricelor. Puteți găsi și alte nume: sortarea bulelor. Sortarea sau sortarea bublelor prin schimburi simple - dar toate acestea vor face diferența între același algoritm. Este numit astfel, deoarece valoarea mai mare sau mai mică "plutește" (deplasare) spre marginea matricei după fiecare repetare, va fi văzută în exemplul respectiv.

Complexitatea acestui algoritm este exprimată prin formula O (n ^ 2) (n la puterea lui 2). Algoritmul rulează încet cu matrice mari și, prin urmare, este ineficient și este rar folosit în practică. cel mai adesea în scopuri educaționale. Pentru a sorta matricele în practică, utilizați alți algoritmi mai rapizi, dintre care unul este QuickSort (sortare rapidă). Funcția de sortare rapidă este inclusă în multe biblioteci standard de limbi de programare, de exemplu în funcția de limbă C qsort () din biblioteca standard.

Algoritmul funcționează foarte simplu. Programul trece prin toate elementele matricei în ordine. Fiecare element curent este comparat cu cel următor, iar dacă acesta este mai mic / mai mare (dacă ordonăm în ordine descrescătoare / în creștere), acesta schimbă locurile cu cel vecin.

Exemplu de lucru al algoritmului de sortare a bulei

Să luăm în considerare un exemplu de lucru al algoritmului cu o matrice formată din patru elemente.

Există o matrice [4, 5, 2, 6]. Sortați-l va fi în ordine descrescătoare.

N este numărul elementelor din matrice. i este numărul de trecere. Algoritmul va trece prin matrice, N-1 total va trece la celula N-i în fiecare iterație pentru orice matrice.

Prima trecere prin ciclu de la primul la elementul N-1, compararea cu condiția și inversarea în cazul satisfacerii condiției - dacă elementul stâng este mai mic decât cel din dreapta.

Comparați 4 și 5, 4 mai puțin de 5, ceea ce înseamnă că le schimbăm.

Comparați 4 și 2, 4 nu este mai mică de 2 și, prin urmare, sărim și mergem mai departe.

Comparați 2 și 6, 4 mai puțin de 6, ceea ce înseamnă că le schimbăm.

Acum avem o matrice [5, 4, 6, 2]. Se pare că nu este încă pe deplin comandat. După prima trecere de la sfârșitul matrice a mutat valoare foarte mică, acum trebuie să facem o altă trecere la N-2 (la urma urmei, este a doua iterație) element.

Facem un pasaj începând cu primul element.

Comparați 5 și 4, 5 nu este mai mic de 4 și, prin urmare, săriți și mergeți mai departe.

Comparați 6 și 4, 6 mai puțin de 4, ceea ce înseamnă că le schimbăm. Am ajuns la elementul N-2, terminăm iterația.

Acum avem o matrice [5, 6, 4, 2]. Ultimele două elemente sunt ordonate după cum este necesar. Pentru a finaliza, trebuie să completați încă o trecere la N-3.

Comparați 5 și 6, 5 mai puțin de 6, ceea ce înseamnă că le schimbăm. Am ajuns la elementul N-3, terminăm iterația.

Ca rezultat, la ieșire avem o ordine ordonată în ordine descrescătoare [6, 5, 4, 2].

Implementarea algoritmului în C ++

Programul va efectua următoarele acțiuni în ordine:

Setați dimensiunea matricei, solicitând utilizatorului să introducă o valoare numerică.
Completați matricea cu valorile introduse de utilizator pentru fiecare element al matricei.
Va imprima matricea originală.
Sortează matricele în ordine descrescătoare.
Afișează matricea sortată.

Acum, codul real pentru fiecare dintre elementele.

1. Declasați variabila și inițializați valoarea acesteia cu datele introduse de utilizator.

Fiți atenți. că în codul programului au fost folosite simbolurile rusești, dacă nu le afișați corect, apoi citiți articolul despre soluția problemei cu afișarea simbolurilor ruse în consola.

Scrierea programului este finalizată, acum vom verifica rezultatele. Și pentru aceasta introducem în program o matrice, sortarea pe care am produs-o, considerând un exemplu de algoritm care funcționează puțin mai sus în acest articol.

După introducerea datelor și executarea programului, am obținut rezultatul.

Rezultatul sortii unui matrice folosind metoda bubble

După cum puteți vedea în imagine, matricea este sortată în ordine descrescătoare. Programul funcționează.

Așa cum am menționat mai devreme, algoritmul este foarte lent, cu cantități mari de date, și, prin urmare, nepotrivit pentru utilizarea în practică, și este adecvat numai în formarea și scopuri educaționale. Uită-te la soluțiile de alte sarcini de programare.