Wprowadzenie do algorytmu sortowania bąbelkowego

Sortowanie to jedna z najbardziej podstawowych operacji, które można zastosować do danych. Możesz sortować elementy w różnych językach programowania przy użyciu różnych algorytmów sortowania, takich jak szybkie sortowanie, sortowanie bąbelkowe, sortowanie przez scalanie, sortowanie przez wstawianie itp. Sortowanie bąbelkowe to najprostszy algorytm spośród wszystkich.

W tym artykule poznasz działanie algorytmu Bubble Sort, pseudokodu Bubble Sort algorytm, jego złożoność czasową i przestrzenną oraz jego implementację w różnych językach programowania, takich jak C++, Python, C i JavaScript.

Jak działa algorytm sortowania bąbelków?

Sortowanie bąbelkowe to najprostszy algorytm sortowania, który wielokrotnie przechodzi przez listę, porównuje sąsiednie elementy i zamienia je, jeśli są w złej kolejności. Koncepcję tę można skuteczniej wyjaśnić za pomocą przykładu. Rozważ nieposortowaną tablicę z następującymi elementami: {16, 12, 15, 13, 19}.

Przykład:

Tutaj są porównywane sąsiednie elementy i jeśli nie są w porządku rosnącym, są zamieniane.

Pseudokod algorytmu sortowania bąbelków

W pseudokodzie, algorytm Bubble Sort można wyrazić jako:

bubbleSort (Arr[], rozmiar)
// pętla, aby uzyskać dostęp do każdego elementu tablicy
dla i=0 do rozmiaru-1 wykonaj:
// pętla do porównywania elementów tablicy
dla j=0 do rozmiaru-i-1 wykonaj:
// porównaj sąsiednie elementy
jeśli Arr[j] > Arr[j+1] to
// zamień je
zamiana (Arr[j], Arr[j+1])
koniec jeśli
koniec dla
koniec dla
koniec

Powyższy algorytm przetwarza wszystkie porównania, nawet jeśli tablica jest już posortowana. Można go dalej zoptymalizować, zatrzymując algorytm, jeśli wewnętrzna pętla nie spowodowała zamiany. Skróci to czas wykonania algorytmu.

Tak więc pseudokod zoptymalizowanego algorytmu Bubble Sort można wyrazić jako:

bubbleSort (Arr[], rozmiar)
// pętla, aby uzyskać dostęp do każdego elementu tablicy
dla i=0 do rozmiaru-1 wykonaj:
// sprawdź, czy następuje zamiana
zamienione = fałszywe
// pętla do porównywania elementów tablicy
dla j=0 do rozmiaru-i-1 wykonaj:
// porównaj sąsiednie elementy
jeśli Arr[j] > Arr[j+1] to
// zamień je
zamiana (Arr[j], Arr[j+1])
zamienione = prawda
koniec jeśli
koniec dla
// jeśli żadne elementy nie zostały zamienione, oznacza to, że tablica jest teraz posortowana, przerwij pętlę.
jeśli (nie zamieniony) to
złamać
koniec jeśli
koniec dla
koniec

Złożoność czasowa i przestrzeń pomocnicza algorytmu sortowania bąbelkowego

Najgorsza złożoność czasowa algorytmu sortowania bąbelków wynosi O(n^2). Występuje, gdy tablica jest w porządku malejącym i chcesz ją posortować w porządku rosnącym lub odwrotnie.

Najlepszą złożonością czasową algorytmu sortowania bąbelków jest O(n). Występuje, gdy tablica jest już posortowana.

Związane z: Co to jest notacja Big-O?

Średnia złożoność czasowa algorytmu sortowania bąbelków wynosi O(n^2). Występuje, gdy elementy tablicy są w pomieszanej kolejności.

Przestrzeń pomocnicza wymagana dla algorytmu Bubble Sort to O(1).

Implementacja algorytmu sortowania bąbelków w C++++

Poniżej znajduje się implementacja algorytmu Bubble Sort w C++:

// Implementacja C++
// zoptymalizowany algorytm Bubble Sort
#zawierać 
używając standardowej przestrzeni nazw;
// Funkcja do wykonania sortowania bąbelkowego
void bubbleSort (int arr[], int size) {
// Pętla, aby uzyskać dostęp do każdego elementu tablicy
dla (int i=0; i// Zmienna sprawdzająca, czy następuje zamiana
bool swapped = false;
// pętla do porównania dwóch sąsiednich elementów tablicy
dla (int j = 0; j < (rozmiar-i-1); j++) {
// Porównanie dwóch sąsiednich elementów tablicy
if (przyp[j] > przyp[j + 1]) {
// Zamień oba elementy, jeśli są
// nie w prawidłowej kolejności
int temp = przyp[j];
przyp[j] = przyp[j + 1];
przyb[j + 1] = temp;
zamienione = prawda;
}
}
// Jeśli żadne elementy nie zostały zamienione, oznacza to, że tablica jest teraz posortowana,
// następnie przerwij pętlę.
if (zamienione == fałsz) {
złamać;
}
}
}
// Wyświetla elementy tablicy
void printArray (int arr[], int rozmiar) {
dla (int i = 0; ja < rozmiar; i++) {
cout << arr[i] << " ";
}
cout << endl;
}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Znajdowanie długości tablicy
int rozmiar = rozmiar (arr) / rozmiar (arr[0]);
// Drukowanie podanej nieposortowanej tablicy
cout << "Niesortowana tablica: " << endl;
printArray (arr, rozmiar);
// Wywołanie funkcji bubbleSort()
bubbleSort (arr, rozmiar);
// Drukowanie posortowanej tablicy
cout << "Tablica posortowana w porządku rosnącym:" << endl;
printArray (arr, rozmiar);
zwróć 0;
}

Wynik:

Nieposortowana tablica: 
16 12 15 13 19 
Tablica posortowana w porządku rosnącym:
12 13 15 16 19

Implementacja algorytmu sortowania bąbelków w Pythonie

Poniżej znajduje się implementacja algorytmu Bubble Sort w Pythonie:

# Implementacja w Pythonie
# zoptymalizowany algorytm sortowania bąbelków
# Funkcja do wykonania sortowania bąbelkowego
def bubbleSort (arr, rozmiar):
# Pętla, aby uzyskać dostęp do każdego elementu listy
dla i w zakresie (rozmiar-1):
# Zmienna do sprawdzenia, czy następuje zamiana
zamienione = Fałsz
# pętla do porównania dwóch sąsiednich elementów listy
dla j w zakresie (rozmiar-i-1):
# Porównanie dwóch sąsiednich elementów listy
jeśli przyp[j] > przyp[j+1]:
temp = przyp[j]
przyp[j] = przyp[j+1]
arr[j+1] = temp
zamienione = Prawda
# Jeśli żadne elementy nie zostały zamienione, oznacza to, że lista jest teraz posortowana,
# następnie przerwij pętlę.
jeśli zamienione == Fałsz:
złamać
# Wyświetla elementy listy
def printArray (arr):
dla elementu w arr:
drukuj (element, end=" ")
wydrukować("")
przyp = [16, 12, 15, 13, 19]
# Znalezienie długości listy
rozmiar = len (arr)
# Drukowanie podanej nieposortowanej listy
print("Nieposortowana lista:")
printArray (arr)
# Wywołanie funkcji bubbleSort()
bubbleSort (arr, rozmiar)
# Drukowanie posortowanej listy
print("Lista posortowana w porządku rosnącym:")
printArray (arr)

Wynik:

Lista nieposortowana:
16 12 15 13 19 
Lista posortowana w porządku rosnącym:
12 13 15 16 19

Związane z: Jak używać pętli for w Pythonie

C Implementacja algorytmu sortowania bąbelkowego

Poniżej znajduje się implementacja w C algorytmu Bubble Sort:

// Implementacja C
// zoptymalizowany algorytm Bubble Sort
#zawierać 
#zawierać 
// Funkcja do wykonania sortowania bąbelkowego
void bubbleSort (int arr[], int size) {
// Pętla, aby uzyskać dostęp do każdego elementu tablicy
dla (int i=0; i// Zmienna sprawdzająca, czy następuje zamiana
bool swapped = false;
// pętla do porównania dwóch sąsiednich elementów tablicy
dla (int j = 0; j < (rozmiar-i-1); j++) {
// Porównanie dwóch sąsiednich elementów tablicy
if (przyp[j] > przyp[j + 1]) {
// Zamień oba elementy, jeśli są
// nie w prawidłowej kolejności
int temp = przyp[j];
przyp[j] = przyp[j + 1];
przyb[j + 1] = temp;
zamienione = prawda;
}
}
// Jeśli żadne elementy nie zostały zamienione, oznacza to, że tablica jest teraz posortowana,
// następnie przerwij pętlę.
if (zamienione == fałsz) {
złamać;
}
}
}
// Wyświetla elementy tablicy
void printArray (int arr[], int rozmiar) {
dla (int i = 0; ja < rozmiar; i++) {
printf("%d", arr[i]);
}
printf(" \⁠n ");
}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Znajdowanie długości tablicy
int rozmiar = rozmiar (arr) / rozmiar (arr[0]);
// Drukowanie podanej nieposortowanej tablicy
printf("Tablica niesortowana: \⁠n");
printArray (arr, rozmiar);
// Wywołanie funkcji bubbleSort()
bubbleSort (arr, rozmiar);
// Drukowanie posortowanej tablicy
printf("Tablica posortowana w porządku rosnącym: \⁠n");
printArray (arr, rozmiar);
zwróć 0;
}

Wynik:

Nieposortowana tablica: 
16 12 15 13 19 
Tablica posortowana w porządku rosnącym: 
12 13 15 16 19

Implementacja algorytmu sortowania bąbelków w JavaScript

Poniżej znajduje się implementacja JavaScript algorytmu Bubble Sort:

// Implementacja JavaScript
// zoptymalizowany algorytm Bubble Sort
// Funkcja do wykonania sortowania bąbelkowego
funkcja bubbleSort (arr, rozmiar) {
// Pętla, aby uzyskać dostęp do każdego elementu tablicy
dla (niech i=0; ja// Zmienna sprawdzająca, czy następuje zamiana
var zamienione = fałsz;
// pętla do porównania dwóch sąsiednich elementów tablicy
dla (niech j=0; jot// Porównanie dwóch sąsiednich elementów tablicy
if (przyp[j] > przyp[j+1]) {
// Zamień oba elementy, jeśli są
// nie w prawidłowej kolejności
niech temp = arr[j];
przyp[j] = przyp[j+1];
przyp[j+1] = temp;
zamienione = prawda;
}
// Jeśli żadne elementy nie zostały zamienione, oznacza to, że tablica jest teraz posortowana,
// następnie przerwij pętlę.
if (zamienione == fałsz) {
złamać;
}
}
}
}
// Wyświetla elementy tablicy
funkcja printArray (arr, rozmiar) {
dla (niech i=0; jadocument.write (arr[i] + " ");
}
dokument.zapis("
")
}
var arr = [16, 12, 15, 13, 19];
// Znajdowanie długości tablicy
var rozmiar = arr.długość;
// Drukowanie podanej nieposortowanej tablicy
document.write("Nieposortowana tablica: 
");
printArray (arr, rozmiar);
// Wywołanie funkcji bubbleSort()
bubbleSort (arr, rozmiar);
// Drukowanie posortowanej tablicy
document.write("Tablica posortowana w kolejności rosnącej: 
");
printArray (arr, rozmiar);

Wynik:

Nieposortowana tablica:
16 12 15 13 19
Tablica posortowana w porządku rosnącym:
12 15 13 16 19

Teraz rozumiesz działanie algorytmu sortowania bąbelków

Sortowanie bąbelkowe jest najprostszym algorytmem sortowania i służy głównie do zrozumienia podstaw sortowania. Sortowanie bąbelkowe można również zaimplementować rekurencyjnie, ale nie zapewnia to żadnych dodatkowych korzyści.

Używając Pythona, możesz z łatwością zaimplementować algorytm Bubble Sort. Jeśli nie znasz języka Python i chcesz rozpocząć swoją podróż, dobrym wyborem będzie rozpoczęcie od skryptu „Hello World”.

Jak zacząć korzystać z Pythona za pomocą skryptu „Hello World”?

Python jest jednym z najpopularniejszych obecnie używanych języków programowania. Postępuj zgodnie z tym samouczkiem, aby rozpocząć pracę z pierwszym skryptem w języku Python.

Czytaj dalej

O autorze