Bubble Sort Algorithm

Do you ever think how the sorting option of our mobile or computer works? Interesting thing, right? Let’s Dig in. There are many sorting algorithms. In this series, we will learn few of these.

 

At the beginning of our journey of learning sorting algorithm, we will learn the very basic sorting algorithm, named Bubble Sort.

 

For our discussion, we will assume that we are sorting an array in ascending order (i.e. small to large). The main logic of bubble sort algorithm is:

• Take first two element.
• Check if they are sorted or not (i.e. first element is smaller than the second element)
• If they are sorted, then go for 2^nd & 3^rd & repeat the process
• If they are not sorted, then swap them. Now, as the first two element are sorted between them, now go for 2^nd & 3^rd element & repeat the process from step 2.

 

Easy right? But for computer, we have to write this in computer’s language. I don’t know which language do you use for programming. So, I am showing you the Algorithm. By following the Algorithm, you can write a code in any language, you want to use.

 

Algorithm Bubble Sort (array[], n)

//array [n] is an unsorted array of size n.

1. Start
2. Repeat for i=1 to n
3. {
4. Repeat for j=1 to n-i
5. {
6. if(array[j]>array[j+1])
7. {
8. array[j] = array[j] + array[j+1];
9. array[j+1] = array[j] – array[j+1];
10. array[j] = array[j] – array[j+1];
11. }  //End of if structure
12. } // End of inner loop
13. } // End of outer loop

Now, let me explain the algorithm. For this, let guess a array as follows:

58, 22, 19, 7, 36, 15, 27, 78

For this array: n=8.

First loop of step no 2, it will repeat 8 times from 1 to 8. Let’s dig in the second loop. This loop condition is (n-i). This is because every time we will reject the last element. I will tell you the reason after a few words. The if condition in the inner loop is actually a swap function. It will interchange the two element, if the first one is bigger than is the second one. So, after the inner loop repeated from 1 to (n-i)=(8-1)=7,  and it will swap the elements if applicable, our array will look like this:

22, 19, 7, 36, 15, 27, 18, 58

If you observe the array now, you can see, the largest element is placed at the last. So, for saving our time, we can skip this in the next step. That’s why the condition of the second loop is (n-i). Because in each step, we will be able to skip one element from right as it is placed in right position. After completion of the process will have the array sorted:

7, 15, 18, 19, 22, 27, 36, 58

If you want to sort the array in descending order then just replace the ‘>‘ sign of the if condition by ‘<‘. If you have any question, feel free ask in the comment section.

 

As you the Bubble Sort now, try to solve these problems using bubble sort technique. It will help you to improve your skill.

1. UVA 12004
2. UVA 299

Code

Before seeing this code ensure that you have tried hard most!!!

Please be honest with yourself. Happy coding.

 

#include

int main()
{
    int i,j;
    int n;

    scanf("%d", &n);
    int array[n];

    for(i=0; i<n; i++)
        scanf("%d", &array[i]);

    for(i=0; i<n-1; i++)
    {
        for(j=0; jarray[j+1])
            {
                array[j] = array[j] + array[j+1];
                array[j+1] = array[j] - array[j+1];
                array[j]= array[j] - array[j+1];
            }
        }

    }
    for(i=0; i<n; i++)
    {
        printf("%d\t", array[i]);
    }
    printf("\n");

    return 0;
}