User Name:


User Email:




This information will only be saved for the purposes of communicating with those who have provided this information voluntarily regarding our services.We will never sell your name or email address to anyone.
© 2018 - First Crazy Developer (Abhishek Kumar)
  

crazydeveloper Bubble Sort - Sorting Algorithm

Bubble Sorting

In application development there are lot of scenario comes when we need to sorting our listed or arrays data. Provided list or array can be n number size. So when we write a code to sorting that data, we should consider the most efficient way to do that, because that process impact on your application performance base on time & space complexity. So for that you'll need a sorting algorithm. To understand the more complex and efficient sorting algorithms, it's important to first understand the simpler, but slower algorithms.


The simplest sorting algorithm is Bubble Sort. The Bubble Sort works by iterating  down an array to be sorted from the first element to the last, comparing each pair of elements and switching their positions if necessary. This process makes multiple passes through a list, until the array is sorted.

It is used to sort N elements that are given in a memory for eg: an Array with N  number of elements. Bubble Sort compares all the element one by one and sort  them based on their values.

It is called Bubble Sort, because with each iteration the smaller element in the list bubbles up towards the first place, just like a water bubble rises up to the water surface.

After above statements we can say that Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

Example:


First Pass:
( 7 1 6 2 4 3) –> ( 1 7 6 2 4 3 ), Here, algorithm compares the first two elements, and swaps since 7 > 1.
( 1 7 6 2 4 3 ) –>  ( 1 6 7 2 4 3 ), Swap since 7 >6
( 1 6 7 2 4 3 ) –>  ( 1 6 2 7 4 3 ), Swap since 7 > 2
( 1 6 7 2 4 3 ) –>  ( 1 6 2 4 7 3 ), Swap since 7 > 4
( 1 6 2 4 7 3 ) –>  ( 1 6 2 4 3 7 ), Swap since 7 > 3

Now after complete first iteration our updated array
( 1 6 2 4 3 7 )

Second Pass:
( 1 6 2 4 3 7 ) –> ( 1 6 2 4 3 7 )
( 1 6 2 4 3 7 ) –> ( 1 2 6 4 3 7 ), Swap since 6 > 2
( 1 2 6 4 3 7 ) –> ( 1 2 4 6 3 7 ), Swap since 6 > 4
( 1 2 4 6 3 7 ) –> ( 1 2 4 3 6 7 ) ,Swap since 6 > 3
( 1 2 4 3 6 7 ) --> ( 1 2 4 3 6 7 )

Now after complete second iteration our updated array
( 1 2 4 3 6 7 )

Third Pass:
( 1 2 4 3 6 7 ) –> ( 1 2 4 3 6 7 )
( 1 2 4 3 6 7 ) –> ( 1 2 4 3 6 7 )
( 1 2 4 3 6 7 ) –> ( 1 2 3 4 6 7 ) Swap since 4 > 3
( 1 2 3 4 6 7 ) --> ( 1 2 3 4 6 7 )
( 1 2 3 4 6 7 ) –> ( 1 2 3 4 6 7 )

Bubbule Sorting


This iteration is going on till six iteration to complete this sorting. Now look the  
following code:

 1: int unsortedArray[6] = {7, 1, 6, 2, 4, 3};
 2: int i, j, temp;
 3: for(i=0; i<6, i++)
 4: {
 5:   for(j=0; j<6-i-1; j++)
 6:   {
 7:     if( unsortedArray[j] > unsortedArray[j+1])
 8:     {
 9:       temp = a[j];
 10:       unsortedArray[j] = unsortedArray[j+1];
 11:       unsortedArray[j+1] = temp;
 12:     }
 13:   }
 14: }



In above code is the algorithm, to sort array with Bubble Sort. But when we go through the complete process we feel that above algorithm is not efficient and we can modified to make more efficient. Because in above algorithm our iteration will keep going for six times even it the array get sorted the third pass.

So we think about to make this algorithm more efficient. What should we do for this problems? Any guess....

Just again go through complete flow and check the complete process. We got that if any iteration whether swapping of elements is not happening it means that array is aleady sorted. What we do, insert a flag to keep watching whether swapping of elements is taking place or not. If not then we break the for loop & jump out.

Now look the update code base on modified algorithm:

 1: int unsortedArray[6] = {7, 1, 6, 2, 4, 3};
 2: int i, j, temp;
 3: for(i=0; i<6, i++)
 4: {
 5:   for(j=0; j<6-i-1; j++)
 6:   {
 7:     int flag = 0;        //taking a flag variable
 8:     if( unsortedArray[j] > unsortedArray[j+1])
 9:     {
 10:       temp = unsortedArray[j];
 11:      unsortedArray[j] = unsortedArray[j+1];
 12:       unsortedArray[j+1] = temp;
 13:       flag = 1;         //setting flag as 1, if swapping occurs
 14:     }
 15:   }
 16:   if(!flag)             //breaking out of for loop if no swapping takes place
 17:   {
 18:     break;
 19:   }
 20: }


In the above code, if in a complete single cycle of j iteration (inner for loop), no swapping takes place, and flag remains 0, then we will break out of the for loops, because the array has already been sorted.

Final algorithm:

 1: for i = 1:n,
 2:     swapped = false
 3:     for j = n:i+1,
 4:         if a[j] < a[j-1],
 5:             swap a[j,j-1]
 6:             swapped = true
 7:     → invariant: a[1..i] in final position
 8:     break if not swapped
 9: end




Final Output of Bubble Sorting:

  • Stable: Yes
  • Auxiliary Space: O(1) extra space
  • Time Complexity: O(n2) comparisons and swaps
  • Boundary Cases: O(n) when nearly sorted

   
   
Note:- Bubble Sort [Best: O(n), Worst:O(N^2)]


crazydeveloper Home Page 26 June 2015

Become a Fan