Tuesday, 11 December 2012

Sorting

In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other algorithms (such as search and merge algorithms) that require sorted lists to work correctly; it is also often useful for canonicalizing data and for producing human-readable output. More formally, the output must satisfy two conditions:
  1. The output is in nondecreasing order (each element is no smaller than the previous element according to the desired total order);
  2. The output is a permutation (reordering) of the input.

Selection Sort

In computer science, a selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) time complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

Coding
 
Implementation  in c
#include<stdio.h>
#define MAX 5
void main()
{
    int ar[MAX],i,j,tmp,small;
      for(i=0;i<5;i++)
    {
        printf("Enter number>> ");
        scanf("%d",&ar[i]);
    }
    printf("\nUnsoted Array\n");
    for(i=0;i<MAX;i++)
        printf("%d\t",ar[i]);
    for(i=0;i<MAX-1;i++)
    {
        small=i;
        for(j=i+1;j<MAX;j++)
        {
            if(ar[small]>ar[j])
            {
                small=j;
            }
        }
        if(small!=i)
        {
            tmp=ar[i];
            ar[i]=ar[small];
            ar[small]=tmp;
        }

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

Bubble Sort

 Bubble sort, sometimes incorrectly referred to as sinking 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.

Coding

Implementation in C

#include<stdio.h>

void main()
{
    int ar[5],i,j,tmp,flag=0;   
    for(i=0;i<5;i++)
    {
        printf("Enter number>> ");
        scanf("%d",&ar[i]);
    }
    printf("\n\nUnsort Array\n");
    for(i=0;i<5;i++)
        printf("%d\t",ar[i]);
    for(i=0;i<5-1;i++)
    {
        flag=0;
        for(j=1;j<5-i-1;j++)
        {
            if(ar[j]>ar[j+1])
            {
                tmp=ar[j];
                ar[j]=ar[j+1];
                ar[j+1]=tmp;
                flag=1;
            }
        }
        if(flag==0);
            break;
    }
    printf("\n\n");
    for(i=0;i<5;i++)
        printf("%d\t",ar[i]);   
}