Bevezetés a buborékrendező algoritmusba

A rendezés az egyik legalapvetőbb művelet, amelyet az adatokra alkalmazhat. Az elemeket különböző programozási nyelveken rendezheti különféle rendezési algoritmusokkal, mint például a Gyors rendezés, Buborékrendezés, Összevonás Rendezés, Beszúrás Rendezés stb. A buborékrendezés a legegyszerűbb algoritmus mindezek között.

Ebben a cikkben megismerkedhet a Bubble Sort algoritmus működésével, a Bubble Sort algoritmus pszeudokódjával, idő- és térbeli összetettségével, valamint különböző programozási nyelveken, például C ++, Python, C és JavaScript.

---

---

Hogyan működik a buborékrendezési algoritmus?

A Buborékrendezés a legegyszerűbb rendezési algoritmus, amely többször átlépi a listát, összehasonlítja a szomszédos elemeket, és kicseréli őket, ha rossz sorrendben vannak. Ez a fogalom hatékonyabban magyarázható egy példa segítségével. Tekintsünk egy nem rendezett tömböt a következő elemekkel: {16, 12, 15, 13, 19}.

Példa:

Itt összehasonlítják a szomszédos elemeket, és ha nem növekvő sorrendben vannak, akkor felcserélik őket.

A buborékrendező algoritmus pszeudokódja

Az álkódban a Bubble Sort algoritmus a következőképpen fejezhető ki:

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


A fenti algoritmus az összes összehasonlítást feldolgozza, még akkor is, ha a tömb már rendezett. Tovább optimalizálható az algoritmus leállításával, ha a belső hurok nem okozott cserét. Ez csökkenti az algoritmus végrehajtási idejét.

---

---

Így az optimalizált Bubble Sort algoritmus pszeudokódja a következőképpen fejezhető ki:

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


A buborékrendező algoritmus időbonyolultsága és segédtere

A buborékrendező algoritmus legrosszabb időbeli összetettsége O (n^2). Ez akkor fordul elő, ha a tömb csökkenő sorrendben van, és növekvő sorrendben szeretné rendezni, vagy fordítva.

---

---

hogyan lehet egyesíteni két fotót androidon

A buborékrendező algoritmus legjobb esetbeni bonyolultsága O (n). Ez akkor fordul elő, ha a tömb már rendezett.

hogyan működik az Overwatch rangsorolási rendszer

Összefüggő: Mi az a Big-O jelölés?

A buborékrendezési algoritmus átlagos esetösszetétele O (n^2). Ez akkor fordul elő, ha a tömb elemei összekevert sorrendben vannak.

A Bubble Sort algoritmushoz szükséges segédterület O (1).

C ++ A buborékrendező algoritmus megvalósítása

Az alábbiakban bemutatjuk a Bubble Sort algoritmus C ++ megvalósítását:

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


Kimenet:

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

A buborékrendező algoritmus Python implementációja

Az alábbiakban bemutatjuk a Bubble Sort algoritmus Python implementációját:

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


Kimenet:

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

Összefüggő: Hogyan kell használni hurkokhoz Pythonban

C A buborékrendező algoritmus megvalósítása

Az alábbiakban bemutatjuk a Bubble Sort algoritmus C megvalósítását:

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

Kimenet:

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

A buborékrendező algoritmus JavaScript implementációja

Az alábbiakban bemutatjuk a Bubble Sort algoritmus JavaScript -implementációját:

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


Kimenet:

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

Most már érti a buborékrendező algoritmus működését

A Bubble Sort a legegyszerűbb rendezési algoritmus, és főleg a rendezés alapjainak megértésére szolgál. A Bubble Sort rekurzív módon is megvalósítható, de további előnyökkel nem jár.

A Python használatával könnyedén megvalósíthatja a Bubble Sort algoritmust. Ha még nem ismeri a Python programot, és szeretné elindítani az utazást, akkor a 'Hello World' szkripttel való kezdés nagyszerű választás.

Részvény Részvény Csipog Email A Python használatának megkezdése a „Hello World” szkript használatával

A Python ma az egyik legnépszerűbb programozási nyelv. Kövesse ezt az oktatóanyagot a legelső Python -szkript használatához.

Olvassa tovább Kapcsolódó témák

• Programozás
• Jáva
• Piton
• Kódolási oktatóanyagok

A szerzőről Yuvraj Chandra(60 cikk megjelent)

Yuvraj egy számítástechnikai egyetemi hallgató a Delhi Egyetemen, Indiában. Szenvedélyesen foglalkozik a Full Stack webfejlesztéssel. Amikor nem ír, a különböző technológiák mélységét kutatja.

miért nem működik a snapom?

Bővebben: Yuvraj Chandra

Iratkozzon fel hírlevelünkre

Csatlakozz hírlevelünkhöz, ahol technikai tippeket, véleményeket, ingyenes e -könyveket és exkluzív ajánlatokat találsz!

Feliratkozáshoz kattintson ide