C Program To Perform Bubble Sort

It is also called as sinking sort.  It works by scanning entries from left to right, comparing each adjacent keys and swap them if the keys are in out of order.  For each iteration, the largest key in the current list will be moved to the end and the remaining keys might be in out of order.  So, repeat the pass until all the elements in the given list are sorted.

Example:    100    1    75     2   50

Iteration 1:
Step 1:  compare adjacent keys (100 and 1)
     | 100 |   1  |  75   2    50
   100 > 1 (So, swap them)
    |  1  | 100  | 75   2    50

Step 2: Compare 100 and 75
   1 |  100 | 75  | 2    50
   100 > 75 (So, swap them)
   1 |  75   | 100 | 2    50

Step 3:  Compare 100 and 2
   1     75   | 100 | 2  |  50
   100 > 2 (So, swap them)
   1     75   |  2   | 100 | 50

Step 4:  Compare 100 and 50
    1    75     2     | 100 | 50 |
   100 > 50 (So, swap them)
   1     75     2     |  50  |  100 |

At the end of 1st iteration, the largest element of current list is placed at right position.

Output:
|     |      |     |      |  100 |

Iteration 2:
Elements needs to processed for iteration 2:     1   75    2    50
Step 1: Compare adjacent keys (1 and 75)
| 1  | 75  |  2   50
1 < 75 (no need of swap)

Step 2: Compare 75 and 2
 1   | 75 |  2 | 50
75 > 2 (So, swap them)
1   | 2  |  75 | 50

Step 3: Compare 75 and 50
1    2   | 75  | 50 |
 75 > 50 (So, swap them)
1    2   | 50  | 75 |

Output:
| 1 | 2   | 3   | 75 | 100 |

All the elements in the list are sorted.  So, no need of further processing.

See Also:

C Program To Perform Insertion Sort

C Program To Perform Shell Sort

C Program To Perform Bubble Sort

C Program To Perform Quick Sort

C Program To Perform Radix Sort

C Program To Perform Selection Sort

C Program To Perform Heap Sort

C Program To Perform Merge Sort

C Program To Perform External Sorting

C Program To Perform Sorting Using Binary Search Tree

Example Program For Bubble Sort:

---

  #include <stdio.h>
  #include <stdlib.h>
  int main() {
        int i, n, num, temp, changed, *data;
        printf("Bubble Sort Example\n");
        printf("Enter ur no of entries:");
        scanf("%d", &num);
        data = (int *)malloc(sizeof (int) * n);
        /* get the inputs from user */
        for (i = 0; i < num; i++)
                scanf("%d", &data[i]);
        n = num-1;
        while (n > 0) {
                changed = 0;
                for (i = 1; i <= n; i++) {
                        /*
                         * compare adjacent keys and swap them
                         * if they are found to be out of order.
                         */
                        if(data[i-1] > data[i]) {
                                temp = data[i];
                                data[i] = data[i-1];
                                data[i-1] = temp;
                                changed = 1;
                        }
                }
                if (!changed)
                        break;
                /*
                 * for each iteration, last element will get
                 * sorted. So, we will ignore it for further
                 * processing
                 */
                n--;
        }
        printf("Sorted data: ");

        for (i = 0; i < num; i++)

                printf("%3d ", data[i]);

        printf("\n");

        return 0;

  }

 Output: (C Program For Bubble Sorting)

  jp@jp-VirtualBox:$ ./a.out
  Bubble Sort Example
  Enter ur no of entries:5
  100 1 75 2 50
  Sorted data:   1   2  50  75 100