bubble sort c with examples
Tehnică de sortare cu bule în C ++.
Bubble Sort este cea mai simplă dintre tehnicile de sortare.
În tehnica sortării cu bule, fiecare dintre elementele din listă este comparat cu elementul său adiacent. Astfel, dacă există n elemente în lista A, atunci A (0) este comparat cu A (1), A (1) este comparat cu A (2) și așa mai departe.
După compararea dacă primul element este mai mare decât al doilea, cele două elemente sunt schimbate atunci.
=> Vizitați aici pentru cursul complet C ++ de la experți.
Ce veți învăța:
ce este o listă legată c ++
- Tehnica de sortare cu bule
- Ilustrare
- Exemplu C ++
- Exemplu Java
- Analiza complexității algoritmului de sortare cu bule
- Concluzie
- Lectură recomandată
Tehnica de sortare cu bule
Folosind tehnica sortării cu bule, sortarea se face în treceri sau iterație. Astfel, la sfârșitul fiecărei iterații, cel mai greu element este plasat la locul potrivit din listă. Cu alte cuvinte, cel mai mare element din listă se ridică.
Am dat mai jos un algoritm general al tehnicii sortării cu bule.
Algoritm general
Pasul 1 : Pentru i = 0 la N-1 repetați Pasul 2
Pasul 2 : Pentru J = i + 1 la N - repet
Pasul 3 : dacă A (J)> A (i)
Schimbați A (J) și A (i)
(Sfârșitul buclei interioare pentru buclă)
(Încheie dacă Outer for loop)
Pasul 4 : Ieșire
Iată un pseudo-cod pentru algoritmul de sortare cu bule, în care traversăm lista folosind două bucle iterative.
În prima buclă, începem de la 0aelement și în bucla următoare, pornim de la un element adiacent. În corpul buclei interioare, comparăm fiecare dintre elementele adiacente și le schimbăm dacă nu sunt în ordine. La sfârșitul fiecărei iterații a buclei exterioare, cel mai greu element se ridică la sfârșit.
Pseudo cod
Procedure bubble_sort (array , N) array – list of items to be sorted N – size of array begin swapped = false repeat for I = 1 to N-1 if array(i-1) > array(i) then swap array(i-1) and array(i) swapped = true end if end for until not swapped end procedureCele de mai sus sunt pseudo-codul pentru tehnica sortării cu bule. Să ilustrăm acum această tehnică folosind o ilustrare detaliată.
Ilustrare
Luăm o matrice de mărimea 5 și ilustrăm algoritmul sortării cu bule.
Tablou complet sortat.
Ilustrația de mai sus poate fi rezumată într-o formă tabelară așa cum se arată mai jos:
| Trece | Listă nesortată | comparaţie | Listă sortată |
|---|---|---|---|
| {5,0,10,12,15} | {10.12} | {5,0,10,12,15} | |
| 1 | {10,5,15,0,12} | {10.5} | {5,10,15,0,12} |
| {5,10,15,0,12} | {10.15} | {5,10,15,0,12} | |
| {5,10,15,0,12} | {15.0} | {5,10,0,15,12} | |
| {5,10,0,15,12} | {15.12} | {5,10,0,12,15} | |
| Două | {5,10,0,12,15} | {5,10} | {5,10,0,12,15} |
| {5,10,0,12,15} | {10.0} | {5,0,10,12,15} | |
| 3 | {5,0,10,12,15} | {5,0} | {0,5,10,12,15} |
| {5,0,10,12,15} | {5,10} | {5,0,10,12,15} | |
| {5,0,10,12,15} | SORTAT |
Așa cum se arată în ilustrație, cu fiecare trecere, cel mai mare element bulele până la ultima sortând astfel lista cu fiecare trecere. După cum s-a menționat în introducere, fiecare element este comparat cu elementul său adiacent și schimbat unul cu altul dacă nu sunt în ordine.
Astfel, așa cum se arată în ilustrația de mai sus, la sfârșitul primei treceri, dacă matricea urmează să fie sortată în ordine crescătoare, cel mai mare element este plasat la sfârșitul listei. Pentru a doua trecere, al doilea element ca mărime este plasat la a doua poziție din listă și așa mai departe.
Când ajungem la N-1 (unde N este un număr total de elemente din listă) trece, vom avea întreaga listă sortată.
întrebări și răspunsuri la interviuri în baze de date pdf
Tehnica sortării cu bule poate fi implementată în orice limbaj de programare. Am implementat algoritmul de sortare a bulelor folosind limbajul C ++ și Java de mai jos.
Exemplu C ++
Să vedem un exemplu de programare pentru a demonstra sortarea cu bule.
#include using namespace std; int main () { int i, j,temp,pass=0; int a(10) = {10,2,0,14,43,25,18,1,5,45}; cout <<'Input list ...
'; for(i = 0; i<10; i++) { cout < Ieșire:
Lista de introducere ...
10 2 0 14 43 25 18 1 5 45
Lista elementelor sortate ...
0 1 2 5 10 14 18 25 43 45
Numărul de treceri luate pentru a sorta lista: 10
Exemplu Java
class Main { public static void main(String() args) { int pass = 0; int() a = {10,-2,0,14,43,25,18,1,5,45}; System.out.println('Input List...'); for(int i=0;i<10;i++) { System.out.print(a(i) + ' '); } for(int i=0;i<10;i++) { for (int j=0;j<10;j++) { if(a(i) Ieșire:
În ambele programe, am folosit o serie de 10 elemente și le sortăm folosind tehnica sortării cu bule. În ambele programe, am folosit două bucle pentru a itera prin elementele adiacente ale matricei.
La sfârșitul fiecărei treceri (bucla exterioară), cel mai mare element din matrice este barbotat până la sfârșitul matricei. De asemenea, numărăm numărul de treceri necesare pentru a sorta întreaga matrice.
Analiza complexității algoritmului de sortare cu bule
Din pseudo-cod și din ilustrația pe care am văzut-o mai sus, în sortare cu bule, facem comparații N-1 în prima trecere, comparații N-2 în a doua trecere și așa mai departe.
Prin urmare, numărul total de comparații în sortarea cu bule este:
I = (n-1) + (n-2) + (n-3) + ... + 3 + 2 + 1
= N (N-1) / 2
= O (nDouă) => Complexitatea în timp a tehnicii sortării cu bule
Astfel, diversele complexități pentru tehnica sortării cu bule sunt date mai jos:
Complexitatea timpului cel mai prost O (n 2) Complexitatea în cel mai bun caz Pe) Complexitatea timpului mediu O (n 2) Complexitatea spațiului O (1)
Tehnica sortării cu bule necesită doar un singur spațiu de memorie suplimentar pentru variabila temp pentru a facilita schimbul. Prin urmare, complexitatea spațiului pentru algoritmul de sortare a bulelor este O (1).
Rețineți că cea mai bună complexitate de timp pentru tehnica sortării cu bule va fi atunci când lista este deja sortată și va fi O (n).
Concluzie
Principalul avantaj al Bubble Sort este simplitatea algoritmului. În sortare cu bule, la fiecare trecere, cel mai mare element se bule până la sfârșitul listei dacă matricea este sortată în ordine crescătoare.
În mod similar, pentru ca lista să fie sortată în ordine descrescătoare, cel mai mic element va fi la locul potrivit la sfârșitul fiecărei treceri.
Fiind cea mai simplă și ușor de implementat tehnica de sortare, sortarea cu bule este de obicei luată pentru introducerea sortării pentru public. În al doilea rând, sortarea cu bule este, de asemenea, utilizată în aplicații precum grafica computerizată în care umplerea marginilor poligonului etc. necesită sortarea cu bule pentru a sorta vârfurile care acoperă poligonul.
În viitorul nostru tutorial, vom afla în detaliu despre Sortarea selecției.
=> Vizitați aici pentru a afla C ++ de la zero.
cum să vizualizați fișiere XML în word
Lectură recomandată
