Bubble sort definition

Bubble sort compares the value of current node with the immediate next node and swaps according to the requirement and goes till the last element.

bubble sort bubbles

Compare and swapping two elements like small soap bubbles and hence the name given as bubble sort.

Bubble sort Big(o)

Bubble sort of N elements can take (N - 1) steps and (N -1) iterations in each steps. Thus resultant is (N - 1)*(N - 1). This sorting algorithm is not however the best in performance when count of the elements are large. Time complexities of bubble sort is Big(o) = N^2 [Square of N]. This sorting is well suited for small number of elements and it is easy the implement in C or any other programming languages.

Bubble sort source code

Here is a C source code of Bubble sorting with 5 integer elements. This code sorts the elements in ascending order.

#include <stdio.h>
void swap_node(int *x, int *y)
{
  int tmp;
  tmp = *x;
  *= *y;
  *= tmp;
}
void bubble_sort(int elements[], int count)
10  {
11    int step, index;
12    printf("Bubble sort started-\n");
13    for (step = 0; step < count - 1; step++)
14    {
15      printf("==== Step %d ====\n", step+1);
16      print_array(elements, 5);
17      for(index = 0; index < (count - step - 1); index++)
18      {
19        printf("#%d ", index+1);
20        if (elements[index] > elements[index + 1])
21        {
22          printf(" swap %d > %d\n",
23                 elements[index],
24                 elements[index + 1]);
25          swap_node(&elements[index],
26                     &elements[index + 1]);
27        } else
28        {
29          printf("no swap %d <= %d\n",
30                 elements[index],
31                 elements[index + 1]);
32        }
33        print_array(elements, 5);
34      }
35    }
36    printf("Bubble sort ended\n");
37    
38  }
39  void print_array(int array[], int count)
40  {
41    int i;
42    printf("[");
43    for(= 0; i < count; i++)
44      printf("%d, ", array[i]);
45    printf("\b\b]\n");
46  }
47  int main(int argc, char *argv[])
48  {
49    int array[5] = { 4, 9, 5, 1, 0 };
50    printf("Unsorted elements\n");
51    print_array(array, 5);
52    bubble_sort(array, 5);
53    printf("Bubble sorted elements\n");
54    print_array(array, 5);
55  }
56 

Steps and Iterations (diagrams)

bubble sort step1 iteration stages

bubble sort step2 iteration stages

bubble sort step3 iteration stages

bubble sort step4 iteration stages

Output

Unsorted elements
[4, 9, 5, 1, 0]                                                                                                                         
Bubble sort started-                                                                                                                    
==== Step 1 ====                                                                                                                        
[4, 9, 5, 1, 0]                                                                                                                         
#1 no swap  4 <= 9                                                                                                                      
[4, 9, 5, 1, 0]                                                                                                                         
#2    swap  9 >  5                                                                                                                      
[4, 5, 9, 1, 0]                                                                                                                         
#3    swap  9 >  1                                                                                                                      
[4, 5, 1, 9, 0]                                                                                                                         
#4    swap  9 >  0                                                                                                                      
[4, 5, 1, 0, 9]                                                                                                                         
==== Step 2 ====                                                                                                                        
[4, 5, 1, 0, 9]                                                                                                                         
#1 no swap  4 <= 5                                                                                                                      
[4, 5, 1, 0, 9]                                                                                                                         
#2    swap  5 >  1                                                                                                                      
[4, 1, 5, 0, 9]                                                                                                                         
#3    swap  5 >  0                                                                                                                      
[4, 1, 0, 5, 9]                                                                                                                         
==== Step 3 ====                                                                                                                        
[4, 1, 0, 5, 9]                                                                                                                         
#1    swap  4 >  1                                                                                                                      
[1, 4, 0, 5, 9]                                                                                                                         
#2    swap  4 >  0                                                                                                                      
[1, 0, 4, 5, 9]                                                                                                                         
==== Step 4 ====                                                                                                                        
[1, 0, 4, 5, 9]                                                                                                                         
#1    swap  1 >  0                                                                                                                      
[0, 1, 4, 5, 9]                                                                                                                         
Bubble sort ended                                                                                                                       
Bubble sorted elements                                                                                                                  
[0, 1, 4, 5, 9]

You have viewed 1 page out of 248. Your C learning is 0.00% complete. Login to check your learning progress.

 Vote 0

Similar topics related to this section

Linear Search, Binary Search, Hash Table, Sorting, Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Heap Sort,

# C Programming Language (Prentice Hall Software)
# Let Us C Paperback - 2006 by Yashavant Kanetkar
# Understanding and Using C Pointers Core techniques for memory management
# Data Structures Using C and C++ Paperback - 1998
# Data Structures In C Paperback - August 11, 2008 by Noel Kalicharan