Uvod u algoritam sortiranja mjehurića

Sortiranje je jedna od najosnovnijih operacija koje možete primijeniti na podatke. Elemente možete sortirati u različitim programskim jezicima pomoću različitih algoritama za sortiranje, poput Brzog sortiranja, Sortiranja mjehurića, Spajanja, Umetanja itd. Sortiranje mjehurića je najjednostavniji algoritam od svih ovih.

U ovom ćete članku naučiti o radu algoritma Bubble Sort, pseudokodu Bubble Sort algoritma, njegovoj vremenskoj i prostornoj složenosti te njegovoj implementaciji u različite programske jezike poput C ++, Python, C i JavaScript.

---

---

Kako funkcionira algoritam sortiranja mjehurića?

Sortiranje mjehurićima najjednostavniji je algoritam za sortiranje koji neprestano prolazi kroz popis, uspoređuje susjedne elemente i mijenja ih ako su u pogrešnom redoslijedu. Ovaj se koncept može učinkovitije objasniti uz pomoć primjera. Razmotrimo nerazvrstani niz sa sljedećim elementima: {16, 12, 15, 13, 19}.

Primjer:

Ovdje se uspoređuju susjedni elementi, a ako nisu u uzlaznom redoslijedu, zamjenjuju se.

Pseudokod algoritma za sortiranje mjehurića

U pseudokodu algoritam Bubble Sort može se izraziti kao:

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


Gornji algoritam obrađuje sve usporedbe čak i ako je niz već sortiran. Može se dodatno optimizirati zaustavljanjem algoritma ako unutarnja petlja nije uzrokovala zamjenu. To će smanjiti vrijeme izvršavanja algoritma.

---

---

Stoga se pseudokod optimiziranog algoritma sortiranja mjehurića može izraziti kao:

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


Vremenska složenost i pomoćni prostor algoritma za sortiranje mjehurića

Najgora vremenska složenost algoritma sortiranja mjehurića je O (n^2). To se događa kada je niz u silaznom redoslijedu i želite ga poredati u rastućem ili obrnuto.

---

---

Nisam dobio narudžbu za Amazon

Složenost u najboljem slučaju algoritma sortiranja mjehurića je O (n). Javlja se kada je polje već sortirano.

kako spojiti Word dokumente 2016

Povezano: Što je oznaka Big-O?

Prosječna složenost algoritma sortiranja mjehurića po vremenu je O (n^2). To se događa kada su elementi niza u zbrkanom redoslijedu.

Pomoćni prostor potreban za algoritam sortiranja mjehurića je O (1).

C ++ Implementacija algoritma za sortiranje mjehurića

Ispod je C ++ implementacija algoritma Bubble Sort:

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


Izlaz:

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

Python implementacija algoritma za sortiranje mjehurića

Ispod je Python implementacija algoritma Bubble Sort:

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


Izlaz:

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

Povezano: Kako koristiti For Loops u Pythonu

C Implementacija algoritma za sortiranje mjehurića

Ispod je C implementacija Bubble Sort algoritma:

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

Izlaz:

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

JavaScript implementacija algoritma za sortiranje mjehurića

U nastavku je JavaScript implementacija algoritma 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);


Izlaz:

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

Sada razumijete rad algoritma za sortiranje mjehurića

Sortiranje mjehurićima je najjednostavniji algoritam sortiranja i uglavnom se koristi za razumijevanje temelja sortiranja. Sortiranje mjehurićima također se može implementirati rekurzivno, ali ne pruža dodatne prednosti za to.

Pomoću Pythona možete s lakoćom implementirati algoritam sortiranja mjehurića. Ako niste upoznati s Pythonom i želite započeti svoje putovanje, početak sa 'Hello World' skriptom je izvrstan izbor.

Udio Udio Cvrkut E -pošta Kako započeti s Pythonom pomoću skripte 'Hello World'

Python je jedan od najpopularnijih programskih jezika koji se danas koristi. Slijedite ovaj vodič da biste započeli s prvom Python skriptom.

Pročitajte Dalje Povezane teme

• Programiranje
• Java
• Piton
• Vodiči za kodiranje

O autoru Yuvraj Chandra(Objavljeno 60 članaka)

Yuvraj je student preddiplomskog studija Računarstva na Sveučilištu u Delhiju u Indiji. Oduševljen je Full Stack web razvojem. Kad ne piše, istražuje dubinu različitih tehnologija.

instaliraj google play store na tabletu fire

Više od Yuvraja Chandre

Pretplatite se na naše obavijesti

Pridružite se našem biltenu za tehničke savjete, recenzije, besplatne e -knjige i ekskluzivne ponude!

Kliknite ovdje za pretplatu