Sortowanie bąbelkowe jest najprostszy algorytm sortowania działa to poprzez wielokrotną zamianę sąsiednich elementów, jeśli są w niewłaściwej kolejności. Algorytm ten nie nadaje się do dużych zbiorów danych, ponieważ jego średnia i najgorszy przypadek złożoności czasowej jest dość wysoka.
Algorytm sortowania bąbelkowego
Zalecana praktyka Sortowanie bąbelkowe Wypróbuj!W algorytmie sortowania bąbelkowego
Pythona lub
- przejdź od lewej strony i porównaj sąsiednie elementy, a wyższy zostanie umieszczony po prawej stronie.
- W ten sposób największy element zostanie najpierw przesunięty na prawy koniec.
- Następnie proces ten jest kontynuowany w celu znalezienia drugiego co do wielkości i umieszczenia go, i tak dalej, aż dane zostaną posortowane.
Jak działa sortowanie bąbelkowe?
Przyjrzyjmy się działaniu sortowania bąbelkowego na podstawie poniższej ilustracji:
Wejście: tablica [] = {6, 0, 3, 5}
Pierwsze przejście:
Największy element umieszczany jest na swoim właściwym miejscu, czyli na końcu tablicy.
Algorytm sortowania bąbelkowego: Umieszczanie największego elementu we właściwej pozycji
Drugie przejście:
Umieść drugi co do wielkości element we właściwym miejscu
Algorytm sortowania bąbelkowego: Umieszczenie drugiego co do wielkości elementu we właściwej pozycji
Trzecie przejście:
Umieść pozostałe dwa elementy na właściwych miejscach.
Algorytm sortowania bąbelkowego: Umieszczanie pozostałych elementów na właściwych miejscach
klasa skanera Java
- Całkowita liczba przepustek: n-1
- Całkowita liczba porównań: n*(n-1)/2
Implementacja sortowania bąbelkowego
Poniżej znajduje się implementacja sortowania bąbelkowego. Można to zoptymalizować, zatrzymując algorytm, jeśli pętla wewnętrzna nie spowodowała żadnej zamiany.
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]) { zamiana(arr[j], arr[j + 1]); zamienione = prawda; } } // Jeśli żadne dwa elementy nie zostały zamienione // za pomocą pętli wewnętrznej, następuje przerwa if (swapped == false) break; } } // Funkcja drukująca tablicę void printArray(int arr[], int size) { int i; dla (i = 0; tj< 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]); zamienione = prawda; } } // Jeśli w pętli wewnętrznej nie zostały zamienione żadne dwa elementy, // następuje przerwa if (swapped == false) break; } } // Funkcja drukująca tablicę void printArray(int arr[], int size) { int i; dla (i = 0; tj< 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; }> Jawa // 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]) { // Zamień arr[j] i arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temperatura; zamienione = prawda; } } // Jeśli żadne dwa elementy nie zostały // zamienione za pomocą pętli wewnętrznej, następuje przerwa if (swapped == false) break; } } // Funkcja wyświetlająca tablicę statyczną void printArray(int arr[], int size) { int i; dla (i = 0; tj< 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 = True if (zamieniony == False): break # Kod sterownika do sprawdzenia powyżej, jeśli __name__ == '__main__': arr = [64, 34, 25, 12, 22, 11, 90] bubbleSort(arr) print('Sortowana tablica:') dla i w zakresie(dł.(arr)): print('%d' % arr[i], end=' ') # Ten kod zmodyfikował 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]) { // Zamień arr[j] i arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temperatura; zamienione = prawda; } } // Jeśli żadne dwa elementy nie zostały // zamienione za pomocą pętli wewnętrznej, następuje przerwa if (swapped == false) break; } } // Funkcja wyświetlająca tablicę statyczną void printArray(int[] arr, int size) { int i; dla (i = 0; tj< 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]) { // Zamień arr[j] i arr[j+1] temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temperatura; zamienione = prawda; } } // JEŚLI żadne dwa elementy nie zostały // zamienione przez pętlę wewnętrzną, to break if (swapped == false) break; } } // Funkcja drukująca tablicę funkcja printArray(arr, size) { var i; dla (i = 0; tj< 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; $ zamienione = Prawda; } } // Jeśli żadne dwa elementy nie zostały zamienione // za pomocą pętli wewnętrznej, następuje przerwa if ($swapped == False) break; } } // Kod sterownika $arr = array(64, 34, 25, 12, 22, 11, 90); $len = rozmiar($arr); sortowanie bąbelkowe($arr); echo 'Posortowana tablica:
'; for($i = 0; $i< $len; $i++) echo $arr[$i].' '; // This code is contributed by ChitraNayal. ?>> Wyjście
Sorted array: 11 12 22 25 34 64 90>
Analiza złożoności sortowania bąbelkowego :
Złożoność czasowa: NA2)
Przestrzeń pomocnicza: O(1)
Zalety sortowania bąbelkowego:
- Sortowanie bąbelkowe jest łatwe do zrozumienia i wdrożenia.
- Nie wymaga dodatkowej przestrzeni pamięci.
- Jest to stabilny algorytm sortowania, co oznacza, że elementy o tej samej wartości klucza zachowują swój względny porządek w posortowanym wyniku.
Wady sortowania bąbelkowego:
- Sortowanie bąbelkowe ma złożoność czasową O(N2), co sprawia, że jest bardzo powolny w przypadku dużych zbiorów danych.
- Sortowanie bąbelkowe to algorytm sortowania oparty na porównaniach, co oznacza, że wymaga operatora porównania w celu określenia względnej kolejności elementów w zbiorze danych wejściowych. W niektórych przypadkach może to ograniczyć skuteczność algorytmu.
Niektóre często zadawane pytania dotyczące sortowania bąbelkowego:
Co to jest przypadek graniczny dla sortowania bąbelkowego?
Sortowanie bąbelkowe zajmuje minimum czasu (kolejność n), gdy elementy są już posortowane. Dlatego najlepiej jest wcześniej sprawdzić, czy tablica jest już posortowana, czy nie, aby uniknąć O(N2) złożoność czasowa.
Czy sortowanie odbywa się w trybie bąbelkowym?
Tak, sortowanie bąbelkowe dokonuje zamiany sąsiadujących par bez użycia jakiejkolwiek większej struktury danych. Dlatego algorytm sortowania bąbelkowego jest algorytmem lokalnym.
Czy algorytm sortowania bąbelkowego jest stabilny?
Tak, algorytm sortowania bąbelkowego jest stabilny.
Gdzie używany jest algorytm sortowania bąbelkowego?
Sortowanie bąbelkowe ze względu na swoją prostotę jest często używane do wprowadzenia koncepcji algorytmu sortowania. W grafice komputerowej jest popularny ze względu na możliwość wykrycia drobnego błędu (takiego jak zamiana zaledwie dwóch elementów) w prawie posortowanych tablicach i naprawienia go przy użyciu jedynie złożoności liniowej (2n).
Przykład: jest używany w algorytmie wypełniania wielokątów, gdzie linie ograniczające są sortowane według współrzędnej x na określonej linii skanowania (linia równoległa do osi x), a wraz ze zwiększaniem y zmienia się tylko ich kolejność (zamieniane są dwa elementy) na przecięciach dwóch linii.
Powiązane artykuły:
- Rekurencyjne sortowanie bąbelkowe
- Praktyka kodowania przy sortowaniu
- Quiz dotyczący sortowania bąbelkowego
- Analiza złożoności sortowania bąbelkowego