Thread: How do I heap sort alphabetically?

  1. #1
    Registered User
    Join Date
    Dec 2007
    Posts
    3

    Post 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;
    }

  2. #2
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by arih56 View Post
    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.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Salem View Post
    > 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.

  5. #5
    Registered User
    Join Date
    Dec 2007
    Posts
    3
    Instead of comparing integers with '<' and '>', compare strings with strcmp().
    But i'm not sure how or where to insert strcmp into the code.

  6. #6
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by arih56 View Post
    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.

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    It is C++. So use std::string which supports comparison operators. The only thing that needs to be changed are relevant variable declarations.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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.
    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"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How do I bubble sort alphabetically?
    By arih56 in forum C++ Programming
    Replies: 4
    Last Post: 02-27-2008, 02:30 AM
  2. heap sort problem
    By Cpro in forum C++ Programming
    Replies: 2
    Last Post: 02-04-2008, 04:54 AM
  3. Heap Sort
    By silicon in forum C++ Programming
    Replies: 1
    Last Post: 05-18-2005, 12:53 PM
  4. heap question
    By mackol in forum C Programming
    Replies: 1
    Last Post: 11-30-2002, 05:03 AM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 08:05 PM