Įvadas į burbulų rūšiavimo algoritmą

Rūšiavimas yra viena iš pagrindinių operacijų, kurią galite taikyti duomenims. Galite rūšiuoti elementus skirtingomis programavimo kalbomis naudodami įvairius rūšiavimo algoritmus, tokius kaip greitas rūšiavimas, burbuliukų rūšiavimas, sujungimo rūšiavimas, įterpimo rūšiavimas ir kt. Burbulų rūšiavimas yra pats paprasčiausias algoritmas tarp visų šių.

Šiame straipsnyje sužinosite apie „Bubble Sort“ algoritmo veikimą, „Bubble Sort“ algoritmo pseudokodą, jo laiką ir erdvės sudėtingumą bei jo įgyvendinimą įvairiomis programavimo kalbomis, tokiomis kaip „C ++“, „Python“, „C“ ir „JavaScript“.

---

---

Kaip veikia burbulų rūšiavimo algoritmas?

„Bubble Rūšiavimas“ yra paprasčiausias rūšiavimo algoritmas, kuris pakartotinai seka sąrašą, lygina gretimus elementus ir keičia juos, jei jie neteisinga tvarka. Šią sąvoką galima efektyviau paaiškinti naudojant pavyzdį. Apsvarstykite nerūšiuotą masyvą su šiais elementais: {16, 12, 15, 13, 19}.

Pavyzdys:

Čia gretimi elementai yra lyginami ir, jei jie nėra didėjančia tvarka, jie keičiami.

Burbulo rūšiavimo algoritmo pseudokodas

Pseudokode „Bubble Sort“ algoritmas gali būti išreikštas taip:

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


Aukščiau pateiktas algoritmas apdoroja visus palyginimus, net jei masyvas jau yra surūšiuotas. Jį galima toliau optimizuoti sustabdžius algoritmą, jei vidinė kilpa nesukėlė jokių apsikeitimų. Tai sutrumpins algoritmo vykdymo laiką.

---

---

Taigi optimizuoto burbulo rūšiavimo algoritmo pseudokodas gali būti išreikštas taip:

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


Laiko sudėtingumas ir pagalbinė burbulų rūšiavimo algoritmo erdvė

Blogiausias burbulų rūšiavimo algoritmo sudėtingumas yra O (n^2). Tai atsitinka, kai masyvas yra mažėjančia tvarka ir norite jį rūšiuoti didėjančia tvarka arba atvirkščiai.

---

---

žadintuvas, leidžiantis išlipti iš lovos

Geriausias burbulų rūšiavimo algoritmo laiko sudėtingumas yra O (n). Tai atsitinka, kai masyvas jau surūšiuotas.

Kaip priversti kompiuterį atpažinti „Samsung“ telefoną?

Susijęs: Kas yra „Big-O“ žymėjimas?

Vidutinis burbulų rūšiavimo algoritmo sudėtingumas yra O (n^2). Tai atsitinka, kai masyvo elementai yra sumaišyti.

Pagalbinė erdvė, reikalinga burbulų rūšiavimo algoritmui, yra O (1).

C ++ burbulų rūšiavimo algoritmo įgyvendinimas

Žemiau pateikiamas burbuliukų rūšiavimo algoritmo C ++ diegimas:

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


Išėjimas:

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

„Python“ burbulų rūšiavimo algoritmo įgyvendinimas

Žemiau pateikiamas „Bubble Sort“ algoritmo „Python“ diegimas:

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


Išėjimas:

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

Susijęs: Kaip naudoti kilpas „Python“

C Burbulų rūšiavimo algoritmo įgyvendinimas

Žemiau pateikiamas burbulų rūšiavimo algoritmo C įgyvendinimas:

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

Išėjimas:

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

„JavaScript“ burbulų rūšiavimo algoritmo diegimas

Žemiau pateikiamas „Bubble Sort“ algoritmo „JavaScript“ diegimas:

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


Išėjimas:

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

Dabar jūs suprantate burbulų rūšiavimo algoritmo veikimą

„Bubble Rūšiavimas“ yra paprasčiausias rūšiavimo algoritmas ir daugiausia naudojamas rūšiavimo pagrindams suprasti. „Bubble Sort“ taip pat gali būti įdiegtas rekursyviai, tačiau tai nesuteikia jokių papildomų privalumų.

Naudodami „Python“, galite lengvai įgyvendinti „Bubble Sort“ algoritmą. Jei nesate susipažinę su „Python“ ir norite pradėti savo kelionę, puikus pasirinkimas pradėti nuo „Hello World“ scenarijaus.

Dalintis Dalintis „Tweet“ Paštu Kaip pradėti naudotis „Python“ naudojant „Hello World“ scenarijų

„Python“ yra viena populiariausių šiandien naudojamų programavimo kalbų. Vykdykite šią pamoką, kad pradėtumėte su savo pirmuoju „Python“ scenarijumi.

Skaityti toliau Susijusios temos

• Programavimas
• „Java“
• Python
• Kodavimo pamokos

Apie autorių Yuvraj Chandra(Paskelbti 60 straipsnių)

Yuvraj yra kompiuterių mokslo bakalauro studentas Delyje, Indijoje. Jis aistringas „Full Stack“ žiniatinklio kūrimui. Kai jis nerašo, jis tyrinėja skirtingų technologijų gylį.

raspberry pi zero projektai pradedantiesiems

Daugiau iš Yuvraj Chandra

Prenumeruokite mūsų naujienlaiškį

Prisijunkite prie mūsų naujienlaiškio, kad gautumėte techninių patarimų, apžvalgų, nemokamų el. Knygų ir išskirtinių pasiūlymų!

Norėdami užsiprenumeruoti, spustelėkite čia