OverIQ.com

  1. Home
  2. C Programming Examples
  3. C Program to sort an array in ascending order using Bubble Sort

C Program to sort an array in ascending order using Bubble Sort

Last updated on September 23, 2020

Bubble Sort #

Bubble sort is a simple method that sorts the elements of an array into either increasing or decreasing order. It works by comparing the adjacent elements and swapping them if they are out of order. Multiple passes through the array are necessary.

The following are the steps to sort an array of size N in ascending order using bubble sort:

Passthrough #1:

  1. Compare arr[0] with arr[1]. If arr[0] > arr[1], swap them.
  2. Compare arr[1] with arr[2]. If arr[1] > arr[2], swap them.
  3. Finally, compare a[N-2] with arr[N-1], if arr[N-2] > arr[N-1], swap them.

This completes the first passthrough.

After, the first passthrough, the highest value in the array will be at the end.

Passthrough #2:

  1. Compare arr[0] with arr[1]. If arr[0] > arr[1], swap them.
  2. Compare arr[1] with arr[2]. If arr[1] > arr[2], swap them.
  3. Finally, compare a[N-3] with arr[N-2], if arr[N-3] > arr[N-2], swap them.

This completes the second passthrough. After, this passthrough, the second highest element will be at the second highest index in the array.

Note that in the final step of the second passthrough, we are not comparing the second last element i.e a[N-2] with the last element i.e arr[N-1], this is because the last element is already in its correct position.

Passthrough #3:

  1. Compare arr[0] with arr[1]. If arr[0] > arr[1], swap them.
  2. Compare arr[1] with arr[2]. If arr[1] > arr[2], swap them.
  3. Finally, compare a[N-4] with arr[N-3], if arr[N-4] > arr[N-3], swap them.

This completes the third passthrough. After, this passthrough, the third highest element will be at the third highest index in the array.

In this way, we keep passing through the array. We stop when we encountered a passthrough that's hasn't swapped any elements.

Let's take an example.

Suppose, we have an array arr declared and initialized as:

1
2
#define SIZE 5
int arr[SIZE] = {80, 60, 90, 10, 40}; // unsorted array

Here are the steps to sort this array in increasing order using bubble sort.

Passthrough #1:

Step 1: Compare 80 and 60. Since, 80 > 60, swap them:

| 60 | 80 | 90 | 10 | 40 |

Step 2: Compare 80 and 90. Since, 80 < 90, we do nothing:

| 60 | 80 | 90 | 10 | 40 |

Step 3: Compare 90 and 10. Since, 90 > 10, swap them:

| 60 | 80 | 10 | 90 | 40 |

Step 4: Compare 90 and 40. Since, 90 > 40, swap them:

| 60 | 80 | 10 | 40 | 90 |

This completes the first passthrough. The highest element i.e 90, is now at the end of the array. We have made three swaps in this passthrough. So, we need to perform another passthrough. Keep in mind that we keep passing through the array until we encounter a passthrough that hasn't swapped any elements.

Passthrough #2:

Step 1: Compare 60 and 80. Since, 60 < 80, we do nothing:

| 60 | 80 | 10 | 40 | 90 |

Step 2: Compare 80 and 10. Since, 80 > 10, swap them:

| 60 | 10 | 80 | 40 | 90 |

Step 3: Compare 80 and 40. Since, 80 > 40, swap them:

| 60 | 10 | 40 | 80 | 90 |

This completes the second passthrough. The second highest element i.e 80, is now at the second highest index in the array. Also, note that we haven't compared 80 with 90. This is because the element 90 is already in its correct position from passthrough #1.

We have made 2 swaps in this passthrough. So, we need to perform another one.

Passthrough #3:

Step 1: Compare 60 and 10. Since, 60 > 10, swap them:

| 10 | 60 | 40 | 80 | 90 |

Step 2: Compare 60 and 40. Since, 60 > 40, swap them:

| 10 | 40 | 60 | 80 | 90 |

This completes the third passthrough. The third highest element i.e 60, is now at the third highest index in the array. Also, note that we haven't compared 60 with 80. This is because the element 80 is already in its correct position from passthrough #2.

We have made 2 swaps in this passthrough. So, we need to perform another one.

Passthrough #4:

Step 1: Compare 10 and 40. Since, 10 < 40, we do nothing:

| 10 | 40 | 60 | 80 | 90 |

This completes the fourth passthrough. We haven't made any swaps in this passthrough. So, we need don't need to perform another one. All the elements in the array are now sorted in ascending order.

Bubble Sort C Program #

The following is a C program which sorts the array in ascending order using Bubble sort algorithm:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/****************************************************************
 * Program to sort an array in ascending order using Bubble sort  
 ****************************************************************/

#include<stdio.h> // include stdio.h library
#define MAX 5
void bubble_sort(int arr[]); // function declaration

int main(void)
{        
    int arr[MAX]; 

    // input array
    for(int i = 0; i < MAX; i++)
    {
        printf("arr[%d] = ", i);    
        scanf("%d", &arr[i]);
    }

    printf("\nUnsorted array: \n");

    // print unsorted array
    for(int i = 0; i < MAX; i++)
    {
        printf("%d ", arr[i]);    
    }

    // sort array
    bubble_sort(arr);

    printf("\n\nSorted array: \n");

    // print sorted array
    for(int i = 0; i < MAX; i++)
    {
        printf("%d ", arr[i]);    
    }

    return 0; // return 0 to operating system
}

/*
 *  bubble_sort() takes an array and sorts it
 *  in the ascending order
 */

void bubble_sort(int arr[])
{
    int tmp,  // temporary variable to hold one of the values while swapping
        is_swapped; // variable to indicate whether we have made any swaps during the passthrough

    for(int i = 0; i < MAX; i++)
    {
        // re-initialize is_swapped to 0 after every passthrough       
        is_swapped = 0;  

        for(int j = 0; j < MAX - 1 - i; j++)
        {            
            if(arr[j] > arr[j+1]) // compare adjacent elements
            {
                // swap adjacent elements
                tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;

                // set is_swapped to 1, to indicate
                // that we have made at least one 
                // swap during the passthrough
                is_swapped = 1;               
            }     
        }        

        // if no swaps are made in the last passthrough,
        // exit the outer for loop

        if (!is_swapped)
        {
            break;
        }
    }        
}

Try it now

Expected Output:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
Enter array: 
arr[0] = 80
arr[1] = 60
arr[2] = 90
arr[3] = 10
arr[4] = 40

Unsorted array: 
80 60 90 10 40 

Sorted array: 
10 40 60 80 90

How it works #

All the work is done inside the bubble_sort() function:

Here is how it works:

In lines 50 and 51, we have declared two variables: tmp and is_swapped. The tmp variable will hold one of the values while swapping the elements and is_swapped is used as a flag to indicate whether we have made any swaps during the passthrough or not.

In lines 53-81, we have an outer for loop, which runs until the array is not sorted.

The inner for loop in lines 58-72, swaps out of order elements during the passthrough. It runs from the beginning of the array and goes on until the index that hasn't been sorted yet.

If we made at least one swap during the passthrough we set is_swapped to 1 (line 70).

At last, the if statement in lines 77-80, checks the value of is_swapped to determine, whether to break out of the outer for loop or not. We break out of the outer for loop when we encountered a passthrough that's hasn't swapped any elements.

Keep in mind that the above function sorts the array in increasing order. To sort elements in decreasing order, simply change the if condition in line 60 from arr[j] > arr[j+1] to arr[j] < arr[j+1].

Recommended Reading:

C Programming Examples

Recent Posts