Saturday, May 18, 2013

Bucket sort 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<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();
}

4 comments:

  1. sir, i've tried your code last time
    it doesn't have error at all
    but why the process stopped ?
    could you help me please to solve this problem ?
    i need your code to make an assignment

    ReplyDelete
  2. what kind of error do you get ? this code works fine at my end ...

    ReplyDelete
  3. your code is great
    I wish I could write such a code ...
    thanks

    ReplyDelete
  4. This Program is not givin me output plz can any1 help

    ReplyDelete