Thread: Help with my string heapsort

  1. #1
    Registered User
    Join Date
    Sep 2010
    Posts
    14

    Help with my string heapsort

    I'm fairly new to algorithms, but i am working on heap sorting strings. The output should be
    a
    b
    c
    d
    e

    but instead it is
    a
    e
    b
    d
    c

    I am only using characters in the string array for testing currently, i will place full strings in once i figure out my problem. Can anyone give me some insight to my problem?

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    
    
    typedef char * string;
    
    void siftDown(string strs[], int root, int bottom);
    void heapSort(string strs[], int array_size);
    
    int main(int argc, char *argv[])
    
    {
    
    	
         int varcount = 5;
    
         string strs[5]; 
         int i;
    
         strs[0] = "c";
         strs[1] = "d";
         strs[2] = "e";
         strs[3] = "b";
         strs[4] = "a";
    
    
    
         heapSort(strs, varcount);
    
         for(i = 0;i < varcount;++i)
    	 printf("%s\n", strs[i]);
    
    	 
    	 return 0;
    
    
    }
    
    void heapSort(string strs[], int array_size)
    {
      int i;
      string temp[1];
     
      for (i = (array_size / 2); i >= 0; i--)
        siftDown(strs, i, array_size - 1);
     
      for (i = array_size-1; i >= 1; i--)
      {
        temp[0] = strs[0];
        strs[0] = strs[i];
        strs[i] = temp[0];
        siftDown(strs, 0, i-1);
      }
    }
     
     
    void siftDown(string strs[], int root, int bottom)
    {
      int done, maxChild;
      string temp[1];
     
      done = 0;
      while ((root*2 <= bottom) && (!done))
      {
        if (root*2 == bottom)
          maxChild = root * 2;
        else if (strcmp(strs[root * 2], strs[root * 2 + 1]) >> 0)
          maxChild = root * 2;
        else
          maxChild = root * 2 + 1;
     
        if (strcmp(strs[root], strs[maxChild]) << 0)
        {
          temp[0] = strs[root];
          strs[root] = strs[maxChild];
          strs[maxChild] = temp[0];
          root = maxChild;
        }
        else
          done = 1;
      }
    }
    Any help would be much appreciated
    My hypothesis is its something with the string compares, because it works for integers.

  2. #2
    Gawking at stupidity
    Join Date
    Jul 2004
    Location
    Oregon, USA
    Posts
    3,218
    >> is the right shift operator and << is the left shift operator. You're looking for greater-than > and less-than <.
    If you understand what you're doing, you're not learning anything.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Heapsort
    By myle in forum C++ Programming
    Replies: 5
    Last Post: 06-26-2008, 01:44 AM
  2. Heapsort
    By xENGINEERx in forum C Programming
    Replies: 2
    Last Post: 03-30-2008, 07:17 PM
  3. heapsort help please!
    By MAC77 in forum C++ Programming
    Replies: 2
    Last Post: 12-14-2005, 12:28 PM
  4. Heapsort
    By abalfazl in forum C Programming
    Replies: 2
    Last Post: 08-06-2005, 06:11 PM
  5. heapsort help plz
    By nsssn73 in forum C# Programming
    Replies: 0
    Last Post: 06-02-2002, 06:54 AM