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

What errors are you getting?

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"

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.

You need to use strcmp in C to compare strings, using the less than operator does not work.

Originally Posted by iMalc

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.

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...
╠╠╠╠╠╠╠╠╠╠╠╠
╠╠╠╠╠╠╠╠╠╠╠╠☺
╠╠╠╠╠╠╠╠╠╠╠╠☻
╠╠╠╠╠╠╠╠╠╠╠╠♥
╠╠╠╠╠╠╠╠╠╠╠╠♦

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.

Zee French rioters, ze are manning zee barricades, no?

Code:

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

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.

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.

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

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

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.

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.