Thread: heap sort problem

  1. #1
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149

    heap sort problem

    I'm trying to sort an array of numbers with heap sort, but it's not sorting the first number in the array.
    Here is my code:
    Code:
    #include <iostream>
    using namespace std;
    
    int BuildMaxHeap(int array1[], int n);
    int MaxHeapify(int array1[], int i, int n);
    int Heapsort(int array1[], int n);
    
    int main()
    {
    	int array1[11] = {11, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9};
    
    	Heapsort(array1, 10);
    
    	for (int z = 0; z < 11 ; z++)
    	{
    		cout << array1[z] << " ";
    	}
    	cout << endl;
    
    	return 0;
    }
    int MaxHeapify(int array1[], int i, int n)
    {
    	int c=0;
    	int l = i << 1;					++c;
    	int r = (i << 1) + 1;			++c;
    	int largest;						++c;
    
    	// Is left larger than i?
    	if (++c && (l <= n) && (array1[l] > array1[i]))
    	{
    		largest = l;					++c;
    	}
    	else
    	{
    		largest = i;					++c;
    	}
    
    	// Is right larger than largest?
    	if (++c && (r <= n) && (array1[r] > array1[largest]))
    	{
    		largest = r;					++c;
    	}
    
    	// Need swap??
    	if (++c && largest != i)
    	{
    		int temp = array1[i];				++c;
    		array1[i] = array1[largest];				++c;
    		array1[largest] = temp;				++c;
    		c += MaxHeapify(array1, largest, n);	++c;
    	}
    
    	return c;
    }
    int BuildMaxHeap(int array1[], int n)
    {
    	int c=0;
    	for (int i = n / 2; ++c && i >= 1; i--)
    	{
    		c += MaxHeapify(array1, i, n);	++c;
    	}
    
    	return c;
    }
    int Heapsort(int array1[], int n)
    {
    	int c=0;
    	BuildMaxHeap(array1, n);				++c;
    	for (int i = n; ++c && i >= 2; i--)
    	{
    		// exchange i with 1
    		int temp = array1[1];			++c;
    		array1[1] = array1[i];				++c;
    		array1[i] = temp;				++c;
    
    		c += MaxHeapify(array1, 1, i-1);	++c;
    	}
    	return c;
    }
    I'm pretty sure the reason is because the whole sorting algorithm is made for a 1 based array (where the first position is 1, not 0). I'm pretty sure it's an easy fix, but i've been trying for a long time and can't figure it out. If I made the first position in the array a dead spot, and shifted the values one spot, this would fix the problem, but i can't figure out how.
    Also, for my real program, i read the numbers in from a file ( i created the above one so it could be copied and pasted to run. The real program requires a file, and needs to be run using the command prompt, so the solution to my problem could be slightly different in each case):
    Code:
    int main(int argc, char* argv[])
    {
    
    	int *array1 = NULL;
    	int size;
    	
    	//First value in the file is assigned to "size".
    	inFile >> size;	
    	
    	array1 = new int[size];
    
    	//FillArray
    	for (int i = 0; i < size; i++)
    	{
    		inFile >> array1[i];
    	}
    
    	//InsertionSort(array1, size);
    	//Quicksort (array1, 0, size-1);
    	Heapsort(array1, size-1);
    	//MergeSort(array1, 0, size-1);
    	//BubbleSort(array1, size);
    	//ShellSort(array1, size);
    	PrintArray(array1, size);	
    
    	delete [] array1;
    	array1 = NULL;
    	cin.get();
    	return 0;
    }
    In this, i launch the program in the command prompt like:
    Code:
    program file.txt
    and the file looks like (the first number is the number of values, and the rest are just random values):
    Code:
    10
    1
    6
    4
    8
    2
    4
    9
    8
    4
    2
    All my other sorting algorithms work in this program except for the heap sort. Once again, i think it's because of the 0 based array problem.

    Thanks.
    IDE - Visual Studio 2005
    Windows XP Pro

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    The main change you need to make to make heapsort work with a zero-based array is to change the child indexing from this:
    Code:
    	int l = i << 1;
    	int r = (i << 1) + 1;
    to this:
    Code:
    	int r = (i + 1) << 1;
    	int l = r - 1;
    Otherwise you can't pass i=zero because i<<1 is still zero. With this change, the children of index zero become 1 and 2 - just what you want.
    You then have to change this line:
    Code:
    	c += MaxHeapify(array1, 1, i-1);
    to this:
    Code:
    	c += MaxHeapify(array1, 0, i-1);
    and also adjust the start and end values of your decrementing for loops but one. There might be more you need to change, but you can probably figure the rest out on your own.

    Oh I see you have used recursion in MaxHeapify! You definitely shouldn't do that. Yes it will work, but one noted advantage of heapsort is that it is one of the algorithms that doesn't require anything more than constant space, and your implementation uses log(n) stack space.

    I also strongly suggest you make the function interfaces consistent. You should never have to pass in 'size' to some algorithms and 'size-1' to others. This parameter should always be the number of items to sort. If you have to, subtract 1 inside the start of the sorting function.

    Since you seem to be interested in a number of sorting algorithms, you may want to have a look at my webpage, which contains the implementations of at least 60 array sorting algorithms, all in C++.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User Cpro's Avatar
    Join Date
    Oct 2006
    Posts
    149
    That fixed it.
    Thanks.
    IDE - Visual Studio 2005
    Windows XP Pro

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 26
    Last Post: 07-05-2010, 10:43 AM
  2. problem with gets and bubble sort
    By wwwildbill in forum C Programming
    Replies: 4
    Last Post: 04-04-2009, 01:31 AM
  3. How do I heap sort alphabetically?
    By arih56 in forum C++ Programming
    Replies: 7
    Last Post: 12-12-2007, 01:00 AM
  4. Problem with Bubble Sort code
    By lisa1234 in forum C++ Programming
    Replies: 7
    Last Post: 01-13-2004, 03:40 PM
  5. Shell, Heap and Quick Sort
    By GaPe in forum C Programming
    Replies: 1
    Last Post: 08-19-2003, 01:04 PM