Like Us On Facebook

Follow Us On Twitter

Drop Down Menu

Tuesday 8 January 2013

Bubble Sort Algorithm And C Code

Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort. Although the algorithm is simple, most of the other sorting algorithms are more efficient for large lists. Bubble sort is not a stable sort which means that if two same elements are there in the list, they may not get their same order with respect to each other.

Step-by-step example:

Let us take the array of numbers "5 1 4 2 8", and sort the array from lowest number to greatest number using bubble sort. In each step, elements written in bold are being compared. Three passes will be required.
First Pass:
5 1 4 2 8 ) \to ( 1 5 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
( 1 5 4 2 8 ) \to ( 1 4 5 2 8 ), Swap since 5 > 4
( 1 4 5 2 8 ) \to ( 1 4 2 5 8 ), Swap since 5 > 2
( 1 4 2 5 8 ) \to ( 1 4 2 5 8 ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.

Second Pass:
1 4 2 5 8 ) \to ( 1 4 2 5 8 )
( 1 4 2 5 8 ) \to ( 1 2 4 5 8 ), Swap since 4 > 2
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
Now, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole pass without any swap to know it is sorted.

Third Pass:
1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )
( 1 2 4 5 8 ) \to ( 1 2 4 5 8 )


Algorithm For Bubble Sort:


/* Double-Click To Select Code */

Step 1: Repeat Steps 2 and 3 for i=1 to 10

Step 2: Set j=1

Step 3: Repeat while j<=n

         (A) if  a[i] < a[j]

             Then interchange a[i] and a[j]

             [End of if]

         (B) Set j = j+1
        [End of Inner Loop]

    [End of Step 1 Outer Loop]

Step 4: Exit


Optimized Algorithm For Bubble Sort:

/* Double-Click To Select Code */

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
       swapped = false
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             swapped = true
          end if
       end for
       n = n - 1
    until not swapped
end procedure


C Program For Bubble Sort:


/* Double-Click To Select Code */

#include<stdio.h>
#include<conio.h>
void main()
{
 int i,n,temp,j,arr[25];
 clrscr();
 printf("Enter the number of elements in the Array: ");
 scanf("%d",&n);
 printf("\nEnter the elements:\n\n");

 for(i=0 ; i<n ; i++)
 {
  printf(" Array[%d] = ",i);
  scanf("%d",&arr[i]);
 }

 for(i=0 ; i<n ; i++)
 {
  for(j=0 ; j<n-i-1 ; j++)
  {
   if(arr[j]>arr[j+1]) //Swapping Condition is Checked
   {
    temp=arr[j];
    arr[j]=arr[j+1];
    arr[j+1]=temp;
   }
  }
 }

 printf("\nThe Sorted Array is:\n\n");
 for(i=0 ; i<n ; i++)
 {
  printf(" %4d",arr[i]);
 }
 getch();
}

Output of Program:

Bubble Sort Algorithm And C Code


Please Comment If You Liked This Post !! 

This article uses material from the Wikipedia article Bubble_Sort which is released under the Creative Commons Attribution-Share-Alike License 3.0


Quick Sort Algorithm And C Code

Quicksort, or partition-exchange sort, is a sorting algorithm that, on average, makes O(n log n) comparisons to sort n items.  It was developed by Tony Hoare. Quicksort is faster in practice than other O(n log n) algorithms such as Bubble sort or Insertion Sort. Quicksort can be implemented with an in-place partitioning algorithm, so the entire sort can be done with only O(log n) additional space.
Quicksort is a comparison sort and is not a stable sort.

Its complexity is as follows:
Best Case - O(n log n)
Worst Case - O(n^2) 
Average Case - O(n log n)

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists.
The steps are:
1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively sort the sub-list of lesser elements and the sub-list of greater elements.
The base case of the recursion are lists of size zero or one, which never need to be sorted.


Algorithm/Pseudo-code For Quicksort:




/* Double-Click To Select Code */

  function quicksort('array')
      if length('array') ≤ 1
         return 'array'  // an array of zero or one elements is already sorted
      select and remove a pivot value 'pivot' from 'array'
      create empty lists 'less' and 'greater'
      for each 'x' in 'array'
         if 'x' ≤ 'pivot' then append 'x' to 'less'
         else append 'x' to 'greater'
      return concatenate(quicksort('less'), 'pivot', quicksort('greater')) 
// two recursive calls



Here is an Image depicting Quick Sort:


Quick Sort
In-place partition in action on a small list. The boxed element is the pivot element, blue elements are less or equal, and red elements are larger.

C Program For Quick Sort:


/* Double-Click To Select Code */

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

void quick_sort(int arr[20],int,int);

void main()
{
 int arr[20],n,i;
 clrscr();
 printf("Enter the number of elements in the Array: ");
 scanf("%d",&n);
 printf("\nEnter %d elements:\n\n",n);

 for(i=0 ; i<n ; i++)
 {
  printf(" Array[%d] = ",i);
  scanf("%d",&arr[i]);
 }

 quick_sort(arr,0,n-1);
 printf("\nThe Sorted Array is:\n\n");

 for(i=0 ; i<n ; i++)
 {
  printf(" %4d",arr[i]);
 } 
 getch();
}

void quick_sort(int arr[20],int low,int high)
{
 int pivot,j,temp,i;
 if(low<high)
 {
  pivot = low;
  i = low;
  j = high;

  while(i<j)
  {
   while((arr[i]<=arr[pivot])&&(i<high))
   {
    i++;
   }

   while(arr[j]>arr[pivot])
   {
    j--;
   }

   if(i<j)
   { 
    temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
   }
  }

  temp=arr[pivot];
  arr[pivot]=arr[j];
  arr[j]=temp;
  quick_sort(arr,low,j-1);
  quick_sort(arr,j+1,high);
 }
}


Output of Program:


Quick Sort Algorithm And C Code

Please Comment If You Liked This Post !! 

This article uses material from the Wikipedia article Quick Sort which is released under the Creative Commons Attribution-Share-Alike License 3.0


Merge Sort Algorithm And C Code

Merge sort is a sorting technique, which is  based on comparison sorting algorithm, having complexity O(n log n). It is one of the types of stable sort, meaning, that in its implementation, input order of equal elements is preserved in the sorted output.  It was invented by John von Neumann in 1945. Merge sort is a divide and conquer algorithm.

The concept of Merge Sort is based on the following principle:

Divide the unsorted list into 'n' sub-lists, each containing 1 element (a list of 1 element is considered sorted).
Repeatedly merge sub-lists to produce new sub-lists until there is only 1 sub-list remaining. This will be the sorted list.

Algorithm for Merge Sort:

/* Double-Click To Select Code */

function merge_sort(list m)
    // if list size is 0 (empty) or 1, consider it sorted and return it
    // (using less than or equal prevents infinite recursion for a zero length m)
    if length(m) <= 1
        return m
    // else list size is > 1, so split the list into two sublists
    var list left, right
    var integer middle = length(m) / 2
    for each x in m before middle
         add x to left
    for each x in m after or equal middle
         add x to right
    // recursively call merge_sort() to further split each sublist
    // until sublist size is 1
    left = merge_sort(left)
    right = merge_sort(right)
    // merge the sublists returned from prior calls to merge_sort()
    // and return the resulting merged sublist
    return merge(left, right)
In this example, the merge function merges the Left and Right sublists.

/* Double-Click To Select Code */

function merge(left, right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) <= first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            append first(right) to result
            right = rest(right)
    end while
    return result


Here is the C Code for Merge Sort:


/* Double-Click To Select Code */

#include <stdio.h>
#include<conio.h>
 
void mergesort(int arr[], int l, int h);
 
void main(void) 
{
 int array[100],n,i = 0; 
 clrscr();
 printf("Enter the number of elements to be sorted: ");
 scanf("%d",&n);
 printf("\nEnter the elements to be sorted: \n");
 for(i = 0 ; i < n ; i++ )
 {
  printf("\tArray[%d] = ",i);
  scanf("%d",&array[i]);
 }
 
 
 printf("\nBefore Mergesort:");  //Array Before Mergesort
 for(i = 0; i < n; i++)
 {
  printf("%4d", array[i]);
 }
 printf("\n");
 
 mergesort(array, 0, n - 1); 

 printf("\nAfter Mergesort:");  //Array After Mergesort
 for(i = 0; i < n; i++)
 {
  printf("%4d", array[i]);
 }
 printf("\n");
 getch();
}
 
void mergesort(int arr[], int l, int h) 
{
 int i = 0;
 int length = h - l + 1;
 int pivot  = 0;
 int merge1 = 0;
 int merge2 = 0;
 int temp[100];
 
 if(l == h)
 return;
 
 pivot  = (l + h) / 2;
 
 mergesort(arr, l, pivot);
 mergesort(arr, pivot + 1, h);
  
 for(i = 0; i < length; i++)
 {
  temp[i] = arr[l + i];
 }
 
 merge1 = 0;
 merge2 = pivot - l + 1;
 
 for(i = 0; i < length; i++) 
 {
  if(merge2 <= h - l)
  {
   if(merge1 <= pivot - l)
   {
    if(temp[merge1] > temp[merge2])
    {
     arr[i + l] = temp[merge2++];
    }

    else
    {
     arr[i + l] = temp[merge1++];
    }
   }

   else
   {
    arr[i + l] = temp[merge2++];
   }
  }

  else
  {
   arr[i + l] = temp[merge1++];
  }
 }
}

Output of Program:



Merge Sort Algorithm And C Code

Please Comment If You Liked This Post !! 

This article uses material from the Wikipedia article Merge Sort which is released under the Creative Commons Attribution-Share-Alike License 3.0