Boblesorteringsalgoritme

I denne vejledning lærer du, hvordan boblesortering fungerer. Du finder også arbejdseksempler på boblesortering i C, C ++, Java og Python.

Boblesortering er en algoritme, der sammenligner de tilstødende elementer og bytter deres positioner, hvis de ikke er i den tilsigtede rækkefølge. Rækkefølgen kan være stigende eller faldende.

Hvordan fungerer Bubblesortering?

Start med det første indeks, sammenlign det første og det andet element. Hvis det første element er større end det andet element, byttes det.
Sammenlign nu det andet og det tredje element. Byt dem, hvis de ikke er i orden.
Ovenstående proces fortsætter indtil det sidste element. Sammenlign de tilstødende elementer
Den samme proces fortsætter for de resterende iterationer. Efter hver iteration placeres det største element blandt de usorterede elementer i slutningen.
I hver iteration finder sammenligningen sted indtil det sidste usorterede element.
Arrayet sorteres, når alle usorterede elementer placeres på deres korrekte positioner. Sammenlign de tilstødende elementer Sammenlign de tilstødende elementer Sammenlign de tilstødende elementer

Boblesorteringsalgoritme

 bubbleSort (array) til 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); )

Optimeret boblesortering

I ovenstående kode foretages alle mulige sammenligninger, selvom arrayet allerede er sorteret. Det øger udførelsestiden.

Koden kan optimeres ved at indføre en ekstra variabel byttet. Efter hver iteration er der ikke behov for at udføre yderligere sløjfer, hvis der ikke finder sted nogen bytte.

I et sådant tilfælde er variabelbyttet sat som falsk. Således kan vi forhindre yderligere iterationer.

Algoritme til optimeret boblesortering er

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

Eksempler på optimerede boblesortering

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 af de enkleste sorteringsalgoritmer. To sløjfer er implementeret i algoritmen.

Cyklus	Antal sammenligninger
1.	(n-1)
2. plads	(n-2)
3.	(n-3)
….	…
sidst	1

Antal sammenligninger: (n - 1) + (n - 2) + (n - 3) +… + 1 = n (n - 1) / 2 svarer næsten til n ²

Kompleksitet: O (n ² )

Vi kan også analysere kompleksiteten ved blot at observere antallet af sløjfer. Der er 2 sløjfer, så kompleksiteten ern*n = n²

Tidskompleksiteter:

Worst Case-kompleksitet: Hvis vi vil sortere i stigende rækkefølge, og arrayet er i faldende rækkefølge, forekommer det værste tilfælde.O(n²)
Bedste tilfælde af kompleksitet:O(n)
Hvis arrayet allerede er sorteret, er der ikke behov for sortering.
Gennemsnitlig sagskompleksitet: Det sker, når elementerne i arrayet er i sammenblandet rækkefølge (hverken stigende eller faldende).O(n²)