Thread: heap sort

Originally Posted by mherald81

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.

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