Bubble sorting algorithm with Bubble sort program in C

Bubble sort is a simple sorting method to sorts the array elements. In the bubble sorting technique each array element is compared to the adjacent elements of the array. If the lower index value is greater than the highest index position of the array then swap these two adjacent values to maintain ascending sorting order.

This process will continue till the element is available in an array.
In the first pass, the largest element of the array will be placed at its proper
position means at the end of the list.

A bubble sorting algorithm is not suitable for large data sets because average time complexity and worst-case time complexity are of Ο(n2) where n is the number of items.

How Bubble Sorting works

Suppose we have an array arr of size n.

• In first pass elements, arr[0] and arr[1] are compared, and then arr[1] is compared with arr[2], arr[2] is compared with
  arr[3], and so on. At last arr[n–2] is compared with arr[n–1]. In pass 1 the biggest element will be positioned at the highest index of the array which is its actual position.
• In second pass elements arr[0] and arr[1] are compared, then arr[1] is compared with arr[2], arr[2] is compared with
  arr[3], and so on. At last arr[n–3] is compared with arr[n–2]. In pass 2 the second biggest element will be at the second highest index of the array which is its actual position.
• In third pass elements arr[0] and arr[1] are compared, then arr[1] is compared with arr[2], arr[2] is compared with
  arr[3], and so on. At last arr[n–4] is compared with arr[n–3]. In pass 3 the third biggest element will be at the third highest index of the array which is its actual position.
• In fourth pass elements arr[0] and arr[1] are compared, then arr[1] is compared with arr[2], arr[2] is compared with
  arr[3], and so on. At last arr[n–5] is compared with arr[n–4]. In pass 3 the fourth biggest element will be at the fourth highest index of the array which is its actual position.
• In n–1 Pass elements arr[0] and arr[1] are compared so that arr[0]<arr[1]. After this step, all the array elements will be sorted in ascending order.

Algorithm of Bubble sort

begin BubbleSort(arr, n)
for I=0 to N-1
    for J=0 to N-I
         if arr[j] > arr[j+1]
             swap(arr[j], arr[j+1])
         end if
     end for
end for
return arr
end BubbleSort

Bubble sort time complexity

Best-case performance O(n) comparisons, O(1) swaps
Average performance О(n2) comparisons and swaps
Worst-case performance О(n2) comparisons and swaps

Bubble sort program in C

#include<stdio.h>
#include<conio.h>

void main(){
    int arr[100],i,j,n,key;
    printf("Enter the number of elements you want to sort:\n");
    scanf("%d",&n);
    printf("Now enter the %d elements you want to sort: \n",n);
    for(i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    printf("before sorting:\n");
    for(i=0;i<n;i++){
        printf("%d \t",arr[i]);
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n-i-1;j++){
            if(arr[j]>arr[j+1])
            {
                key=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=key;
            }
        }
    }
    printf("\n");
    printf("after sorting:\n");
    for(i=0;i<n;i++){
        printf("%d \t",arr[i]);
    }
    getch();
}

Output :

Enter the number of elements you want to sort:
5
Now enter the 5 elements you want to sort: 
78
96
12
2
55
before sorting:
78      96      12      2       55 
after sorting:
2       12      55      78      96 

---

[wpusb]