W tym samouczku dowiesz się, jak działa sortowanie bąbelkowe. Znajdziesz również działające przykłady sortowania bąbelkowego w C, C ++, Javie i Pythonie.
Sortowanie bąbelkowe to algorytm, który porównuje sąsiednie elementy i zamienia ich pozycje, jeśli nie są w zamierzonej kolejności. Kolejność może być rosnąca lub malejąca.
Jak działa sortowanie bąbelkowe?
- Zaczynając od pierwszego indeksu, porównaj pierwszy i drugi element, jeśli pierwszy element jest większy niż drugi, zostaną zamienione.
Teraz porównaj drugi i trzeci element. Zamień je, jeśli nie są w porządku.
Powyższy proces trwa do ostatniego elementu.
Porównaj sąsiednie elementy - Ten sam proces przebiega w pozostałych iteracjach. Po każdej iteracji największy element spośród nieposortowanych elementów jest umieszczany na końcu.
W każdej iteracji następuje porównanie do ostatniego nieposortowanego elementu.
Tablica jest sortowana, gdy wszystkie nieposortowane elementy zostaną umieszczone na właściwych pozycjach.
Porównaj sąsiednie elementy 
Porównaj sąsiednie elementy 
Porównaj sąsiednie elementy
Algorytm sortowania bąbelkowego
bubbleSort (tablica) dla i zamiany rightElement leftElement i rightElement koniec bubbleSort
Przykłady w Pythonie, Javie i C / C ++
Python Java C C ++ # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)
// Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )
// Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
Zoptymalizowane sortowanie bąbelkowe
W powyższym kodzie wszystkie możliwe porównania są dokonywane, nawet jeśli tablica jest już posortowana. Zwiększa czas wykonania.
Kod można zoptymalizować, wprowadzając dodatkową zamienioną zmienną. Po każdej iteracji, jeśli nie ma zamiany, nie ma potrzeby wykonywania kolejnych pętli.
W takim przypadku zmienna zamieniona ma wartość false. W ten sposób możemy zapobiec dalszym iteracjom.
Algorytm zoptymalizowanego sortowania bąbelkowego to
bubbleSort (array) swapped <- false for i rightElement swap leftElement and rightElement swapped <- true end bubbleSort
Zoptymalizowane przykłady sortowania bąbelkowego
Python Java C + # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)
// Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )
// Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )
// Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (
// Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )
Złożoność
Sortowanie bąbelkowe to jeden z najprostszych algorytmów sortowania. W algorytmie zaimplementowano dwie pętle.
| Cykl | Liczba porównań |
|---|---|
| 1 | (n-1) |
| 2nd | (n-2) |
| 3rd | (n-3) |
| … | … |
| ostatni, ubiegły, zeszły | 1 |
Liczba porównań: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 prawie równa się n 2
Złożoność: O (n 2 )
Możemy również przeanalizować złożoność, po prostu obserwując liczbę pętli. Istnieją 2 pętle, więc złożoność jestn*n = n2
Złożoność czasowa:
-
Najgorsza złożoność przypadku : jeśli chcemy posortować w porządku rosnącym, a tablica jest w porządku malejącym, wtedy pojawia się najgorszy przypadek.
O(n2) -
Najlepsza złożoność
O(n)
przypadku : jeśli tablica jest już posortowana, nie ma potrzeby sortowania. -
Średnia złożoność przypadku: występuje, gdy elementy tablicy są pomieszane (ani rosnąco, ani malejąco).
O(n2)
Złożoność przestrzeni: Złożoność
przestrzeni wynika z tego, O(1)że do zamiany używana jest dodatkowa zmienna temp.
W zoptymalizowanym algorytmie zamieniana zmienna zwiększa złożoność przestrzeni, czyniąc ją tym samym O(2).
Aplikacje do sortowania bąbelkowego
Sortowanie bąbelkowe jest używane w następujących przypadkach, w których
- złożoność kodu nie ma znaczenia.
- preferowany jest krótki kod.
