Bubble Sort Algorithm

I denne opplæringen lærer du hvordan boblesortering fungerer. Du vil også finne eksempler på bruk av boblesorter i C, C ++, Java og Python.

Boblesortering er en algoritme som sammenligner de tilstøtende elementene og bytter plassering hvis de ikke er i den tiltenkte rekkefølgen. Rekkefølgen kan være stigende eller synkende.

Hvordan fungerer boblesortering?

Fra den første indeksen, sammenlign det første og det andre elementet. Hvis det første elementet er større enn det andre elementet, byttes det ut.
Sammenlign nå det andre og det tredje elementet. Bytt dem hvis de ikke er i orden.
Ovennevnte prosess fortsetter til det siste elementet. Sammenlign de tilstøtende elementene
Den samme prosessen fortsetter for de gjenværende iterasjonene. Etter hver iterasjon plasseres det største elementet blant de usorterte elementene på slutten.
I hver iterasjon foregår sammenligningen opp til det siste usorterte elementet.
Matrisen sorteres når alle usorterte elementene er plassert på riktig plassering. Sammenlign de tilstøtende elementene Sammenlign de tilstøtende elementene Sammenlign de tilstøtende elementene

Bubble Sort Algorithm

 bubbleSort (array) for i rightElement swap leftElement og rightElement end bubbleSort

Python, Java og C / C ++ eksempler

Python Java C C ++

 # Bubble sort in Python def bubbleSort(array): # run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Asc ending Order:') print(data)

 // Bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) for (int j = 0; j  to array(j + 1)) ( // swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; ) ) // driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Bubble sort in C #include void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i " to " array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printArray(data, size); )

 // Bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( // run loops two times: one for walking throught the array // and the other for comparison for (int step = 0; step < size - 1; ++step) ( for (int i = 0; i to array(i + 1)) ( // swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; ) ) ) ) // function to print the array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Optimalisert boblesortering

I koden ovenfor gjøres alle mulige sammenligninger selv om matrisen allerede er sortert. Det øker utførelsestiden.

Koden kan optimaliseres ved å innføre en ekstra variabel byttet. Hvis det ikke er bytting etter hver iterasjon, er det ikke behov for å utføre ytterligere sløyfer.

I et slikt tilfelle er variabelbytting satt som falsk. Dermed kan vi forhindre ytterligere iterasjoner.

Algoritme for optimalisert boblesortering er

 bubbleSort (array) byttet <- false for i rightElement swap leftElement og rightElement swapped <- true end bubbleSort

Optimaliserte boblesorteringseksempler

Python Java C C +

 # Optimized bubble sort in python def bubbleSort(array): # Run loops two times: one for walking throught the array # and the other for comparison for i in range(len(array)): # swapped keeps track of swapping swapped = True for j in range(0, len(array) - i - 1): # To sort in descending order, change> to array(j + 1): # Swap if greater is at the rear position (array(j), array(j + 1)) = (array(j + 1), array(j)) swapped = False # If there is not swapping in the last swap, then the array is already sorted. if swapped: break data = (-2, 45, 0, 11, -9) bubbleSort(data) print('Sorted Array in Ascending Order:') print(data)

 // Optimized bubble sort in Java import java.util.Arrays; class BubbleSort ( void bubbleSort(int array()) ( int size = array.length; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i < size - 1; i++) ( // swapped keeps track of swapping boolean swapped = true; for (int j = 0; j  to array(j + 1)) ( // Swap if greater is at the rear position int temp = array(j); array(j) = array(j + 1); array(j + 1) = temp; swapped = false; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == true) break; ) ) // Driver code public static void main(String args()) ( int() data = ( -2, 45, 0, 11, -9 ); BubbleSort bs = new BubbleSort(); bs.bubbleSort(data); System.out.println("Sorted Array in Ascending Order:"); System.out.println(Arrays.toString(data)); ) )

 // Optimized bubble sort in C #include void bubbleSort(int arrayay(), int size) ( for (int step = 0; step < size - 1; ++step) ( // Swapped keeps track of swapping int swapped = 0; // Run loops two times: one for walking throught the array // and the other for comparison for (int i = 0; i to arrayay(i + 1)) ( // Swap if greater is at the rear position int temp = arrayay(i); arrayay(i) = arrayay(i + 1); arrayay(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printarrayay(int arrayay(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", arrayay(i)); ) printf(""); ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); printf("Sorted Array in Ascending Order:"); printarrayay(data, size); )

 // Optimized bubble sort in C++ #include using namespace std; void bubbleSort(int array(), int size) ( for (int step = 0; step < size - 1; ++step) (

  // Run loops two times: one for walking throught the array // and the other for comparison int swapped = 0; for (int i = 0; i to array(i + 1)) ( // Swap if greater is at the rear position int temp = array(i); array(i) = array(i + 1); array(i + 1) = temp; swapped = 1; ) ) // If there is not swapping in the last swap, then the array is already sorted. if (swapped == 0) break; ) ) // Function to print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( cout << " " << array(i); ) cout << ""; ) // Driver code int main() ( int data() = (-2, 45, 0, 11, -9); int size = sizeof(data) / sizeof(data(0)); bubbleSort(data, size); cout << "Sorted Array in Ascending Order:"; printArray(data, size); )

Kompleksitet

Bubble Sort er en av de enkleste sorteringsalgoritmene. To sløyfer er implementert i algoritmen.

Syklus	Antall sammenligninger
Første	(n-1)
2. plass	(n-2)
3.	(n-3)
….	…
siste	1

Antall sammenligninger: (n - 1) + (n - 2) + (n - 3) + … + 1 = n (n - 1) / 2 er nesten lik n ²

Kompleksitet: O (n ² )

Vi kan også analysere kompleksiteten ved å bare observere antall løkker. Det er to sløyfer så kompleksiteten ern*n = n²

Tidskompleksiteter:

Verste sakskompleksitet: Hvis vi vil sortere i stigende rekkefølge og matrisen er i synkende rekkefølge, oppstår det verste tilfellet.O(n²)
Best case-kompleksitet:O(n)
Hvis matrisen allerede er sortert, er det ikke behov for sortering.
Gjennomsnittlig sakskompleksitet: Det oppstår når elementene i matrisen er i rotet rekkefølge (verken stigende eller synkende).O(n²)