Bubble Sort

Bubble Sort

Bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.

•  Bubble sort with n element required n – 1 passes.

Example:

First Pass: 

( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1. 

( 1 5 4 2 8 ) –>  ( 1 4 5 2 8 ), Swap since 5 > 4 

( 1 4 5 2 8 ) –>  ( 1 4 2 5 8 ), Swap since 5 > 2 

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass: 

( 1 4 2 5 8 ) –> ( 1 4 2 5 8 ) 

( 1 4 2 5 8 ) –> ( 1 2 4 5 8 ), Swap since 4 > 2 

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

( 1 2 4 5 8 ) –>  ( 1 2 4 5 8 ) 

Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass: 

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

( 1 2 4 5 8 ) –> ( 1 2 4 5 8 ) 

Advantages of the Bubble Sort:

• The bubble sort requires very little memory other than that which the array or list itself occupies. 
• The bubble sort is comprised of relatively few lines of code. 
• With a best-case running time of O(n), the bubble sort is good for testing whether or not a list is sorted or not. Other sorting methods often cycle through their whole sorting sequence, which often have runningtimes of O(n^2) or O(n log n) for this task. 
• The same applies for data sets that have only a few items that need to be swapped a few times.
• The space requirement is at a minimum.

Disadvantages of the Bubble Sort: 

•  The main disadvantage of the bubble sort method is the time it requires. With a running time of  O(n^2), it is highly inefficient for large data sets.
• Additionally, the presence of turtles can severely slow the sort. 
• The bubble sort is mostly suitable for academic teaching but not for real-life applications.

Bubble Sort Complexity: 

Best :O(n²)

Worst: O(n²)

Average: O(n²)

Space Complexity: O(1)

Stability :Yes

CODE:

1. #include<stdio.h>
2.     int swap_cnt, comp_cnt;
3.     void bubble_sort(int a[20], int n)
4.     {
5.         int i, temp, pass;
6.         comp_cnt=0, swap_cnt=0;
7.         for(pass=1; pass<n; pass++)
8.         {
9.     for(i=0; i<=n-pass-1; i++)
10.     {
11.         comp_cnt++;
12.         if(a[i]>a[i+1])
13.         {
14.             swap_cnt++;
15.     temp=a[i];
16.     a[i]=a[i+1];
17.     a[i+1]=temp;
18.         }//if
19.             }//inner for
20.         }//outer for
21.     }//function
22. 
    
23. void main()
24. {
25.     int a[20], n, i;
26.     printf("\n How Many Number In Array=");
27.     scanf("%d",&n);
28.     printf("Enter a element of array:");
29. for(i=0; i<n; i++)
30. scanf("%d", &a[i]);
31.     bubble_sort(a, n);
32.     printf("\n >>Sorted Element Are<< \n");
33. for(i=0; i<n; i++)
34. printf("%d\t", a[i]);
35.     printf("\n Number of comp_cnt are: %d \n", comp_cnt);
36.     printf("\n Number of swap_cnt are: %d \n", swap_cnt);
37. }

👉Execute👈

//Output

/*

 How Many Number In Array=4

Enter a element of array:9

81

4

3

 >>Sorted Element Are<< 

3 4 9 81

 Number of comp_cnt are: 6 

 Number of swap_cnt are: 5 

*/

EXPLANATION:

- The function is called with an array of integers, n, and it sorts the elements in that array.

- It starts by setting comp_cnt to 0 and swap_cnt to 0.

- Then it has two for loops inside the function: one for each pass through the loop.

- Inside these inner loops, comp_cnt is incremented every time there's a comparison between two numbers (a[i]>a[i+1]).

- If this happens, then swap_cnt is also incremented because there was a swap in the previous iteration of the outer loop.

- After all comparisons are done, temp=a[i]; a[i]=a[i+1]; and a[i+1]=temp; are executed so that they can be used later on when swapping values back into their original places in memory.

- The main() function first creates an integer array named "n" which will hold 20 integers (0-19).

- Next it creates an integer variable named "comp_cnt" which will count how many times swaps have been made during each pass through the bubble sort function using nested for loops within itself as well as outside of itself (the outer loop iterates over 20- The code attempts to sort an array of integers.

- The function bubble_sort() will be called 20 times, with the input being a single integer that is the number of elements in the array.

- The first line declares two variables, comp_cnt and swap_cnt.

- These variables are used to keep track of how many times each side has been swapped during the sorting process.

- The next line calls a function named bubble_sort().

- This function takes one argument, which is an array of integers that contains 20 elements.

- It also takes one variable, n, which is the number of elements in this particular array.

- After calling bubble_sort(), comp_cnt and swap_cnt are initialized to 0 and

                                                                                  //ThE ProFessoR