Sorting

[helnow]

I am doing heap sort
i start from generating rand array, then heapify it, then sort it using heap method.
the heapify works fine.
but on the heap sort, after i swap the first and last element, i deleted from the heap, then when i re-heapify, the deleted last element is involved.

void print(int n )
{
for (int i = 0; i<n; i++)
	{
		cout<<arr[i]<<" ";
	}
	cout<<endl;
	arraytoheap(n);

	for (int i = 0; i<n; i++)
	{
		cout<<arr[i]<<" ";
	}
	cout<<endl;
}

void heapsort(int n )
{
	int arra[50];

		swap(arr[0], arr[n-1]);
		for (int i = 0; i<n; i++)
	{
		cout<<arr[i]<<" ";
	}
		cout<<endl;
		n--;
	print(n);	
}

5
42 68 35 1 70------> original rand array 
70 68 35 1 42----> after heapify
42 68 35 1 70 ---> swapped first and last index 
42 68 35 1 ----> delete last element
70 68 35 1--->heaplify it again, but 70 shows up after deletion when i reheaplify, any reason why
Press any key to continue . . .

Thank you!

[Duthomhas]

I see no actual sorting in that code.

Heapsort is an in-place sort, and the difference between the heap and the sorted elements is just an index into the array.

|----heap----|----sorted----|
             n

Changing the size of the heap is really just decrementing that index by one.

|----heap---|-----sorted----|
            n-1

If you need more reading, see the FAQ:
http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/heapsort/

Hope this helps.

[helnow]

yeah, i get that
i made a little modification to my code

//prints the heaps 
void print(int n )
{
for (int i = 0; i<5; i++)
	{
		cout<<arr[i]<<" ";
	}
	cout<<endl;

}

void heapsort(int n )
{
	
	for (int i = 0; i<n; i++){
		swap(arr[0], arr[n-1]); // swaps the first and last element 
			n--; // decreament the index 
		while (arr[i]<arr[2*i+1]&&arr[2*i+1]!=arr[n]) // while check for re-heap
		swap(arr[i], arr[2*i+1]);
	
		print(n); //function call
	}	
}

but the output is not sorted correctly, any reason
please help !!

5  ---> array size
42 68 35 1 70---> rand size
70 68 35 1 42 ---> heap
68 42 35 1 70--->after swapping the last element then, re heap
1 42 35 68 70
35 42 1 68 70 ---> last output, but as you can see it is not sorted.
Press any key to continue . . .

[Duthomhas]

You are not properly maintaining the heap property (lines 15 and 18). You can't mix the two operations into one loop.

You should make yourself a separate function (called "sink" or something) to sink the new node in the heap, and call it after you swap first and last node and decrement the heap size.


BTW, the forum's spell check is messing with me... I've been spelling the word 'decrement' properly for many, many years now...

[helnow]

sorry, but im not sure i understand what you mean
is this what you mean ?

void sink (int n)
{
	
	for (int i = 0; i<n; i++)
	{
		if (arr[i]<arr[2*i+1])
		{
			if (arr[2*i+1] < arr[2*i+2])
			{
				swap(arr[2*i+1], arr[2*i+2]);
				swap(arr[i], arr[2*i+1]);
			}
				
		}
	}
}



void heapsort(int n )
{
	int t = 0;
	int arra[50];
	for (int i = 0; i<n; i++){
		swap(arr[0], arr[n-1]);
		n--;
		sink(n);
			print(n);
	}	
}		

[Duthomhas]

Sort of. You need to revisit the logic of your sink function.

The arr[i] is the current parent node, right?

If either child node is larger than the parent node, then you need to do a swap with that child, and then update i to the index of the child node you just swapped with.

Terminate if no children are larger than the parent.

Also beware of the last parent node -- it may have only one child!

http://www.cplusplus.com/faq/sequences/sequencing/sort-algorithms/heapsort/#heap-property

Hope this helps.