Zenith

Saturday, May 18, 2013

For in-depth understanding of Data Structure and Algorithm concepts refer :

1) INTRODUCTION TO ALGORITHMS by Coremen Introduction to Algorithms, 3rd Edition From flipkart.com
Introduction to Algorithms, 3rd Edition From amazon.com
Introduction to Algorithms from amazon.in

2) DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron - DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron from flipkart.com
Data Structures Using C and C++ (2nd Edition) from amazon.com
Data Structures Using C and C++ from amazon.in

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

class node
{
    public:
        float info;
        node *next,*prev;
        node(){next=prev=0;}
        node(int n, node *ptr=0, node *ptr1=0)
        {
            info=n;
            next=ptr;
            prev=ptr1;
        }
};

/* sort the link list of elements*/
void isort(node *head)
{
    if (head == 0)
        return;
    float key;
    node *j,*i, *q=0;

    for(i=head->next;i!=0;i=i->next)
    {
        q=0;
        key = i->info;
        j=i->prev;
        while(j!=0 && key < (j->info) )
        {
            j->next->info=j->info;
            q = j;
            j=j->prev;
        }

        if(q!=0)
            q->info = key;
    }

}

void bucket_sort(float *a,int n)
{
    /* create buckets */
    node* *b = new node* [n];
    for(int i=0; i<n;i++)
        b[i]=0;

    /* step 2 begins - insert a[i] into buckets */
    for(int i=0;i<n;i++)
    {
        int index=n*a[i];

        node *temp=new node(sizeof(node));
        temp->info=a[i];

        if(b[index]==NULL)
        {
            b[index]=temp;
        }
        else
        {
            temp->next=b[index];
            b[index]->prev=temp;
            b[index]=temp;
        }
    } // end of for
    /* step 2 ends */

    /* step 3 begins - sort each bucket */
    for(int i=0; i<n;i++)
    {
        isort(b[i]);
    }
    /* step 3 ends */

    /* step 4 begins - concatenate all the buckets */
    node *trav=0;
    cout<<"\n\nSorted array is: \n";
    for(int i=0; i<n;i++)
    {
        trav = b[i];
        while(trav != 0)
        {
            cout<<trav->info<<" ";
            trav = trav->next;
        }
    }
    /* step 4 ends */
}

void main()
{
    clrscr();

    int n;
    float *a;

    cout<<"\n\t Enter the size of array : ";
    cin>>n;

    cout<<"\n\t Enter the elements of an array :\n";
    a=new float[n];
    for(int l=0;l<n;l++)
        cin>>a[l];

    cout<<"\n\t Unsorted array is..\n";
    for(l=0;l<n;l++)
        cout<<a[l]<<" ";
    cout<<"\n" ;

    /* sort lements using buckt sort */
    bucket_sort(a,n);

    getch();
}

Radix sort c++ code

priority queue c++ code

For in-depth understanding of Data Structure and Algorithm concepts refer :

1) INTRODUCTION TO ALGORITHMS by Coremen Introduction to Algorithms, 3rd Edition From flipkart.com
Introduction to Algorithms, 3rd Edition From amazon.com
Introduction to Algorithms from amazon.in

2) DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron - DATA STRUCTURES USING C AND C++ by Tenenbaum M Aaron from flipkart.com
Data Structures Using C and C++ (2nd Edition) from amazon.com
Data Structures Using C and C++ from amazon.in

#include<iostream.h>
#include<conio.h>
#include<process.h>
int n;
void maxheapinsert(int [],int key);
void heapincreasekey(int a[],int i,int key);
int heapextractmax(int a[]);
int prioritymaximum(int a[]);
void max_heapify(int a[20],int n1);
int heapsize;
int left(int i)
{
    return(2*i);
}
int right(int i)
{
    return((2*i)+1);
}
void max_heapify(int A[20],int i)
{
    int l,r,largest,s;
    l=left(i);
    r=right(i);

    if(l<=heapsize && A[l]>A[i])
        largest=l;
    else
        largest=i;

    if(r<=heapsize && A[r]>A[largest])
        largest=r;

    if(largest!=i)
    {
        s=A[i];
        A[i]=A[largest];
        A[largest]=s;
        max_heapify(A,largest);
    }
}
int prioritymaximum(int a[])
{

    return a[1];
}
int heapextractmax(int a[])
{
    if(n<0)
        cout<<"Underflow"<<endl;
    int max=a[1];
    a[1]=a[n];
    n--;
    max_heapify(a,1);
    return max;
}

void heapincreasekey(int a[],int i,int k)
{
    if(k<a[i])
        cout<<"New key is smaller than current key"<<endl;
    a[i]=k;
    while(i>1&&a[i/2]<a[i])
    {
        int t=a[i];
        a[i]=a[i/2];
        a[i/2]=t;
        i=i/2;
    }
}
void maxheapinsert(int a[],int k)
{
    n=n+1;
    a[n]=-999;
    heapincreasekey(a,n,k);
}

void main()
{
    int x,i2,c,key,a[20];
    a[0]=-999;
    int m;
    for( ; ; )
    {
        cout<<"Menu:"<<endl;
        cout<<"1:To get the maximum value"<<endl;
        cout<<"2:To extract maximum value"<<endl;
        cout<<"3:To increase key value"<<endl;
        cout<<"4:To insert new value"<<endl;
        cout<<"5:Exit:"<<endl;
        cout<<"Enter your choice"<<endl;
        cin>>c;
        switch(c)
        {
            case 1:
                x=prioritymaximum(a);
                cout<<x<<endl;
                break;
            case 2:
                m=heapextractmax(a);cout<<"process with priority "<<m<<" is being processed";
                break;
            case 3:
                cout<<"Enter the index value that is to modified "<<endl;
                cin>>i2;
                cout<<"Enter the new value"<<endl;
                cin>>key;
                heapincreasekey(a,i2,key);
                cout<<"Value modified"<<endl;
                break;
            case 4:
                cout<<"Enter the new value"<<endl;
                cin>>key;
                maxheapinsert(a,key);
                break;
            case 5:
                exit(0);
            default:
                cout<<"Wrong code"<<endl;
        }
    }
    getch();
}

Merge sort C++ code

Insertion sort C++ code

Tuesday, May 14, 2013

Time/Space complexity of sorting algorithms

Sorting

Algorithm	Data Structure	Time Complexity			Worst Case Auxiliary Space Complexity
		Best	Average	Worst	Worst
Quicksort	Array	`O(n log(n))`	`O(n log(n))`	`O(n^2)`	`O(log(n))`
Mergesort	Array	`O(n log(n))`	`O(n log(n))`	`O(n log(n))`	`O(n)`
Heapsort	Array	`O(n log(n))`	`O(n log(n))`	`O(n log(n))`	`O(1)`
Bubble Sort	Array	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Insertion Sort	Array	`O(n)`	`O(n^2)`	`O(n^2)`	`O(1)`
Select Sort	Array	`O(n^2)`	`O(n^2)`	`O(n^2)`	`O(1)`
Bucket Sort	Array	`O(n+k)`	`O(n+k)`	`O(n^2)`	`O(nk)`
Radix Sort	Array	`O(nk)`	`O(nk)`	`O(nk)`	`O(n+k)`