Showing posts with label Sorting. Show all posts
Showing posts with label Sorting. Show all posts

Sunday 12 March 2017

Bubble Sort

Bubble Sort 

Introduction



Bubble sort is a simple sorting algorithm that compares each pair of adjacent items and swaps them if they are in the wrong order.

The pass through the list is repeated until no swaps are required, which indicates that the list is sorted.


C code

#include <stdio.h>
void BubbleSort(int items[], int length);
void PrintArray(int items[],int length)
{
    printf("\n");
    for(int i=0; i < length; i++)
    {
        printf("%d ",items[i]);
    }
}
int main()
{
    int items[] = {1,4,5,-22,11,3};

    printf("Before sorting\n");
    PrintArray(items,6);
    printf("\n**********************\n");
    BubbleSort(items,6);
    printf("\n**********************\n");
    printf("after sorting\n");
    PrintArray(items,6);
 
    return 0;
}

void BubbleSort(int items[], int length)
{
    //iterate from first item (index 0) till 2nd last
   for(int i=0; i<length-1;i++)
   {
       //iterate from first item(index 0) till length-(i+1)
       for(int j=0; j<length-i-1;j++)
       {
           if(items[j] > items[j+1])
           {
               printf("\n swapping between %d and %d",j, j+1);
               items[j]= items[j] ^ items[j+1];
             
               items[j+1] = items[j] ^ items[j+1];
     
               items[j] = items[j] ^ items[j+1];
              PrintArray(items,6);
           }
       
       }
     
   }
 
}



 
 



http://onlinegdb.com/B1_F_nQsl



Complexity


Worst Case : О(n2)

Average Case : O(n2)

Best Case : O(n)  happens when the list is already sorted. But in this case insertion sort performs better than Bubble Sort.