How do I heap sort alphabetically?

I have a heapsort function which i've used to sort a list of integers. How do I adapt this function to sort a list of strings alphbetically?
My sort function is:

Code:

---

int temp, item, j;
for(int k=i-1; k>0; k--)
{
        for(int i=0; i<=k; i++)
        {
                item=value[i].first_name;
                j=i/2;
                while (j>0 && value[j].first_name<item)
                {
                        value[i].first_name=value[j].first_name;
                        i=j;
                        j=j/2;
                }
                value[i].first_name=item;
        }

        temp=value[1].first_name;
        value[1].first_name=value[k].first_name;
        value[k].first_name=temp;
}

---

Quote:

---

Originally Posted by arih56

I have a heapsort function which i've used to sort a list of integers. How do I adapt this function to sort a list of strings alphbetically?

---

Instead of comparing integers with '<' and '>', compare strings with strcmp().

If strcmp(a, b) == -1, this means that a < b (lexically).
If strcmp(a, b) == 1, this means that a > b,
If strcmp(a, b) == 0, this means that a == b.

> If strcmp(a, b) == -1, this means that a < b (lexically).
The standard specifies the tests as <0, ==0 and >0
+/-1 would be implementation specific.

Quote:

---

Originally Posted by Salem

> If strcmp(a, b) == -1, this means that a < b (lexically).
The standard specifies the tests as <0, ==0 and >0
+/-1 would be implementation specific.

---

Yes, true. I don't actually code my tests that way either.

Quote:

---

Instead of comparing integers with '<' and '>', compare strings with strcmp().

---

But i'm not sure how or where to insert strcmp into the code.

Quote:

---

Originally Posted by arih56

But i'm not sure how or where to insert strcmp into the code.

---

Everywhere you compare two array values, you would replace with strcmp() instead.

It is C++. So use std::string which supports comparison operators. The only thing that needs to be changed are relevant variable declarations.

That might bear some small resemblance to heapsort, but it is very much not heapsort!
I ran it through my sorting demo program to animate how it sorts and my fears were more than confirmed:

First of all it is O(n*n*logn) which is worse than bubble sort. HeapSort should always be O(n*logn) or it is not really heapsort. This algorithm actually ran very significantly slower than an unoptimised bubblesort!
Secondly, it didn't quite sort correctly. It leaves the wrong item at the first position in the array, though the rest is always sorted.
I was able to make it sort correctly by making two small changes:
1. Instead of incorrectly swapping with element one at the end of the loop, swap with element zero.
2. Change the first part of the expression in the while loop to "j!=i" instead of "j>0"

It does actually build and use what definitely appears to be a heap, though it does so through extremely inefficient means. It seems to check EVERY parent/child relationship through the process of insertion or extracting from the heap.
I'm actually going to hang onto this source code if for no other reason than purely to be able to demonstrate how not to write heapsort.