heap sort

This is a discussion on heap sort within the C Programming forums, part of the General Programming Boards category; Originally Posted by mherald81 It's actually not because of 3 consecutive letters, but instead some of the strings in your ...

  1. #16
    Registered User Char*Pntr's Avatar
    Join Date
    Sep 2007
    Location
    Lathrop, CA
    Posts
    198
    Quote Originally Posted by mherald81 View Post
    It's actually not because of 3 consecutive letters, but instead some of the strings in your input has the first character as a lowercase. I will have to work on fixing that.
    Yes, I changed all to lower case, and the list was sorted ok.
    Last edited by Char*Pntr; 10-31-2010 at 02:32 AM. Reason: Error

  2. #17
    Registered User
    Join Date
    Jan 2008
    Posts
    42
    Ok here's my updated code. However I'm not too sure how to check without making everything uppercase or lowercase.

    Code:
    /*****************************************************************************/
    /*  Program: HeapSort Test                                                   */
    /*  Author:  mherald81                                                       */
    /*****************************************************************************/
    
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    #include <ctype.h>
    
    /*****************************************************************************/
    /*    Function Prototypes                                                    */
    /*****************************************************************************/
    void swap(char** first, char** second);
    void print(char **array, const int arraySize);
    void heapSort(char **a);
    void makeHeap(char **a);
    void siftDown(char **a, int node, int size);
    void readInputFile(FILE *input);
    void stoupper(char *s);
    
    /*****************************************************************************/
    /*    Global Variables                                                       */
    /*****************************************************************************/
    int num_elements = 0;
    int num_allocated = 0;
    char **someArray;
    
    /*****************************************************************************/
    /*    Main                                                                   */
    /*****************************************************************************/
    int main(void)
    {
        FILE *inFile;
        inFile = fopen("input.txt", "r");
        if(inFile == NULL)
        {
            printf("Can't open input file!!!\n");
            system("pause");
            exit(1);
        }
    
        readInputFile(inFile);
        heapSort(someArray);
        print(someArray, num_elements);
        free(someArray);
        fclose(inFile);
        return 0;
    }
    
    /*****************************************************************************/
    /*    Function Definitions                                                   */
    /*****************************************************************************/
    void stoupper(char *s) 
    {
        do if (96 == (224 & *s)) *s &= 223;
        while (*s++);
    }
    
    void readInputFile(FILE *input)
    {    
        char **temp;
        char username[80];
        
        printf("Reading file...\n");
    
        while(fscanf(input, "%s", username) != EOF)
        {
            stoupper(username);
            if(num_elements == num_allocated)
            {
                if (num_allocated == 0)
                    num_allocated = 3; 
                else
                    num_allocated *= 2; 
                temp = realloc(someArray, (num_allocated * sizeof(char*)));
                if(temp == NULL)
                {
                    printf("ERROR: Couldn't realloc memory!\n");
                    exit(1);
                }
                someArray = temp;
            }
            someArray[num_elements] = malloc(sizeof(username));
            strcpy(someArray[num_elements],username);
            num_elements++;
        }
    }
    
    void swap(char **first, char **second)
    {
        char *temp = *first;
        *first = *second;
        *second = temp;
    }
    
    void print(char **array, const int arraySize)
    {
        int i;
        for(i = 0; i < num_elements; i++)
            printf("%s\n", array[i]); 
    }
    
    void siftDown(char **a, int node, int size)
    {
        while (2 * node + 1 < size)
        {
            int largest = node;
            // If the child has a sibling and the child's value is less than
            // its sibling's
            if (strcmp(a[largest],a[2 * node + 1]) < 0)
                largest = 2 * node + 1;
            if (2 * node + 2 < size && 
                strcmp(a[largest],a[2 * node + 2]) < 0)
                largest = 2 * node + 2;
    
            if (strcmp(a[node],a[largest]) < 0)
            { // out of max-heap order
                swap(&a[node], &a[largest]);
                node = largest;
            }
            else
                break;
        }
    }
    
    void makeHeap(char **a)
        // This function will play a in a max-heap order.
        // The shiftDown function is called.
    {
        int i;
        for (i = num_elements / 2; i >= 0; --i)
            siftDown(a, i, num_elements);
    }
    
    void heapSort(char **a)
        // This function will sort the values using heap
        // sort. makeHeap and shiftDown functions are called.
    {
        int size;
        makeHeap(a);// first place a in max-heap order
        size = num_elements;
    
        while (size != 1)
        {// swap the root(maximum value) of the heap with the last element 
         // of the heap
            swap(&a[0], &a[size - 1]);
            // decrease the size of the heap by one so that the previous max 
            // value will stay in its proper placement
            --size;
            siftDown(a, 0, size); // put the heap back in max-heap order   
        }
    }
    Last edited by mherald81; 10-31-2010 at 10:25 AM.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. heap sort problem
    By Cpro in forum C++ Programming
    Replies: 2
    Last Post: 02-04-2008, 04:54 AM
  2. How do I heap sort alphabetically?
    By arih56 in forum C++ Programming
    Replies: 7
    Last Post: 12-12-2007, 01:00 AM
  3. Heap Sort
    By silicon in forum C++ Programming
    Replies: 1
    Last Post: 05-18-2005, 01: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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21