1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Bubble sort and Headp Sort

Discussion in 'C' started by Peter_APIIT, Sep 22, 2007.

  1. Peter_APIIT

    Peter_APIIT New Member

    Joined:
    Apr 11, 2007
    Messages:
    92
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Malaysia
    Hello all expert C and C++ programmer, i truly new to programming.

    1. I have coded the bubble sort but i cannot sort it in ascending order.

    Below is my code:

    Code:
    #include<iostream>
    
    using std::cout;
    using std::cin;
    
    
    void bubbleSort(int [], int);
    
    
    // ------------------------------------------
    int main(int argc, char *argv[])
    {
    	int sequence[5] = { 5, 3 , 4, 2, 1};
    	bubbleSort(sequence, 5);
    	return 0;
    }
    // ------------------------------------------
    void bubbleSort(int sequence[], int size)
    {
    	int inner_loop, outer_loop, temp;
    
    	
    	for (outer_loop=0;outer_loop<size;++outer_loop)
    	{
    		for (inner_loop=1;inner_loop<size;++inner_loop)
    		{
    			if (sequence[outer_loop] > sequence[inner_loop])
    			{
    				temp = sequence[outer_loop];
    				sequence[outer_loop] = sequence[inner_loop];
    				sequence[inner_loop] = temp;
    			}
    		}
    	}
    
    	for (inner_loop=0;inner_loop<size;++inner_loop)
    	{
    		cout << "The array[" << inner_loop
    			<< "] : " << sequence[inner_loop] << "\n";
    	}
    }
    
    
    Why this code is not sort the array into ascending but this give the correct result ?

    Code:
    #include<iostream>
    
    using std::cout;
    using std::cin;
    
    
    void bubbleSort(int [], int);
    
    
    // ------------------------------------------
    int main(int argc, char *argv[])
    {
    	int sequence[5] = { 5, 3 , 4, 2, 1};
    	bubbleSort(sequence, 5);
    	return 0;
    }
    // ------------------------------------------
    void bubbleSort(int sequence[], int size)
    {
    	int inner_loop, outer_loop, temp;
    
    	for (inner_loop=4;inner_loop>=0;inner_loop--)
    	{
    		for (outer_loop=1;outer_loop<size;++outer_loop)
    		{
    			if (sequence[outer_loop - 1] > sequence[outer_loop])
    			{
    				temp = sequence[outer_loop - 1];
    				sequence[outer_loop - 1] = sequence[outer_loop];
    				sequence[outer_loop] = temp;
    			}
    		}
    	}
    
    	for (inner_loop=0;inner_loop<size;++inner_loop)
    	{
    		cout << "The array[" << inner_loop
    			<< "] : " << sequence[inner_loop] << "\n";
    	}
    }
    	
    

    2. Can u explain to me the heap sort algorithm ? What is siftdown ?

    Thanks for your help.

    Your help is greatly appreciated by me and others.
     
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,283
    Likes Received:
    364
    Trophy Points:
    83
    By this time you should be aware what is an article and you should not be submitting your queries as articles. As of now I have moved them in the forum for discussion.
     
  3. Peter_APIIT

    Peter_APIIT New Member

    Joined:
    Apr 11, 2007
    Messages:
    92
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Malaysia
    Sorry for my blind eye. Thanks shabir.
     
  4. DaWei

    DaWei New Member

    Joined:
    Dec 6, 2006
    Messages:
    835
    Likes Received:
    5
    Trophy Points:
    0
    Occupation:
    Semi-retired EE
    Location:
    Texan now in Central NY
    Home Page:
    Your array only has a few items. If you will go through your algorithm with pencil and paper, you will discover your problem.

    A heap siftdown is the method for restoring the heapness of the tree after the root has been removed.
     
  5. Peter_APIIT

    Peter_APIIT New Member

    Joined:
    Apr 11, 2007
    Messages:
    92
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    Student
    Location:
    Malaysia
    Finally, i have understand the algorithm.

    Basically, the outer_loop has enforce the inner loop to loop again and again until the array is sorted.

    Below is the code:

    Code:
    void bubbleSort(int sequence[], int size)
    {
    	int inner_loop, outer_loop, temp;
    
    	for (inner_loop=4;inner_loop>=0;inner_loop--)
    	{
    		for(outer_loop=1;outer_loop<size;++outer_loop)
    		{
    			if (sequence[outer_loop - 1] > sequence[outer_loop])
    			{
    				temp = sequence[outer_loop - 1];
    				sequence[outer_loop - 1] = sequence[outer_loop];
    				sequence[outer_loop] = temp;
    			}
    		}
    	}
    
    
    This algorithm used the concept of queue where one person stand in front of the queue and another person standing back of the queue, move accordingly and if not sorted, the outer_loop(Manager) enforce the inner_loop(Worker) to start again and again until it is sorted.

    Imagine this case.

    I hope this code and algorithm help others.
     

Share This Page