logo

TechCodeview

Bubble Sort – Tietorakenteen ja algoritmin opetusohjelmat

Kuplalajittelu on yksinkertaisin lajittelualgoritmi joka toimii vaihtamalla toistuvasti vierekkäisiä elementtejä, jos ne ovat väärässä järjestyksessä. Tämä algoritmi ei sovellu suurille tietojoukoille, koska sen keskimääräinen ja pahimmassa tapauksessa aika monimutkaisuus on melko korkea.

Kuplalajittelualgoritmi

Bubble Sort -algoritmissa

  • poikki vasemmalta ja vertaa vierekkäisiä elementtejä ja korkeampi sijoitetaan oikealle puolelle.
  • Tällä tavalla suurin elementti siirretään aluksi oikeanpuoleiseen päähän.
  • Tätä prosessia jatketaan sitten toiseksi suurimman löytämiseksi ja sen sijoittamiseksi ja niin edelleen, kunnes tiedot on lajiteltu.
Suositeltu harjoituskuplalajittelu Kokeile sitä!

Miten kuplalajittelu toimii?

Ymmärrämme kuplalajittelun toimintaa seuraavan kuvan avulla:



Syöte: arr[] = {6, 0, 3, 5}

Ensimmäinen passi:

Suurin elementti sijoitetaan oikeaan paikkaansa, eli taulukon loppuun.

Bubble Sort Algorithm: Suurimman elementin sijoittaminen oikeaan paikkaan

Toinen passi:

Aseta toiseksi suurin elementti oikeaan kohtaan

Bubble Sort Algorithm : Toiseksi suurimman elementin sijoittaminen oikeaan paikkaan

Kolmas passi:

Aseta loput kaksi elementtiä oikeille paikoilleen.

Bubble Sort Algorithm : Sijoita muut elementit oikeisiin paikkoihinsa

kulmikas materiaali
  • Yhteensä nro passeista: n-1
  • Yhteensä nro vertailuista: n*(n-1)/2

Bubble Sort -sovelluksen käyttöönotto

Alla on kuplalajittelun toteutus. Se voidaan optimoida pysäyttämällä algoritmi, jos sisäsilmukka ei aiheuttanut vaihtoa.

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]);  vaihdettu = tosi;  } } // Jos kahta elementtiä ei vaihdettu // sisäisellä silmukalla, niin break if (vaihdettu == false) break;  } } // Toiminto taulukon tulostamiseksi void printArray(int arr[], int size) { int i;  for (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]);  vaihdettu = tosi;  } } // Jos kahta elementtiä ei vaihdettu sisäsilmukalla, // sitten break if (vaihdettu == false) break;  } } // Toiminto taulukon tulostamiseksi void printArray(int arr[], int size) { int i;  for (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]) { // Vaihda arr[j] ja arr[j+1] temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = lämpötila;  vaihdettu = tosi;  } } // Jos kahta elementtiä ei // vaihdettu sisäsilmukalla, niin break if (vaihdettu == false) break;  } } // Toiminto taulukon tulostamiseksi staattinen void printArray(int arr[], int size) { int i;  for (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.>
Python 3 
# 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 = Tosi, jos (vaihdettu == Epätosi): tauko # Ohjainkoodi testattavaksi yllä, jos __nimi__ == '__main__': arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print('Sorted array:') for i in range(len(arr)): print('%d' % arr[i], end=' ') # Tätä koodia on muokannut 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]) { // Vaihda arr[j] ja arr[j+1] temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = lämpötila;  vaihdettu = tosi;  } } // Jos kahta elementtiä ei // vaihdettu sisäsilmukalla, niin break if (vaihdettu == false) break;  } } // Toiminto taulukon tulostamiseksi staattinen void printArray(int[] arr, int size) { int i;  for (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]) { // Vaihda arr[j] ja arr[j+1] temp = arr[j];  arr[j] = arr[j + 1];  arr[j + 1] = lämpötila;  vaihdettu = tosi;  } } // JOS kahta elementtiä ei // vaihdettu sisäsilmukalla, katkea jos (vaihdettu == false) break;  } } // Funktio taulukkofunktion tulostamiseen printArray(arr, size) { var i;  for (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; $vaihdettu = tosi; } } // Jos kahta elementtiä ei vaihdettu // sisäisellä silmukalla, katkea jos ($swaped == False) break; } } // Ohjainkoodi $arr = array(64, 34, 25, 12, 22, 11, 90); $len = koko($arr); bubbleSort($arr); echo 'Lajiteltu taulukko: 
'; for($i = 0; $i< $len; $i++) echo $arr[$i].' '; // This code is contributed by ChitraNayal. ?>>>  
  Lähtö      Aika monimutkaisuus:    PÄÄLLÄ2)  
    Aputila:    O(1)
 
    Kuplalajittelun edut:    
  • Bubble lajittelu on helppo ymmärtää ja toteuttaa.
  • Se ei vaadi ylimääräistä muistitilaa.
  • Se on vakaa lajittelualgoritmi, mikä tarkoittaa, että elementit, joilla on sama avainarvo, säilyttävät suhteellisen järjestyksensä lajitetussa lähdössä.
    Kuplalajittelun haitat:    
  • Kuplalajittelun aikamonimutkaisuus on O(N2), mikä tekee siitä erittäin hidasta suurille tietojoukoille.
  • Bubble sort on vertailupohjainen lajittelualgoritmi, mikä tarkoittaa, että se vaatii vertailuoperaattorin määrittämään syöttötietojoukon elementtien suhteellisen järjestyksen. Se voi rajoittaa algoritmin tehokkuutta tietyissä tapauksissa.
Joitakin Bubble Sort -ohjelmaan liittyviä usein kysyttyjä kysymyksiä:
    Mikä on Bubble-lajittelun rajakotelo?     
Kuplalajittelu vie minimiajan (n järjestys), kun elementit on jo lajiteltu. Siksi on parasta tarkistaa etukäteen, onko taulukko jo lajiteltu vai ei, jotta vältetään O(N2) ajan monimutkaisuus.
 
Tapahtuuko lajittelu paikallaan Bubble lajittelussa?
Kyllä, Bubble sort suorittaa vierekkäisten parien vaihdon ilman suuria tietorakenteita. Tästä syystä Bubble sort -algoritmi on paikallaan oleva algoritmi.
 
Onko Bubble sort -algoritmi vakaa?
Kyllä, kuplalajittelualgoritmi on vakaa.
 
Missä Bubble sort -algoritmia käytetään?
Yksinkertaisuudensa vuoksi kuplalajittelua käytetään usein esittelemään lajittelualgoritmin käsite. Tietokonegrafiikassa se on suosittu sen kyvystään havaita pieni virhe (kuten vain kahden elementin vaihto) lähes lajiteltuissa taulukoissa ja korjata se vain lineaarisella monimutkaisella (2n).
 
Esimerkki: Sitä käytetään monikulmion täyttöalgoritmissa, jossa rajaavat viivat lajitellaan niiden x-koordinaatin mukaan tietyllä pyyhkäisyviivalla (x-akselin suuntainen viiva), ja y:tä kasvatettaessa niiden järjestys muuttuu (kaksi elementtiä vaihdetaan) vain kahden viivan risteyksessä.
 
    Aiheeseen liittyvät artikkelit:     
 
  •  Rekursiivinen kuplalajittelu 
  •  Lajittelun koodauskäytäntö 
  •  Bubble Sort -kysely 
  •  Kuplalajittelun monimutkaisuusanalyysi