Sorting Arrays: Bubble Sort ( C Program, Java Program source code, a tutorial explaining the Algorithm and an MCQ Quiz)

Computer Science‎ > ‎

Sorting Arrays: Bubble Sort ( C Program, Java Program source code, a tutorial explaining the Algorithm and an MCQ Quiz)

Basic Sorting and Searching Algorithms for Arrays, at a glance

Bubble Sort(You are here)

Insertion Sort

Quick Sort

Binary Search Algorithm

To go through the C program / source-code, scroll down to the end of this page

Bubble Sort

It’s a sorting algorithm, in which each pair of adjacent items are compared and swapped if they are in wrong order. The comparison is repeated until no swaps are needed, indicating that the list is sorted. The smaller elements ‘bubble’ to the top of the list, hence, the name Bubble Sort. In this like selection sort, after every pass the largest element moves to the highest index position of the list.

Algorithm:

It starts with the first element of the list. The comparison of the adjacent pair of elements and swapping is done until the list is sorted as follows

1. Compare two adjacent elements and check if they are in correct order (that is second one has to be greater than the first).

2. Swap them if they are not in correct order.

Let iter denotes the number of iterations, then for iter ranging from 1 to n-1 (where n is total number of elements in the list) check

1. If value of the second item at position iter is lesser than the value of the first item i.e. at position iter-1, then swap them.

2. Else, move to the next element at position iter+1.

The effective size of the list is hence reduced by one after every pass and the largest element is moved to its final position in the sorted array. Repeat the two steps until the list is sorted and no swap is required i.e. the effective size is reduced to 1.

To see a Java Applet Visualization of the Bubble Sort Mechanism, click on the image below :

The gadget spec URL could not be found

Properties:

1. Best Case performance – When the list is already sorted, we require only one pass to check, hence O(n).

2. Worst Case performance – When the list is in the reverse order, n number of comparisons and swap are required to be done n number of times, hence O(n2).

3. Average Case performance – O(n2)

4. It does not require any extra space for sorting, hence O(1) extra space.

Complete Tutorial with example :

Bubble Sort - C Program Source Code

#include<stdio.h>
/* Logic : Do the following thing until the list is sorted
            (i) Compare two adjacent elements and check if they are in correct order(that is second one has
                to be greater than the first). 
            (ii) Swap them if they are not in correct order.
 */ 
void BubbleSort(int *array,int number_of_elements)
{
        int iter, temp, swapped;
        do
        {
                swapped = 0; /* If no element is swapped array is sorted */
                /* In the following loop compare every pair of adjacent elements and check
                   if they are in correct order */
                for(iter = 1; iter < number_of_elements; iter++)
                {
                        if(array[iter-1] > array[iter])
                        {
                                temp = array[iter-1];
                                array[iter-1] = array[iter];
                                array[iter] = temp;
                                swapped = 1;
                        }
                }

        }while(swapped);
}
int main()
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements]; 
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        BubbleSort(array,number_of_elements); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;

}

Bubble Sort- Java Program Source Code

Post to LiveJournal
/* Logic : Do the following thing until the list is sorted
            (i) Compare two adjacent elements and check if they are in correct order(that is second one has
                to be greater than the first). 
            (ii) Swap them if they are not in correct order.
 */ 
import java.io.*;
 public class BubbleSort
{
void BubbleSort(int array[],int number_of_elements)
{
        int iter, temp, swapped;
        do
        {
                swapped = 0; /* If no element is swapped array is sorted */
                /* In the following loop compare every pair of adjacent elements and check
                   if they are in correct order */
                for(iter = 1; iter < number_of_elements; iter++)
                {
                        if(array[iter-1] > array[iter])
                        {
                                temp = array[iter-1];
                                array[iter-1] = array[iter];
                                array[iter] = temp;
                                swapped = 1;
                        }
                }

        }while (swapped!=0);
}
int main()throws IOException
{
    BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        System.out.println("Enter the number of elements");
        int number_of_elements;
        number_of_elements=Integer.parseInt(in.readLine());
        int array[]=new int[number_of_elements]; 
        int iter;
        System.out.println("Enter the elements one by one");
        for(iter = 0;iter < number_of_elements;iter++)
        {
           array[iter]=Integer.parseInt(in.readLine());
        }
        /* Calling this functions sorts the array */
        BubbleSort(array,number_of_elements); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
                System.out.print(array[iter]+"\t");
        }
        System.out.print("\n");
        return 0;

}
}

MCQ Quiz: The Basics of Sorting Algorithms- Quadratic Sorts: Check how much you know about Quadratic Time Sorting Algorithms

Your score will be e-mailed to the address filled up by you.

MCQ Quiz #1: Quadratic Time Sorting Algorithms
Google Spreadsheet Form

Related Tutorials :

Bubble Sort

One of the most elementary sorting algorithms to implement - and also very inefficient. Runs in quadratic time. A good starting point to understand sorting in general, before moving on to more advanced techniques and algorithms. A general idea of how the algorithm works and a the code for a C program.

Insertion Sort

Another quadratic time sorting algorithm - an example of dynamic programming. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs insertion sort.

Selection Sort

Another quadratic time sorting algorithm - an example of a greedy algorithm. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs selection sort.

Shell Sort

An inefficient but interesting algorithm, the complexity of which is not exactly known.

Merge Sort

An example of a Divide and Conquer algorithm. Works in O(n log n) time. The memory complexity for this is a bit of a disadvantage.

Quick Sort

In the average case, this works in O(n log n) time. No additional memory overhead - so this is better than merge sort in this regard. A partition element is selected, the array is restructured such that all elements greater or less than the partition are on opposite sides of the partition. These two parts of the array are then sorted recursively.

Heap Sort

Efficient sorting algorithm which runs in O(n log n) time. Uses the Heap data structure.

Binary Search Algorithm

Commonly used algorithm used to find the position of an element in a sorted array. Runs in O(log n) time.

Testing Zone For Programmers-

Try out our online Multiple-Choice-Question tests in Programming and Computer Science!

Photo-credits: www.istockphoto.com

Quizzes on Basic Object Oriented Programming with C++

Quizzes on Java Programming

Quizzes on C Programming- Arrays, Strings and Pointers

Quizzes on Data Structures, Algorithms and Complexity

bubblesort.png

(34k)

Prashant Bhattacharji,

Oct 7, 2012, 9:44 AM

v.1

The Learning Point

Navigation

Navigation