Introducere în algoritmul de sortare cu bule

Sortarea este una dintre cele mai simple operații pe care le puteți aplica datelor. Puteți sorta elemente în diferite limbaje de programare folosind diferiți algoritmi de sortare, cum ar fi Sortare rapidă, Sortare cu bule, Sortare Merge, Sortare prin inserție etc. Bubble Sort este cel mai simplu algoritm dintre toate acestea.

În acest articol, veți afla despre funcționarea algoritmului Bubble Sort, pseudocodul Bubble Sort algoritmul, complexitatea sa de timp și spațiu și implementarea sa în diferite limbaje de programare precum C ++, Python, C și JavaScript.

Cum funcționează algoritmul de sortare cu bule?

Bubble Sort este cel mai simplu algoritm de sortare care parcurge în mod repetat lista, compară elementele adiacente și le schimbă dacă sunt în ordinea greșită. Acest concept poate fi explicat mai eficient cu ajutorul unui exemplu. Luați în considerare o matrice nesortată cu următoarele elemente: {16, 12, 15, 13, 19}.

Exemplu:

Aici sunt comparate elementele adiacente și dacă nu sunt în ordine crescătoare, sunt schimbate.

Pseudocodul algoritmului de sortare cu bule

În pseudocod, algoritmul Bubble Sort poate fi exprimat ca:

bubbleSort (Arr [], dimensiune)
// bucla pentru a accesa fiecare element matrice
pentru i = 0 până la mărimea-1 faceți:
// bucla pentru a compara elementele matricei
pentru j = 0 până la mărimea-i-1 faceți:
// comparați elementele adiacente
dacă Arr [j]> Arr [j + 1] atunci
// schimbă-le
swap (Arr [j], Arr [j + 1])
incheie daca
sfârșit pentru
sfârșit pentru
Sfârșit

Algoritmul de mai sus procesează toate comparațiile, chiar dacă matricea este deja sortată. Poate fi optimizat în continuare prin oprirea algoritmului dacă bucla interioară nu a provocat niciun schimb. Acest lucru va reduce timpul de execuție al algoritmului.

Astfel, pseudocodul algoritmului optimizat de sortare a bulelor poate fi exprimat ca:

bubbleSort (Arr [], dimensiune)
// bucla pentru a accesa fiecare element matrice
pentru i = 0 până la mărimea-1 faceți:
// verificați dacă are loc schimbarea
swapped = false
// bucla pentru a compara elementele matricei
pentru j = 0 până la mărimea-i-1 faceți:
// comparați elementele adiacente
dacă Arr [j]> Arr [j + 1] atunci
// schimbă-le
swap (Arr [j], Arr [j + 1])
swapped = adevărat
incheie daca
sfârșit pentru
// dacă nu au fost schimbate elemente, înseamnă că matricea este sortată acum, atunci rupeți bucla.
dacă (nu se schimbă) atunci
pauză
incheie daca
sfârșit pentru
Sfârșit

Complexitatea timpului și spațiul auxiliar al algoritmului de sortare a bulelor

Cea mai gravă situație de timp a algoritmului de sortare a bulelor este O (n ^ 2). Apare atunci când matricea este în ordine descrescătoare și doriți să o sortați în ordine crescătoare sau invers.

Complexitatea în cel mai bun caz al algoritmului de sortare a bulelor este O (n). Apare atunci când matricea este deja sortată.

Legate de: Ce este notația Big-O?

Complexitatea timpului mediu al cazului algoritmului de sortare a bulelor este O (n ^ 2). Apare atunci când elementele matricei sunt în ordine confuză.

Spațiul auxiliar necesar algoritmului de sortare cu bule este O (1).

C ++ Implementarea algoritmului Bubble Sort

Mai jos este implementarea C ++ a algoritmului Bubble Sort:

// Implementarea C ++ a
// algoritm optimizat de sortare a bulelor
#include 
folosind spațiul de nume std;
// Funcția de efectuare a sortării cu bule
void bubbleSort (int arr [], int size) {
// Buclați pentru a accesa fiecare element al matricei
pentru (int i = 0; i // Variabilă pentru a verifica dacă are loc schimbarea
bool swapped = false;
// bucla pentru a compara două elemente adiacente ale matricei
pentru (int j = 0; j // Compararea a două elemente matrice adiacente
if (arr [j]> arr [j + 1]) {
// Schimbați ambele elemente dacă sunt
// nu în ordine corectă
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
swapped = adevărat;
}
}
// Dacă nu au fost schimbate elemente, înseamnă că matricea este sortată acum,
// apoi rupeți bucla.
if (swapped == false) {
pauză;
}
}
}
// Tipărește elementele matricei
void printArray (int arr [], dimensiunea int) {
pentru (int i = 0; i cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Găsirea lungimii matricei
int size = sizeof (arr) / sizeof (arr [0]);
// Imprimarea matricei nesortate date
cout << "Unsorted Array:" << endl;
printArray (arr, dimensiune);
// Apelarea funcției bubbleSort ()
bubbleSort (arr, dimensiune);
// Imprimarea matricei sortate
cout << "Matrice sortate în ordine crescătoare:" << endl;
printArray (arr, dimensiune);
retur 0;
}

Ieșire:

Matrice nesortate: 
16 12 15 13 19 
Matricea sortată în ordine crescătoare:
12 13 15 16 19

Implementarea Python a algoritmului de sortare cu bule

Mai jos este implementarea Python a algoritmului Bubble Sort:

# Implementarea Python a
# algoritm optimizat de sortare a bulelor
# Funcția de efectuare a sortării cu bule
def bubbleSort (arr, dimensiune):
# Buclă pentru a accesa fiecare element al listei
pentru i în interval (dimensiunea-1):
# Variabilă pentru a verifica dacă are loc schimbarea
swapped = Fals
# buclă pentru a compara două elemente adiacente ale listei
pentru j în interval (dimensiunea-i-1):
# Comparând două elemente de listă adiacente
dacă arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = temp
swapped = Adevărat
# Dacă nu au fost schimbate elemente, înseamnă că lista este sortată acum,
# apoi rupeți bucla.
dacă este schimbat == False:
pauză
# Tipărește elementele listei
def printArray (arr):
pentru element în ar:
print (element, end = "")
imprimare("")
arr = [16, 12, 15, 13, 19]
# Găsirea lungimii listei
size = len (arr)
# Tipărirea listei nesortate date
print ("Listă nesortată:")
printArray (arr)
# Apelarea funcției bubbleSort ()
bubbleSort (arr, dimensiune)
# Tipărirea listei sortate
print ("Lista sortată în ordine crescătoare:")
printArray (arr)

Ieșire:

Lista nesortată:
16 12 15 13 19 
Lista sortată în ordine crescătoare:
12 13 15 16 19

Legate de: Cum se folosește buclele în Python

C Implementarea algoritmului Bubble Sort

Mai jos este implementarea C a algoritmului Bubble Sort:

// C implementarea
// algoritm optimizat de sortare a bulelor
#include 
#include 
// Funcția de efectuare a sortării cu bule
void bubbleSort (int arr [], int size) {
// Buclați pentru a accesa fiecare element al matricei
pentru (int i = 0; i // Variabilă pentru a verifica dacă are loc schimbarea
bool swapped = false;
// bucla pentru a compara două elemente adiacente ale matricei
pentru (int j = 0; j // Compararea a două elemente matrice adiacente
if (arr [j]> arr [j + 1]) {
// Schimbați ambele elemente dacă sunt
// nu în ordine corectă
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
swapped = adevărat;
}
}
// Dacă nu au fost schimbate elemente, înseamnă că matricea este sortată acum,
// apoi rupeți bucla.
if (swapped == false) {
pauză;
}
}
}
// Tipărește elementele matricei
void printArray (int arr [], dimensiunea int) {
pentru (int i = 0; i printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// Găsirea lungimii matricei
int size = sizeof (arr) / sizeof (arr [0]);
// Imprimarea matricei nesortate date
printf ("Unsorted Array: \ ⁠n");
printArray (arr, dimensiune);
// Apelarea funcției bubbleSort ()
bubbleSort (arr, dimensiune);
// Imprimarea matricei sortate
printf ("Matricea sortată în ordine crescătoare: \ ⁠n");
printArray (arr, dimensiune);
retur 0;
}

Ieșire:

Matrice nesortate: 
16 12 15 13 19 
Matricea sortată în ordine crescătoare: 
12 13 15 16 19

Implementarea JavaScript a algoritmului Bubble Sort

Mai jos este implementarea JavaScript a algoritmului Bubble Sort:

// Implementarea JavaScript a
// algoritm optimizat de sortare a bulelor
// Funcția de efectuare a sortării cu bule
funcție bubbleSort (arr, dimensiune) {
// Buclați pentru a accesa fiecare element al matricei
pentru (să i = 0; eu// Variabilă pentru a verifica dacă are loc schimbarea
var swapped = false;
// bucla pentru a compara două elemente adiacente ale matricei
pentru (fie j = 0; j// Compararea a două elemente matrice adiacente
if (arr [j]> arr [j + 1]) {
// Schimbați ambele elemente dacă sunt
// nu în ordine corectă
let temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
swapped = adevărat;
}
// Dacă nu au fost schimbate elemente, înseamnă că matricea este sortată acum,
// apoi rupeți bucla.
if (swapped == false) {
pauză;
}
}
}
}
// Tipărește elementele matricei
funcție printArray (arr, dimensiune) {
pentru (să i = 0; eudocument.write (arr [i] + "");
}
document.write („
")
}
var arr = [16, 12, 15, 13, 19];
// Găsirea lungimii matricei
var size = arr.length;
// Imprimarea matricei nesortate date
document.write ("Matrice nesortată: 
");
printArray (arr, dimensiune);
// Apelarea funcției bubbleSort ()
bubbleSort (arr, dimensiune);
// Imprimarea matricei sortate
document.write ("Matricea sortată în ordine crescătoare: 
");
printArray (arr, dimensiune);

Ieșire:

Matrice nesortate:
16 12 15 13 19
Matricea sortată în ordine crescătoare:
12 15 13 16 19

Acum înțelegeți funcționarea algoritmului de sortare cu bule

Bubble Sort este cel mai simplu algoritm de sortare și este utilizat în principal pentru a înțelege bazele sortării. Bubble Sort poate fi, de asemenea, implementat recursiv, dar nu oferă avantaje suplimentare în acest sens.

Folosind Python, puteți implementa algoritmul Bubble Sort cu ușurință. Dacă nu sunteți familiarizați cu Python și doriți să începeți călătoria, începeți cu un script „Hello World” este o alegere excelentă.

Cum să începeți cu Python folosind un script „Hello World”

Python este unul dintre cele mai populare limbaje de programare utilizate astăzi. Urmați acest tutorial pentru a începe cu primul dvs. script Python.

Citiți în continuare

Despre autor