Thread: heap sort

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    42

    heap sort

    I had this working in C++ but wanted to get a C version. I'm pretty sure I'm getting lost with the pointers. I would appreciate any help.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    
    #define ARRAY_SIZE 8
    
    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);
    
    int main( )
    {
    
    	char **someArray;
    
    	someArray = (char**)calloc(sizeof(char**),ARRAY_SIZE);
    	if (someArray == NULL) 
    	{
    		printf("Error allocating filename array\n");
    		exit(1);
      }
    	
    	someArray[0] = "Darin";
    	someArray[1] = "David";
    	someArray[2] = "Brian";
    	someArray[3] = "Dog";
    	someArray[4] = "Nikki";
    	someArray[5] = "Aaron";
    	someArray[6] = "Robert";
    	someArray[7] = "Tim";
    	heapSort(someArray);
    	print(someArray, ARRAY_SIZE);
    	free(someArray);
    	system("PAUSE");
    	return 0;
    }
    
    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 < arraySize; 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 (a[largest] < a[2 * node + 1])
    			largest = 2 * node + 1;
    		if (2 * node + 2 < size && 
    			a[largest] < a[2 * node + 2])
    		largest = 2 * node + 2;
          
    		if (a[node] < a[largest])
    		{ //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 = ARRAY_SIZE / 2; i >= 0; --i)
    		siftDown(*a, i, ARRAY_SIZE);
    }
    
    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 = ARRAY_SIZE;
      
    	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   
    	}
    }

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    What errors are you getting?
    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"

  3. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    42
    No errors, just that it doesn't sort the names correctly.

    original:
    "Darin"
    "David"
    "Brian"
    "Dog"
    "Nikki"
    "Aaron"
    "Robert"
    "Tim"

    new
    "David"
    "Brian"
    "Dog"
    "Nikki"
    "Aaron"
    "Robert"
    "Tim"
    "Darin"

  4. #4
    Registered User
    Join Date
    Jan 2008
    Posts
    42
    Updated it a bit, but still have some issues. It's only sorting based on the first letter. So if I have 2 words that start with the same letter it won't sort correctly.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    
    #define ARRAY_SIZE 8
    
    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);
    
    int main( )
    {
    
    	char **someArray;
    
    	someArray = (char**)calloc(sizeof(char**),ARRAY_SIZE);
    	if (someArray == NULL) 
    	{
    		printf("Error allocating filename array\n");
    		exit(1);
      }
    	
    	someArray[0] = "Darin";
    	someArray[1] = "David";
    	someArray[2] = "Brian";
    	someArray[3] = "Jim";
    	someArray[4] = "Nikki";
    	someArray[5] = "Aaron";
    	someArray[6] = "Robert";
    	someArray[7] = "Tim";
    	heapSort(someArray);
    	print(someArray, ARRAY_SIZE);
    	free(someArray);
    	system("PAUSE");
    	return 0;
    }
    
    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 < arraySize; 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 (*a[largest] < *a[2 * node + 1])
    			largest = 2 * node + 1;
    		if (2 * node + 2 < size && 
    			*a[largest] < *a[2 * node + 2])
    		largest = 2 * node + 2;
          
    		if (*a[node] < *a[largest])
    		{ //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 = ARRAY_SIZE / 2; i >= 0; --i)
    		siftDown(a, i, ARRAY_SIZE);
    }
    
    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 = ARRAY_SIZE;
      
    	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   
    	}
    }
    Output:
    Aaron
    Brian
    David
    Darin
    Jim
    Nikki
    Robert
    Tim

    The issue is in my siftDown function.

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You need to use strcmp in C to compare strings, using the less than operator does not work.
    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"

  6. #6
    Registered User
    Join Date
    Jan 2008
    Posts
    42
    Quote Originally Posted by iMalc View Post
    You need to use strcmp in C to compare strings, using the less than operator does not work.
    Thanks, I keep forgetting. I got it working.

  7. #7
    Registered User
    Join Date
    Jan 2008
    Posts
    42
    Ok, I'm trying to change it up a bit to read from a file but I'm having issues. The function that I'm having trouble creating is readInputFile.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    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, char **a);
    
    int num_elements = 0;
    
    int main( )
    {
    	char **someArray;
    	FILE *inFile;
    	someArray = (char**)malloc(sizeof(char**)*10);
    
    
    	inFile = fopen("input.txt", "r");
    	if(inFile == NULL)
    	{
    		printf("Can't open input file!!!\n");
    		system("pause");
    		exit(1);
    	}
    
    	readInputFile(inFile, someArray);
    	heapSort(someArray);
    	print(someArray, num_elements);
    	free(someArray);
    	system("PAUSE");
    	return 0;
    }
    
    void readInputFile(FILE *input, char **a)
    {	
    	
    	char username[10];
    
    	printf("Reading file...\n");
    
    	while(fscanf(input,"%s", username) != EOF)
    	{
    		a[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   
    	}
    }
    input.txt
    Code:
    Mike
    Brian
    Nikki
    Aaron
    David
    output:
    Code:
    Reading file...
    ╠╠╠╠╠╠╠╠╠╠╠╠
    ╠╠╠╠╠╠╠╠╠╠╠╠☺
    ╠╠╠╠╠╠╠╠╠╠╠╠☻
    ╠╠╠╠╠╠╠╠╠╠╠╠♥
    ╠╠╠╠╠╠╠╠╠╠╠╠♦

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by mherald81
    Ok, I'm trying to change it up a bit to read from a file but I'm having issues. The function that I'm having trouble creating is readInputFile.
    This is wrong, though it probably does not actually cause a problem:
    Code:
    someArray = (char**)malloc(sizeof(char**)*10);
    It should be:
    Code:
    someArray = malloc(sizeof(someArray[0]) * 10);
    Note that someArray[0] is of type char*, not char**, and that you do not need to cast the return value of malloc in C.

    Now, here's where you have a problem, in readInputFile:
    Code:
    a[num_elements] =username;
    username is an array of 10 chars. You are assigning a pointer to the first character of username to a[num_elements], so a[num_elements] points to the first char of username. But username is immediately overwritten on the next iteration, and futhermore, it is local to the readInputFile function, so it does not exist after control leaves that function.

    A possible solution is to do something like this:
    Code:
    void readInputFile(FILE *input, char **a)
    {
        char username[10];
    
        printf("Reading file...\n");
    
        while (fscanf(input, "%9s", username) == 1)
        {
            a[num_elements] = malloc(10);
            strcpy(a[num_elements, username);
            num_elements++;
        }
    }
    But remember to free what you malloc. That said, if you are really going to have strings of at most length 9, then you might as well change someArray to a pointer to an array of 10 char:
    Code:
    char (*someArray)[10];
    In which case you can write:
    Code:
    void readInputFile(FILE *input, char (*a)[10])
    {
        printf("Reading file...\n");
    
        while (fscanf(input, "%9s", a[num_elements]) == 1)
        {
            num_elements++;
        }
    }
    Be warned that your code is susceptible to buffer overflow in both cases. If you are setting an upper bound of 10 elements, then you should check for it.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Zee French rioters, ze are manning zee barricades, no?

    Code:
    Reading file...
    ╠╠╠╠╠╠╠╠╠╠╠╠
    ╠╠╠╠╠╠╠╠╠╠╠╠☺
    ╠╠╠╠╠╠╠╠╠╠╠╠☻
    ╠╠╠╠╠╠╠╠╠╠╠╠♥
    ╠╠╠╠╠╠╠╠╠╠╠╠♦

  10. #10
    Registered User
    Join Date
    Jan 2008
    Posts
    42
    Is there a way to modify it to accept any number of elements? I had the bound set to 10 just to test it out.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by mherald81
    Is there a way to modify it to accept any number of elements?
    Yes, by keeping track of the capacity in addition to the size, and using realloc to expand the dynamic array by some factor whenever a new read would otherwise cause the size to exceed the capacity.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Jan 2008
    Posts
    42
    Something like this? I'm still messing around with it to get it working but would appreciate any hints or suggestions.

    Code:
    void readInputFile(FILE *input)
    {	
    	char *temp;
    	char username[80];
    
    	printf("Reading file...\n");
    	while(fscanf(input, "%s", username) != EOF)
    	{
    		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;
    		}
    		strcpy(someArray[num_elements],username);
    		num_elements++;
    	}
    	free(temp);
    }

  13. #13
    Registered User
    Join Date
    Jan 2008
    Posts
    42
    laserlight,

    Can you look over this and make sure everything is ok.

    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    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);
    
    int num_elements = 0;
    int num_allocated = 0;
    char **someArray;
    
    int main( )
    {
    	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);
    	return 0;
    }
    
    void readInputFile(FILE *input)
    {	
    	char **temp;
    	char username[80];
    
    	printf("Reading file...\n");
    
    	while(fscanf(input, "%s", username) != EOF)
    	{
    		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   
    	}
    }

  14. #14
    Registered User Char*Pntr's Avatar
    Join Date
    Sep 2007
    Location
    Lathrop, CA
    Posts
    198

    Smile minor problem?

    I tested the code with some names and it seemed to work ok.

    However, when I tried to "break" your code I found out that there
    may be a problem when there are 3 consecutive letters.

    I don't know if this is important to you or not...

    Here is my input.txt file:

    Code:
    zebra zztack Dog Aaaron Tim Darin ZeeFrenchRioters Nikki Aaron TeeenyTim Robert David Brian Aaron
    Attached is my output. I have no comment on the rest of your code as it's above
    the level that I am at. :-)

    Edit: The code tested was in Post #13.
    Last edited by Char*Pntr; 10-31-2010 at 12:58 AM. Reason: clarification

  15. #15
    Registered User
    Join Date
    Jan 2008
    Posts
    42
    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.

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