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 jest najprostszym algorytmem spośród wszystkich.

W tym artykule dowiesz się o działaniu algorytmu Bubble Sort, pseudokodzie algorytmu Bubble Sort, jego złożoności czasowej i przestrzennej oraz jego implementacji 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[], size)
// loop to access each array element
for i=0 to size-1 do:
// loop to compare array elements
for j=0 to size-i-1 do:
// compare the adjacent elements
if Arr[j] > Arr[j+1] then
// swap them
swap(Arr[j], Arr[j+1])
end if
end for
end for
end


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[], size)
// loop to access each array element
for i=0 to size-1 do:
// check if swapping occurs
swapped = false
// loop to compare array elements
for j=0 to size-i-1 do:
// compare the adjacent elements
if Arr[j] > Arr[j+1] then
// swap them
swap(Arr[j], Arr[j+1])
swapped = true
end if
end for
// if no elements were swapped that means the array is sorted now, then break the loop.
if(not swapped) then
break
end if
end for
end


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.

---

---

złe informacje o konfiguracji systemu Windows 10 2019

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

czy ps5 gra w gry ps4?

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++:

// C++ implementation of the
// optimised Bubble Sort algorithm
#include
using namespace std;
// Function to perform Bubble Sort
void bubbleSort(int arr[], int size) {
// Loop to access each element of the array
for (int i=0; i<(size-1); i++) {
// Variable to check if swapping occurs
bool swapped = false;
// loop to compare two adjacent elements of the array
for (int j = 0; j <(size-i-1); j++) {
// Comparing two adjacent array elements
if (arr[j] > arr[j + 1]) {
// Swap both elements if they're
// not in correct order
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no elements were swapped that means the array is sorted now,
// then break the loop.
if (swapped == false) {
break;
}
}
}
// Prints the elements of the array
void printArray(int arr[], int size) {
for (int i = 0; i cout << arr[i] << ' ';
}
cout << endl;
}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Finding the length of the array
int size = sizeof(arr) / sizeof(arr[0]);
// Printing the given unsorted array
cout << 'Unsorted Array: ' << endl;
printArray(arr, size);
// Calling bubbleSort() function
bubbleSort(arr, size);
// Printing the sorted array
cout << 'Sorted Array in Ascending Order:' << endl;
printArray(arr, size);
return 0;
}


Wyjście:

Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 13 15 16 19

Implementacja algorytmu sortowania bąbelków w Pythonie

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

# Python implementation of the
# optimised Bubble Sort algorithm

# Function to perform Bubble Sort
def bubbleSort(arr, size):
# Loop to access each element of the list
for i in range (size-1):
# Variable to check if swapping occurs
swapped = False
# loop to compare two adjacent elements of the list
for j in range(size-i-1):
# Comparing two adjacent list elements
if arr[j] > arr[j+1]:
temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
swapped = True
# If no elements were swapped that means the list is sorted now,
# then break the loop.
if swapped == False:
break
# Prints the elements of the list
def printArray(arr):
for element in arr:
print(element, end=' ')
print('')

arr = [16, 12, 15, 13, 19]
# Finding the length of the list
size = len(arr)
# Printing the given unsorted list
print('Unsorted List:')
printArray(arr)
# Calling bubbleSort() function
bubbleSort(arr, size)
# Printing the sorted list
print('Sorted List in Ascending Order:')
printArray(arr)


Wyjście:

Unsorted List:
16 12 15 13 19
Sorted List in Ascending Order:
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:

// C implementation of the
// optimised Bubble Sort algorithm
#include
#include
// Function to perform Bubble Sort
void bubbleSort(int arr[], int size) {
// Loop to access each element of the array
for (int i=0; i<(size-1); i++) {
// Variable to check if swapping occurs
bool swapped = false;
// loop to compare two adjacent elements of the array
for (int j = 0; j <(size-i-1); j++) {
// Comparing two adjacent array elements
if (arr[j] > arr[j + 1]) {
// Swap both elements if they're
// not in correct order
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
}
}
// If no elements were swapped that means the array is sorted now,
// then break the loop.
if (swapped == false) {
break;
}
}
}
// Prints the elements of the array
void printArray(int arr[], int size) {
for (int i = 0; i printf('%d ', arr[i]);
}
printf(' ⁠n ');
}
int main() {
int arr[] = {16, 12, 15, 13, 19};
// Finding the length of the array
int size = sizeof(arr) / sizeof(arr[0]);
// Printing the given unsorted array
printf('Unsorted Array: ⁠n');
printArray(arr, size);
// Calling bubbleSort() function
bubbleSort(arr, size);
// Printing the sorted array
printf('Sorted Array in Ascending Order: ⁠n');
printArray(arr, size);
return 0;
}

Wyjście:

Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
12 13 15 16 19

Implementacja algorytmu sortowania bąbelków w JavaScript

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

// JavaScript implementation of the
// optimised Bubble Sort algorithm
// Function to perform Bubble Sort
function bubbleSort(arr, size) {
// Loop to access each element of the array
for(let i=0; i // Variable to check if swapping occurs
var swapped = false;
// loop to compare two adjacent elements of the array
for(let j=0; j // Comparing two adjacent array elements
if(arr[j] > arr[j+1]) {
// Swap both elements if they're
// not in correct order
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
swapped = true;
}
// If no elements were swapped that means the array is sorted now,
// then break the loop.
if (swapped == false) {
break;
}
}
}
}
// Prints the elements of the array
function printArray(arr, size) {
for (let i=0; i document.write(arr[i] + ' ');
}
document.write('
')
}

var arr = [16, 12, 15, 13, 19];
// Finding the length of the array
var size = arr.length;
// Printing the given unsorted array
document.write('Unsorted Array:
');
printArray(arr, size);
// Calling bubbleSort() function
bubbleSort(arr, size);
// Printing the sorted array
document.write('Sorted Array in Ascending Order:
');
printArray(arr, size);


Wyjście:

Unsorted Array:
16 12 15 13 19
Sorted Array in Ascending Order:
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”.

Udział Udział Ćwierkać E-mail Jak rozpocząć pracę z Pythonem 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 Powiązane tematy

• Programowanie
• Jawa
• Pyton
• Poradniki kodowania

O autorze Yuvraj Chandra(60 opublikowanych artykułów)

Yuvraj jest studentem informatyki na Uniwersytecie w Delhi w Indiach. Jest pasjonatem Full Stack Web Development. Kiedy nie pisze, bada głębię różnych technologii.

jak łatwo jest włamać się do kamery internetowej

Więcej od Yuvraja Chandra

Zapisz się do naszego newslettera

Dołącz do naszego newslettera, aby otrzymywać porady techniczne, recenzje, bezpłatne e-booki i ekskluzywne oferty!

Kliknij tutaj, aby zasubskrybować