Úvod do algoritmu triedenia bublín

Zoradenie je jednou z najzákladnejších operácií, ktoré môžete s údajmi použiť. Prvky môžete triediť v rôznych programovacích jazykoch pomocou rôznych triediacich algoritmov, ako sú napríklad rýchle triedenie, bublinkové triedenie, zlučovacie triedenie, vkladacie triedenie atď. Bublinkové triedenie je zo všetkých najjednoduchší algoritmus.

V tomto článku sa dozviete o fungovaní algoritmu Bubble Sort, pseudokódu algoritmu Bubble Sort, jeho časovej a priestorovej zložitosti a jeho implementácii v rôznych programovacích jazykoch ako C ++, Python, C a JavaScript.

---

---

Ako funguje algoritmus triedenia bublín?

Bubble Sort je najjednoduchší algoritmus triedenia, ktorý opakovane prechádza zoznamom, porovnáva susedné prvky a zamieňa ich, ak sú v zlom poradí. Tento koncept je možné efektívnejšie vysvetliť na príklade. Zvážte netriedené pole s nasledujúcimi prvkami: {16, 12, 15, 13, 19}.

Príklad:

Tu sú porovnané susedné prvky a ak nie sú vo vzostupnom poradí, sú vymenené.

Pseudokód algoritmu triedenia bublín

V pseudokode môže byť algoritmus triedenia bublín vyjadrený ako:

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


Vyššie uvedený algoritmus spracováva všetky porovnania, aj keď je pole už zoradené. Ak vnútorná slučka nespôsobila výmenu, môže byť ďalej optimalizovaná zastavením algoritmu. Tým sa zníži doba vykonávania algoritmu.

---

---

Pseudokód optimalizovaného algoritmu triedenia bublín je teda možné vyjadriť ako:

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


Časová zložitosť a pomocný priestor algoritmu triedenia bublín

Časová zložitosť algoritmu zoradenia podľa bublín je O (n^2). K tomu dochádza, keď je pole zostupne a chcete ho zoradiť vzostupne alebo naopak.

---

---

ako spustiť diagnostiku systému v systéme Windows 10

Najlepšia časová zložitosť algoritmu zoradenia podľa bublín je O (n). K tomu dochádza, keď je pole už zoradené.

ako vytvoriť bootovacie USB z Windows 7

Súvisiace: Čo je to Big-O notácia?

Priemerná časová zložitosť algoritmu zoradenia podľa bublín je O (n^2). K tomu dochádza vtedy, keď sú prvky poľa usporiadané v neusporiadanom poradí.

Pomocný priestor požadovaný pre algoritmus triedenia bublín je O (1).

C ++ Implementácia algoritmu triedenia bublín

Nasleduje implementácia algoritmu Bubble Sort v jazyku 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;
}


Výkon:

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

Implementácia algoritmu bublinového triedenia v Pythone

Nasleduje implementácia algoritmu Bubble Sort v Pythone:

# 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)


Výkon:

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

Súvisiace: Ako používať slučky v Pythone

C Implementácia algoritmu triedenia podľa bublín

Nasleduje implementácia algoritmu Bubble Sort v jazyku C:

// 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;
}

Výkon:

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

Implementácia algoritmu bublinového triedenia v JavaScripte

Nasleduje implementácia algoritmu Bubble Sort v jazyku JavaScript:

// 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);


Výkon:

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

Teraz rozumiete fungovaniu algoritmu triedenia bublín

Bubble Sort je najjednoduchší algoritmus triedenia a používa sa hlavne na pochopenie základov triedenia. Bubble Sort je možné implementovať aj rekurzívne, ale neposkytuje na to žiadne ďalšie výhody.

V Pythone môžete algoritmus Bubble Sort implementovať ľahko. Ak nie ste oboznámení s Pythonom a chcete začať svoju cestu, začať so skriptom „Hello World“ je skvelou voľbou.

zdieľam zdieľam Tweet E -mail Ako začať s Pythonom pomocou skriptu „Hello World“

Python je jedným z najpopulárnejších programovacích jazykov, ktoré sa dnes používajú. Nasledujte tento návod a začnite so svojim úplne prvým skriptom v jazyku Python.

Čítajte ďalej Súvisiace témy

• Programovanie
• Java
• Python
• Návody na kódovanie

O autorovi Yuvraj Chandra(60 publikovaných článkov)

Yuvraj je študentom informatiky na univerzite v Dillí v Indii. Je nadšený pre vývoj webových aplikácií Full Stack. Keď nepíše, skúma hĺbku rôznych technológií.

nainštalujte si obchod Google Play do tabletu Fire

Viac od Yuvraja Chandru

prihlásiť sa ku odberu noviniek

Pripojte sa k nášmu bulletinu a získajte technické tipy, recenzie, bezplatné elektronické knihy a exkluzívne ponuky!

Kliknutím sem sa prihlásite na odber