Bubble Sort Algorithm

I den här handledningen lär du dig hur bubblasortering fungerar. Du hittar också arbetsexempel på bubblasortering i C, C ++, Java och Python.

Bubblesortering är en algoritm som jämför de intilliggande elementen och byter positioner om de inte är i den avsedda ordningen. Ordningen kan vara stigande eller fallande.

Hur fungerar Bubblesortering?

Med utgångspunkt från det första indexet, jämför det första och det andra elementet. Om det första elementet är större än det andra elementet byts de ut.
Jämför nu det andra och det tredje elementet. Byt dem om de inte är i ordning.
Ovanstående process fortsätter tills det sista elementet. Jämför de intilliggande elementen
Samma process pågår för återstående iterationer. Efter varje iteration placeras det största elementet bland de osorterade elementen i slutet.
I varje iteration sker jämförelsen fram till det senaste osorterade elementet.
Matrisen sorteras när alla osorterade element placeras på rätt position. Jämför de intilliggande elementen Jämför de intilliggande elementen Jämför de intilliggande elementen

Bubble Sort Algorithm

 bubbleSort (array) för i rightElement swap leftElement och rightElement end bubbleSort

Python, Java och C / C ++ exempel

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

Optimerad bubbelsortering

I ovanstående kod görs alla möjliga jämförelser även om arrayen redan är sorterad. Det ökar utförandetiden.

Koden kan optimeras genom att en extra variabel byts ut. Om det inte sker någon byte efter varje iteration, finns det inget behov av att utföra ytterligare slingor.

I ett sådant fall är variabelbyte satt som falskt. Således kan vi förhindra ytterligare iterationer.

Algoritm för optimerad bubblasortering är

 bubbleSort (array) bytt <- falskt för i rightElement swap leftElement och rightElement swapped <- true end bubbleSort

Optimerade exempel på bubblasortering

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

Komplexitet

Bubble Sort är en av de enklaste sorteringsalgoritmerna. Två slingor implementeras i algoritmen.

Cykel	Antal jämförelser
1: a	(n-1)
2: a	(n-2)
3: e	(n-3)
….	…
sista	1

Antal jämförelser: (n - 1) + (n - 2) + (n - 3) + … + 1 = n (n - 1) / 2 är nästan lika med n ²

Komplexitet: O (n ² )

Vi kan också analysera komplexiteten genom att helt enkelt observera antalet slingor. Det finns två slingor så komplexiteten ärn*n = n²

Tidskomplexitet:

Värstfallskomplexitet: Om vi vill sortera i stigande ordning och matrisen är i fallande ordning inträffar det värsta fallet.O(n²)
Bästa fallkomplexitet:O(n)
Om matrisen redan är sorterad behöver det inte sorteras.
Genomsnittlig fallkomplexitet: Det inträffar när elementen i matrisen är i rörlig ordning (varken stigande eller fallande).O(n²)