logo

TechCodeview

Bubble Sort – Tutoriale privind structura datelor și algoritmi

Sortare cu bule este cel mai simplu algoritm de sortare care funcționează prin schimbarea în mod repetat a elementelor adiacente dacă acestea sunt în ordinea greșită. Acest algoritm nu este potrivit pentru seturi mari de date, deoarece complexitatea sa medie și în cel mai rău caz este destul de mare.

Algoritmul de sortare cu bule

În algoritmul de sortare cu bule,

  • traversați din stânga și comparați elementele adiacente, iar cel mai înalt este plasat în partea dreaptă.
  • În acest fel, cel mai mare element este deplasat la capătul din dreapta la început.
  • Acest proces este apoi continuat pentru a găsi al doilea ca mărime și plasați-l și așa mai departe până când datele sunt sortate.
Practică recomandată Bubble Sort Încercați!

Cum funcționează sortarea cu bule?

Să înțelegem funcționarea sortării cu bule cu ajutorul următoarei ilustrații:



Intrare: arr[] = {6, 0, 3, 5}

Prima trecere:

Cel mai mare element este plasat în poziția sa corectă, adică capătul matricei.

Algoritmul de sortare cu bule: Plasarea celui mai mare element în poziția corectă

înlocuirea metodei în java

A doua trecere:

Așezați al doilea element ca mărime în poziția corectă

Algoritmul de sortare cu bule: Plasarea celui de-al doilea element ca mărime în poziția corectă

A treia trecere:

Așezați cele două elemente rămase în pozițiile lor corecte.

Algoritmul de sortare cu bule: plasarea elementelor rămase în pozițiile lor corecte

harta in java
  • Nr total. de treceri: n-1
  • Nr total. de comparatii: n*(n-1)/2

Implementarea Bubble Sort

Mai jos este implementarea sortării cu bule. Poate fi optimizat prin oprirea algoritmului dacă bucla interioară nu a provocat nicio schimbare.

C++ 
// Optimized implementation of Bubble sort #include  using namespace std; // An optimized version of Bubble Sort void bubbleSort(int arr[], int n) {  int i, j;  bool swapped;  for (i = 0; i < n - 1; i++) {  swapped = false;  for (j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { swap(arr[j], arr[j + 1]);  schimbat = adevărat;  } } // Dacă nu au fost schimbate două elemente // prin bucla interioară, atunci break if (swapped == false) break;  } } // Funcție de tipărire a unui tablou void printArray(int arr[], int size) { int i;  pentru (i = 0; i< size; i++)  cout << ' ' << arr[i]; } // Driver program to test above functions int main() {  int arr[] = { 64, 34, 25, 12, 22, 11, 90 };  int N = sizeof(arr) / sizeof(arr[0]);  bubbleSort(arr, N);  cout << 'Sorted array: 
';  printArray(arr, N);  return 0; } // This code is contributed by shivanisinghss2110>
C 
// Optimized implementation of Bubble sort #include  #include  void swap(int* xp, int* yp) {  int temp = *xp;  *xp = *yp;  *yp = temp; } // An optimized version of Bubble Sort void bubbleSort(int arr[], int n) {  int i, j;  bool swapped;  for (i = 0; i < n - 1; i++) {  swapped = false;  for (j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { swap(&arr[j], &arr[j + 1]);  schimbat = adevărat;  } } // Dacă nu au fost schimbate două elemente prin bucla interioară, // atunci break if (swapped == false) break;  } } // Funcție de tipărire a unui tablou void printArray(int arr[], int size) { int i;  pentru (i = 0; i< size; i++)  printf('%d ', arr[i]); } // Driver program to test above functions int main() {  int arr[] = { 64, 34, 25, 12, 22, 11, 90 };  int n = sizeof(arr) / sizeof(arr[0]);  bubbleSort(arr, n);  printf('Sorted array: 
');  printArray(arr, n);  return 0; }>
Java 
// Optimized java implementation of Bubble sort import java.io.*; class GFG {    // An optimized version of Bubble Sort  static void bubbleSort(int arr[], int n)  {  int i, j, temp;  boolean swapped;  for (i = 0; i < n - 1; i++) {  swapped = false;  for (j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { // Schimbați arr[j] și arr[j+1] temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = temp;  schimbat = adevărat;  } } // Dacă nu au fost // schimbate două elemente prin bucla interioară, atunci break if (swapped == false) break;  } } // Funcție de tipărire a unui tablou static void printArray(int arr[], int size) { int i;  pentru (i = 0; i< size; i++)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver program  public static void main(String args[])  {  int arr[] = { 64, 34, 25, 12, 22, 11, 90 };  int n = arr.length;  bubbleSort(arr, n);  System.out.println('Sorted array: ');  printArray(arr, n);  } } // This code is contributed // by Nikita Tiwari.>
Python3 
# Optimized Python program for implementation of Bubble Sort def bubbleSort(arr): n = len(arr) # Traverse through all array elements for i in range(n): swapped = False # Last i elements are already in place for j in range(0, n-i-1): # Traverse the array from 0 to n-i-1 # Swap if the element found is greater # than the next element if arr[j]>arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] swapped = Adevărat dacă (schimbat == Fals): sparge # Codul șoferului de testat mai sus dacă __name__ == '__main__': arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print('Matrice sortată:') pentru i în interval(len(arr)): print('%d' % arr[i], end=' ') # Acest cod este modificat de Suraj krushna Yadav>
C# 
// Optimized C# implementation of Bubble sort using System; class GFG {  // An optimized version of Bubble Sort  static void bubbleSort(int[] arr, int n)  {  int i, j, temp;  bool swapped;  for (i = 0; i < n - 1; i++) {  swapped = false;  for (j = 0; j < n - i - 1; j++) {  if (arr[j]>arr[j + 1]) { // Schimbați arr[j] și arr[j+1] temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = temp;  schimbat = adevărat;  } } // Dacă nu au fost // schimbate două elemente prin bucla interioară, atunci break if (swapped == false) break;  } } // Funcție de tipărire a unui tablou static void printArray(int[] arr, int size) { int i;  pentru (i = 0; i< size; i++)  Console.Write(arr[i] + ' ');  Console.WriteLine();  }  // Driver method  public static void Main()  {  int[] arr = { 64, 34, 25, 12, 22, 11, 90 };  int n = arr.Length;  bubbleSort(arr, n);  Console.WriteLine('Sorted array:');  printArray(arr, n);  } } // This code is contributed by Sam007>
Javascript 
// Optimized javaScript implementation // of Bubble sort // An optimized version of Bubble Sort function bubbleSort(arr, n) {  var i, j, temp;  var swapped;  for (i = 0; i < n - 1; i++)   {  swapped = false;  for (j = 0; j < n - i - 1; j++)   {  if (arr[j]>arr[j + 1]) { // Schimbați arr[j] și arr[j+1] temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = temp;  schimbat = adevărat;  } } // DACĂ nu au fost // schimbate două elemente prin bucla interioară, atunci break if (swapped == false) break;  } } // Funcție pentru a tipări o funcție matrice printArray(arr, size) { var i;  pentru (i = 0; i< size; i++)  console.log(arr[i] + ' '); } // Driver program var arr = [ 64, 34, 25, 12, 22, 11, 90 ]; var n = arr.length; bubbleSort(arr, n); console.log('Sorted array: '); printArray(arr, n); // This code is contributed shivanisinghss2110>
PHP 
 // PHP Optimized implementation // of Bubble sort // An optimized version of Bubble Sort function bubbleSort(&$arr) { $n = sizeof($arr); // Traverse through all array elements for($i = 0; $i < $n; $i++) { $swapped = False; // Last i elements are already // in place for ($j = 0; $j < $n - $i - 1; $j++) { // Traverse the array from 0 to // n-i-1. Swap if the element  // found is greater than the // next element if ($arr[$j]>$arr[$j+1]) { $t = $arr[$j]; $arr[$j] = $arr[$j+1]; $arr[$j+1] = $t; $swapped = Adevărat; } } // Dacă nu au fost schimbate două elemente // prin bucla interioară, atunci break if ($swapped == False) break; } } // Cod driver $arr = array(64, 34, 25, 12, 22, 11, 90); $len = dimensiunea($arr); bubbleSort($arr); echo 'Matrice sortată: 
'; pentru($i = 0; $i< $len; $i++) echo $arr[$i].' '; // This code is contributed by ChitraNayal. ?>>>>  
  Ieșire      Complexitatea timpului:    PE2)  
    Spațiu auxiliar:    O(1)
 
    Avantajele sortării cu bule:    
  • Sortarea cu bule este ușor de înțeles și implementat.
  • Nu necesită spațiu de memorie suplimentar.
  • Este un algoritm de sortare stabil, ceea ce înseamnă că elementele cu aceeași valoare cheie își mențin ordinea relativă în rezultatul sortat.
    Dezavantajele sortării cu bule:    
  • Sortarea cu bule are o complexitate de timp de O(N2), ceea ce o face foarte lent pentru seturi mari de date.
  • Sortarea cu bule este un algoritm de sortare bazat pe comparație, ceea ce înseamnă că necesită un operator de comparație pentru a determina ordinea relativă a elementelor din setul de date de intrare. Poate limita eficiența algoritmului în anumite cazuri.
Câteva întrebări frecvente legate de sortarea cu bule:
    Ce este cazul limită pentru sortarea cu bule?     
Sortarea cu bule durează minim (Ordinea lui n) când elementele sunt deja sortate. Prin urmare, cel mai bine este să verificați dacă matricea este deja sortată sau nu în prealabil, pentru a evita O(N2) complexitatea timpului.
 
Sortarea are loc în sortarea cu bule?
Da, Bubble sort realizează schimbarea perechilor adiacente fără a utiliza nicio structură de date majoră. Prin urmare, algoritmul de sortare cu bule este un algoritm pe loc.
 
Este algoritmul de sortare cu bule stabil?
Da, algoritmul de sortare cu bule este stabil.
 
Unde este folosit algoritmul de sortare cu bule?
Datorită simplității sale, sortarea cu bule este adesea folosită pentru a introduce conceptul de algoritm de sortare. În grafica computerizată, este popular pentru capacitatea sa de a detecta o eroare mică (cum ar fi un schimb de doar două elemente) în matrice aproape sortate și de a o remedia doar cu o complexitate liniară (2n).
 
Exemplu: este utilizat într-un algoritm de umplere a poligonului, în care liniile de delimitare sunt sortate după coordonatele lor x la o linie de scanare specifică (o linie paralelă cu axa x) și, cu creșterea y, ordinea lor se modifică (două elemente sunt schimbate) numai la intersecțiile a două linii.
 
    Articole similare:     
 
  •  Sortare recursiv cu bule 
  •  Practică de codificare pentru sortare 
  •  Test pentru sortarea cu bule 
  •  Analiza complexității sortării cu bule