10 Replies - 3791 Views - Last Post: 25 July 2008 - 10:47 PM Rate Topic: -----

#1 HulkingNightcrawler  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 26-June 08

Merge Sort and Quick Sort

Posted 24 July 2008 - 03:01 PM

Hello I am trying to write a program that uses merge sort and quick sort. I am using an array for quick sort and a linked list for merge sort. I can get the quick sort to sort most of the elements but then it stops sorting and leaves the last half of the array unsorted. I figured this must be a boundries issue, but I cannot seem to find the problem. Concerning my merge sort, I cannot even compile this code as of right now and I am not to sure why, I don't know if I am calling my variable wrong or not but it is confusing me on why it is not compiling. Thanks in advanced!!!
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

/* A struct for a node of the doubly linked list */
/* We will use node_t as the type. "dummytype" is there to make the
compiler happy */
  typedef struct dummytype
  {
		 struct dummytype* prev;  /* Points to the previous node */
		 struct dummytype* next;  /* Points to the next node */
		 int value;			   /* An integer value */
  } node_t;

/* This struct has all the information for a list */
/* The list is implemented as a doubly linked list */
  typedef struct
  {
		 node_t* head;		   /* Points to the head node of the list */
		 node_t* tail;		   /* Points to the tail node of the list */
  } mylist_t;
  int moves = 0;


void myinit(mylist_t *l, int x);
void myPush(mylist_t *l, int x);
void myDumpHead(mylist_t *l);
void printArray(int *array, int entries);
void selection(int* array, int r, int l);
int partition(int* array, int r, int l);
void quickSort(int* array, int r, int l);


int main(int argc, char *argv[])
{
  

  /*Number of items the users would like to sort*/
  int entries;

  /*Random variable I used through the program*/
  int i, j;

  /*Using Dynamic Memory allocation, I created an array off 100 indexes*/
  int* array = (int *)malloc(sizeof(int)*100);
  int* quickArray = (int *)malloc(sizeof(int)*100);
  int* mergeArray = (int *)malloc(sizeof(int)*100);

  /*Variable used to set my list*/
  mylist_t q;

  /*I initialize my list here*/
  myinit(&q, 3);  
  
  printf("How many entries would you like me to sort??\n");
  scanf("%d", &entries);
  printf("\n");

  /*This gets an array and linked list of random numbers*/
  for(i = 0; i < entries; i++)
  {
		array[i] = rand();
		myPush(&q, array[i]);
		quickArray[i] = array[i];
		mergeArray[i] = array[i];
  }


  
  
			printf("Unsorted Array\n");
			myDumpHead(&q);
			printf("\n\n");
			selection(array, entries, 0);
		
			/* This is just for me to double check the array vs. the linked list */
			for(j = 0; j < entries; j++)
			{
				  printf("%d ", array[j]);
			}
		
			printf("\n");
		
			printf("Quick Sort\n");
			quickSort(quickArray, 0, entries);
		
			/* This is just for me to double check the array vs. the linked list */
			for(j = 0; j < entries; j++)
			{
				  printf("%d ", quickArray[j]);
			}


   printf("\n");   
   return 0;
}

void myinit(mylist_t *l, int x)
{
	 /*Sets both pointers to NULL when the list is empty*/
	 l->head = l->tail = NULL;
}

void myPush(mylist_t *l, int x)
{
	 node_t *tmp = (node_t *)malloc(sizeof(node_t));

	 tmp->value = x;

	 if(!l->tail)
	 {
		 tmp->next = tmp->prev = NULL;
		 l->head = l->tail = tmp;
	 }
	 else
	 {
		 tmp->next = NULL;
		 tmp->prev = l->tail;
		 l->tail->next = tmp;
		 l->tail = tmp;
	 }
}

void myDumpHead(mylist_t *l)
{
		 node_t *tmp = l->head;

		 for(; tmp; tmp = tmp->next)
		 {
			   printf("%d ", tmp->value);
		 }
}

int swap(int a, int b, int *array)
{

   int t = array[a];
   array[a] = array[b];
   array[b] = t;
   moves++;
   return moves;
}

void printArray(int *array, int entries)
{
	 int i = 0;
	 for(; i < entries; i++)
		   printf("%d ", array[i]);
	 printf("\n");
}

void selection(int* array, int r, int l)
{
		 int i, j, compares, move;
		 compares = -1;
		 move = 0;
		 printf("Selection Sort\n");
		 for(i = l; i < r - 1; i++)
		 {
			   int min = i;

			   for(j = i + 1; j < r; j++)
			   {
					 compares++;
					 if(array[j] < array[min])
					 {			 						 
								 min = j;
					 }			 
			   }

			   printArray(array, r);
			   printf("Compares %d Moves %d\n", compares, move );		   
			   move = swap(i, min, array);
	 }
}

int partition(int* array, int l, int r)
{
	 int i = l - 1;
	 int j = r;
	 int v = array[r-1];

	 for(;;)
	 {
			while(array[++i] < v);

			while(v < array[--j])
			{
				if(j == l)
				   break;
			}

			if(i >= j)
				 break;

			swap(i, j-1, array);

	  }
	  swap(i , r-1, array);
	  return i;
}

void quickSort(int* array, int l, int r)
{
	 int p;
	 if(r <= l) return;
	 p = partition(array, l , r);
	 quickSort(array, l , p - 1);
	 quickSort(array, p + 1, r);
}

int merge(mylist_t *a, mylist_t *b)
{
	node_t *head;
	mylist_t *c = &head;
	while((a != NULL) && (b != NULL))
	{
		if(a->value < b->value)
		{
			c->next = a;
			c = a;
			a = a->next;
		}
		
		else
		{
			c->next = b; 
			c = b;
			b = b->next;
		}
	}
		
	c->next = (a == NULL) ? b : a;
	return head.next;	
}

int mergeSort(mylist_t *c)
{
	mylist_t *a;
	mylist_t *b;
	
	if(c->next == NULL)
		return c;
	a = c;
	b = c->next;
	
	while((b != NULL) && (b->next != NULL))
	{
		c = c->next;
		b = b->next->next;
	}
	
	b = c->next;
	c->next = NULL;
	
	return merge(mergeSort(a), mergeSort(b));
}




Is This A Good Question/Topic? 0
  • +

Replies To: Merge Sort and Quick Sort

#2 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Merge Sort and Quick Sort

Posted 24 July 2008 - 08:02 PM

Quote

int merge(mylist_t *a, mylist_t *b)
{
	node_t *head;
	mylist_t *c = &head;
	while((a != NULL) && (b != NULL))
	{
		if(a->value < b->value)
		{
			c->next = a;
			c = a;
			a = a->next;
		}
		
		else
		{
			c->next = b;
			c = b;
			b = b->next;
		}
	}
		
	c->next = (a == NULL) ? b : a;
	return head.next;	
}


This is where my compiler craps out. First of all there is the line:
mylist_t *c = &head;
head is of type node_t * not mylist_t * so you can't make this assignment without a cast. Not sure a cast would be a good thing.

Next you use: if(a->value < b->value) the problem here is that a and b are of type mylist_t * and the structure mylist_t does not have a member "value". This type of behavior continues...

I think you mean to have all of these variables of type node_t *
Was This Post Helpful? 0
  • +
  • -

#3 HulkingNightcrawler  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 26-June 08

Re: Merge Sort and Quick Sort

Posted 24 July 2008 - 09:03 PM

View PostNickDMax, on 24 Jul, 2008 - 08:02 PM, said:

Quote

int merge(mylist_t *a, mylist_t *b)
{
	node_t *head;
	mylist_t *c = &head;
	while((a != NULL) && (b != NULL))
	{
		if(a->value < b->value)
		{
			c->next = a;
			c = a;
			a = a->next;
		}
		
		else
		{
			c->next = b;
			c = b;
			b = b->next;
		}
	}
		
	c->next = (a == NULL) ? b : a;
	return head.next;	
}


This is where my compiler craps out. First of all there is the line:
mylist_t *c = &head;
head is of type node_t * not mylist_t * so you can't make this assignment without a cast. Not sure a cast would be a good thing.

Next you use: if(a->value < b->value) the problem here is that a and b are of type mylist_t * and the structure mylist_t does not have a member "value". This type of behavior continues...

I think you mean to have all of these variables of type node_t *


Yea I see what you mean well I revamped my code a little and now it looks like this, so please take a look, I would love to hear some more of your advice.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

/* A struct for a node of the doubly linked list */
/* We will use node_t as the type. "dummytype" is there to make the
compiler happy */
  typedef struct dummytype
  {
		 struct dummytype* prev;  /* Points to the previous node */
		 struct dummytype* next;  /* Points to the next node */
		 int value;			   /* An integer value */
  } node_t;

/* This struct has all the information for a list */
/* The list is implemented as a doubly linked list */
  typedef struct
  {
		 node_t* head;		   /* Points to the head node of the list */
		 node_t* tail;		   /* Points to the tail node of the list */
  } mylist_t;
  int moves = 0;


void myinit(mylist_t *l, int x);
void myPush(mylist_t *l, int x);
void myDumpHead(mylist_t *l);
void printArray(int *array, int entries);
void selection(int* array, int r, int l);
int partition(int* array, int r, int l);
void quickSort(int* array, int r, int l);


int main(int argc, char *argv[])
{
 
  /*Number of items the users would like to sort*/
  int entries;

  /*Random variable I used through the program*/
  int i, j;

  /*Using Dynamic Memory allocation, I created an array off 100 indexes*/
  int* array = (int *)malloc(sizeof(int)*100);
  int* quickArray = (int *)malloc(sizeof(int)*100);
  int* mergeArray = (int *)malloc(sizeof(int)*100);

  /*Variable used to set my list*/
  mylist_t q;

  /*I initialize my list here*/
  myinit(&q, 3);

 

  
  printf("How many entries would you like me to sort??\n");
  scanf("%d", &entries);
  printf("\n");

  /*This gets an array and linked list of random numbers*/
  for(i = 0; i < entries; i++)
  {
		array[i] = rand();
		myPush(&q, array[i]);
		quickArray[i] = array[i];
		mergeArray[i] = array[i];
  }


 
			printf("Unsorted Array\n");
			myDumpHead(&q);
			printf("\n\n");
			selection(array, entries, 0);

			/* This is just for me to double check the array vs. the linked list */
			for(j = 0; j < entries; j++)
			{
				  printf("%d ", array[j]);
			}

			printf("\n");

			printf("Quick Sort\n");
			quickSort(quickArray, 0, entries);

			/* This is just for me to double check the array vs. the linked list */
			for(j = 0; j < entries; j++)
			{
				  printf("%d ", quickArray[j]);
			}

   printf("\n");
   return 0;
}

void myinit(mylist_t *l, int x)
{
	 /*Sets both pointers to NULL when the list is empty*/
	 l->head = l->tail = NULL;
}

void myPush(mylist_t *l, int x)
{
	 node_t *tmp = (node_t *)malloc(sizeof(node_t));

	 tmp->value = x;

	 if(!l->tail)
	 {
		 tmp->next = tmp->prev = NULL;
		 l->head = l->tail = tmp;
	 }
	 else
	 {
		 tmp->next = NULL;
		 tmp->prev = l->tail;
		 l->tail->next = tmp;
		 l->tail = tmp;
	 }
}

void myDumpHead(mylist_t *l)
{
		 node_t *tmp = l->head;

		 for(; tmp; tmp = tmp->next)
		 {
			   printf("%d ", tmp->value);
		 }
}

int swap(int a, int b, int *array)
{

   int t = array[a];
   array[a] = array[b];
   array[b] = t;
   moves++;
   return moves;
}

void printArray(int *array, int entries)
{
	 int i = 0;
	 for(; i < entries; i++)
		   printf("%d ", array[i]);
	 printf("\n");
}

void selection(int* array, int r, int l)
{
		 int i, j, compares, move;
		 compares = -1;
		 move = 0;
		 printf("Selection Sort\n");
		 for(i = l; i < r - 1; i++)
		 {
			   int min = i;

			   for(j = i + 1; j < r; j++)
			   {
					 compares++;
					 if(array[j] < array[min])
					 {
								 min = j;
					 }
			   }

			   printArray(array, r);
			   printf("Compares %d Moves %d\n", compares, move );
			   move = swap(i, min, array);
		 }
}

int partition(int* array, int l, int r)
{
	 int i = l - 1;
	 int j = r;
	 int v = array[r-1];

	 for(;;)
	 {
			while(array[++i] < v);

			while(v < array[--j])
			{
				if(j == l)
				   break;
			}

			if(i >= j)
				 break;

			swap(i, j-1, array);

	  }
	  swap(i , r-1, array);
	  return i;
}

void quickSort(int* array, int l, int r)
{
	 int p;
	 if(r <= l) return;
	 p = partition(array, l , r);
	 quickSort(array, l , p - 1);
	 quickSort(array, p + 1, r);
}

int merge(mylist_t *a, mylist_t *b)
{
		mylist_t *c;

		while((a->head != NULL) && (b->head != NULL))
		{
				if(a->head->value < b->head->value)
				{
						c->head->next = a->head;
						c->head = a->head;
						a->head = a->head->next;
				}

				else
				{
						c->head->next = b->head;
						c->head = b->head;
						b->head = b->head->next;
				}
		}

		c->head->next = (a->head == NULL) ? b->head : a->head;
		return c->head->next->value;
}

int mergeSort(mylist_t *c)
{
		mylist_t *a;
		mylist_t *b;

		if(c->head->next == NULL)
				return c->head->value;
		a->head = c->head;
		b->head = c->head->next;

		while((b->head != NULL) && (b->head->next != NULL))
		{
				c->head = c->head->next;
				b->head = b->head->next->next;
		}

		b->head = c->head->next;
		c->head->next = NULL;

		return merge(mergeSort(a), mergeSort(b));
}


}


Was This Post Helpful? 0
  • +
  • -

#4 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Re: Merge Sort and Quick Sort

Posted 24 July 2008 - 09:45 PM

the ending "}" is unneeded, and the line return merge(mergeSort(a), mergeSort(b )); tries to pass merge two ints.

This post has been edited by NickDMax: 24 July 2008 - 09:45 PM

Was This Post Helpful? 0
  • +
  • -

#5 HulkingNightcrawler  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 26-June 08

Re: Merge Sort and Quick Sort

Posted 25 July 2008 - 10:52 AM

View PostNickDMax, on 24 Jul, 2008 - 09:45 PM, said:

the ending "}" is unneeded, and the line return merge(mergeSort(a), mergeSort(b )); tries to pass merge two ints.


Ok so I revamped my code a little more and I have gotten it to compile but I am getting a Segmentation fault when I try to run the merge sort. I don't have a debugger at hand so I don't know where it is coming from. Thanks for all the help.

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>

/* A struct for a node of the doubly linked list */
/* We will use node_t as the type. "dummytype" is there to make the
compiler happy */
  typedef struct dummytype
  {
		 struct dummytype* prev;  /* Points to the previous node */
		 struct dummytype* next;  /* Points to the next node */
		 int value;			   /* An integer value */
  } node_t;

/* This struct has all the information for a list */
/* The list is implemented as a doubly linked list */
  typedef struct
  {
		 node_t* head;		   /* Points to the head node of the list */
		 node_t* tail;		   /* Points to the tail node of the list */
  } mylist_t;
  int moves = 0;


void myinit(mylist_t *l, int x);
void myPush(mylist_t *l, int x);
void myDumpHead(mylist_t *l);
mylist_t *merge(mylist_t *a, mylist_t *b);
mylist_t *mergeSort(mylist_t *c);

int main(int argc, char *argv[])
{


  /*Number of items the users would like to sort*/
  int entries;

  /*Random variable I used through the program*/
  int i, j;

  /*Variable used to set my list*/
  mylist_t q;

  /*I initialize my list here*/
  myinit(&q, 3);

  printf("How many entries would you like me to sort??\n");
  scanf("%d", &entries);
  printf("\n");

  /*This gets an array and linked list of random numbers*/
  for(i = 0; i < entries; i++)
  {
		array[i] = rand()% 10000;
		myPush(&q, array[i]);
		quickArray[i] = array[i];
		
  }
  
			printf("Unsorted Array\n");
			myDumpHead(&q);
		   
		
		printf("\n");
		printf("Merge Sort\n");
		mergeSort(&q);
		myDumpHead(&q);
		printf("\n");

  /*Production Mode*/

   printf("\n");   
   return 0;
}

void myinit(mylist_t *l, int x)
{
	 /*Sets both pointers to NULL when the list is empty*/
	 l->head = l->tail = NULL;
}

void myPush(mylist_t *l, int x)
{
	 node_t *tmp = (node_t *)malloc(sizeof(node_t));

	 tmp->value = x;

	 if(!l->tail)
	 {
		 tmp->next = tmp->prev = NULL;
		 l->head = l->tail = tmp;
	 }
	 else
	 {
		 tmp->next = NULL;
		 tmp->prev = l->tail;
		 l->tail->next = tmp;
		 l->tail = tmp;
	 }
}

void myDumpHead(mylist_t *l)
{
		 node_t *tmp = l->head;

		 for(; tmp; tmp = tmp->next)
		 {
			   printf("%d ", tmp->value);
		 }
}

mylist_t *merge(mylist_t *a, mylist_t *b)
{
	mylist_t *d;	
	
	while((a->head != NULL) && (b->head != NULL))
	{
		if(a->head->value < b->head->value)
		{
			d->head->next = a->head;
			d->head = a->head;
			a->head = a->head->next;
		}
		
		else
		{
			d->head->next = b->head; 
			d->head = b->head;
			b->head = b->head->next;
		}
	}
		
	d->head->next = (a->head == NULL) ? b->head : a->head;
	return d;	
}

mylist_t *mergeSort(mylist_t *c)
{
	mylist_t *a;
	mylist_t *b;	
	
	if(c->head->next == NULL)
		return c;
	a->head = c->head;
	b->head = c->head->next;
	
	while((b->head != NULL) && (b->head->next != NULL))
	{
		c->head = c->head->next;
		b->head = b->head->next->next;
	}
	
	b->head = c->head->next;
	c->head->next = NULL;
	
	return merge(mergeSort(a), mergeSort(b));
}


Was This Post Helpful? 0
  • +
  • -

#6 perfectly.insane  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 70
  • View blog
  • Posts: 644
  • Joined: 22-March 08

Re: Merge Sort and Quick Sort

Posted 25 July 2008 - 02:50 PM

mylist_t *mergeSort(mylist_t *c)
{
    mylist_t *a;
    mylist_t *b;    
    
    if(c->head->next == NULL)
        return c;
    a->head = c->head;
    b->head = c->head->next;
    
    while((b->head != NULL) && (b->head->next != NULL))
    {
        c->head = c->head->next;
        b->head = b->head->next->next;
    }
    
    b->head = c->head->next;
    c->head->next = NULL;
    
    return merge(mergeSort(a), mergeSort( b ));
}



Well, here is why you get the segfault (well, it might not be the only reason). a and b don't actually point to anything valid, so you can't dereference them. Instead, you should have declared them as mylist_t a, b, and then access head by using a.head, b.head, etc. mergeSort(a) would then need to be mergeSort(&a).

This post has been edited by perfectly.insane: 25 July 2008 - 02:51 PM

Was This Post Helpful? 0
  • +
  • -

#7 HulkingNightcrawler  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 26-June 08

Re: Merge Sort and Quick Sort

Posted 25 July 2008 - 05:51 PM

View Postperfectly.insane, on 25 Jul, 2008 - 02:50 PM, said:

Well, here is why you get the segfault (well, it might not be the only reason). a and b don't actually point to anything valid, so you can't dereference them. Instead, you should have declared them as mylist_t a, b, and then access head by using a.head, b.head, etc. mergeSort(a) would then need to be mergeSort(&a).



I did that and I came up with this:
[code]
mylist_t *merge(mylist_t *a, mylist_t *B)
{
mylist_t d;

while((a->head != NULL) && (b->head != NULL))
{
if(a->head->value < b->head->value)
{
d.head->next = a->head;
d.head = a->head;
a->head = a->head->next;
}

else
{
d.head->next = b->head;
d.head = b->head;
b->head = b->head->next;
}
}

d.head->next = (a->head == NULL) ? b->head : a->head;
return d;
}

mylist_t *mergeSort(mylist_t *c)
{
mylist_t a;
mylist_t b;

if(c->head->next == NULL)
return c;
a.head = c->head;
b.head = c->head->next;

while((b.head != NULL) && (b.head->next != NULL))
{
c->head = c->head->next;
b.head = b.head->next->next;
}

b.head = c->head->next;
c->head->next = NULL;

return merge(mergeSort(&a), mergeSort(&B));
}

But now I am getting the error of "Control reaches end of non-void function" "Incompatible types in return"
I am sorry but I am not good at all at trying to realize where pointers are and stuff, and I don't understand why it won't take my list as return type if I set up the function to return a list. Thanks again.
Was This Post Helpful? 0
  • +
  • -

#8 perfectly.insane  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 70
  • View blog
  • Posts: 644
  • Joined: 22-March 08

Re: Merge Sort and Quick Sort

Posted 25 July 2008 - 06:40 PM

>>> Control reaches end of non-void function

This means you have a function where the return type is not void (i.e. int main(), as opposed to void myfunc()) in which you have a case where the function ends without a return statement.... i.e.:

int addnums(int x, int y)
{
	int z = x + y;
	// no return statement...
}



Or even more complicated cases, where there is a possibility of ending the function at a point other than a return statement (such as if there is a return statement in an if block, but none outside of it at the bottom of the function).

>>> Incompatible types in return

This means the value that a function is trying to return does not match what it is defined to return. Such as return "hello"; in a function defined as int func().
Was This Post Helpful? 0
  • +
  • -

#9 perfectly.insane  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 70
  • View blog
  • Posts: 644
  • Joined: 22-March 08

Re: Merge Sort and Quick Sort

Posted 25 July 2008 - 06:51 PM

I'm also thinking that there is little actual need to use pointers for mylist_t itself in any of the cases (mylist_t contains pointers, but doesn't really need to be a pointer itself). The sorted list is returned from the final call to the merge function, so there is little need to actually modify the input arguments. That is what is causing the error message... returning a mylist_t from merge, when the return type is mylist_t*.
Was This Post Helpful? 0
  • +
  • -

#10 HulkingNightcrawler  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 26-June 08

Re: Merge Sort and Quick Sort

Posted 25 July 2008 - 08:10 PM

View Postperfectly.insane, on 25 Jul, 2008 - 06:51 PM, said:

I'm also thinking that there is little actual need to use pointers for mylist_t itself in any of the cases (mylist_t contains pointers, but doesn't really need to be a pointer itself). The sorted list is returned from the final call to the merge function, so there is little need to actually modify the input arguments. That is what is causing the error message... returning a mylist_t from merge, when the return type is mylist_t*.


Ok well I have been working on this merge sort all night long, and I have gotten no where with it. Thanks a bunch for all your help, but I think this is just gonna go no where. I have to be doin something wrong, but I cannot tell what it is to save my life. I just dont understand how to fix these errors, please is you can point me into another direction?? Thanks
Was This Post Helpful? 0
  • +
  • -

#11 perfectly.insane  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 70
  • View blog
  • Posts: 644
  • Joined: 22-March 08

Re: Merge Sort and Quick Sort

Posted 25 July 2008 - 10:47 PM

Whatever way you decide to go from here, remember that you should not return a pointer to a local variable in a function from that function. For example, for merge, you should not return &d; as d is invalid once the function call has completed.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1