Quicksort-1000000-lines problem

hi, i m having some problems with my program. Would appreciate any help. I am supposed to sort over 10000 lines of characters using quicksort. I cannot seem to tell what is wrong with the one i have come up with. Thank you for your attention!

here is my code

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#define MAXLINE 1000000
#define MAXWORD 1000000

void quicksort(char *data[], int low, int high);
int main(void)
{
	clock_t start , end;
	int i;
	char *data[MAXLINE], *tmp, buffer[MAXWORD];

	for (i = 0; i < MAXLINE; i++) {
		if (gets(buffer) == NULL) break;
		if ((tmp = malloc(strlen(buffer) + 1)) == NULL) exit(-1);
		strcpy(tmp, buffer);
		*(data + i) = tmp;
	}
	*(data+i) = NULL;

	start = clock();
       	quicksort(data,0,i-1);
	end = clock();

	for (i = 0; data[i]; i++) {
	  fprintf(stdout, "%s\n", data[i]);
	  free(data[i]);
	}

	fprintf(stderr, "\n****************\n%f sec\n****************\n", (double)(end - start) / CLOCKS_PER_SEC);
	return (0);
}


void quicksort(char *data[], int low, int high)
{
	char pivot[1000000],temp[1000000],i,j;
	i=low;
	j=high;
	
	strcpy (pivot, data[(low+high)/2]);
	
	do
	{
		while ((strcmp(data[i],pivot))<1) 
		i++;
		while ((strcmp(data[j],pivot))>1)
		j--;
		if (i<=j)
		{
			strcpy (temp, data[i]);
			strcpy (data[i], data[j]);
			strcpy (data[j], temp);
		       	i++;
		       	j--;
		}
	}
	while (i<=j);
	
       	if (low<j) quicksort(data, low,j);
	if (i<high) quicksort(data, i, high);
}

Could you at least tell us what the errors seem to be. Is it crashing? What errors are being displayed by your compiler?

Code:

#define MAXWORD 1000000

int main(void)
{
    char *data[MAXLINE], *tmp, buffer[MAXWORD];

    ...


void quicksort(char *data[], int low, int high)
{
    char pivot[1000000],temp[1000000],i,j;

    ...

You might be having problems trying to declare 1 million+ or 2 million+ bytes on the local stack. This might need to be declared dynamically or maybe globally. Can't you use the standard qsort function which implements the quicksort algorithm instead?

> char pivot[1000000],temp[1000000],i,j;
Especially as this is in a recursive function!

when i try to run the program, i get "segmentation fault (core dumped)" which indicates some fault in the memory allocation. However when i try to lower the number to say just 100 instead of 1000000, the program does not churn out any results at all.

We were specifically told not to use qsort. i wish i could have used that though.....

Post your latest example which uses 100 as the base size

it does not seem to work even if i make MAXLINE and MAXWORD to be 100. When i look into the program in detail, it seems to me that the problem arises from the quicksort function that i have written. It does not proceed beyond

Code:

	strcpy (pivot, data[(low+high)/2]);

the error after trying to run the program was Segmentation fault (core dumped)

here is my program anyway.

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#define MAXLINE 100
#define MAXWORD 100

void quicksort(char *data[], int low, int high);
int main(void)
{
	clock_t start , end;
	int i;
	char *data[MAXLINE], *tmp, buffer[MAXWORD];

	for (i = 0; i < MAXLINE; i++) {
		if (gets(buffer) == NULL) break;
		if ((tmp = malloc(strlen(buffer) + 1)) == NULL) exit(-1);
		strcpy(tmp, buffer);
		*(data + i) = tmp;
	}
	*(data+i) = NULL;

	start = clock();
       	quicksort(data,0,i-1);
	end = clock();

	for (i = 0; data[i]; i++) {
	  fprintf(stdout, "%s\n", data[i]);
	  free(data[i]);
	}

	fprintf(stderr, "\n****************\n%f sec\n****************\n", (double)(end - start) / CLOCKS_PER_SEC);
	return (0);
}


void quicksort(char *data[], int low, int high)
{
  char pivot[100],temp[100];
  int  i,j;
  i=low;
  j=high;
	
	strcpy (pivot, data[(low+high)/2]);
	
	do
	{
		while ((strcmp(data[i],pivot))<1) 
		i++;
		while ((strcmp(data[j],pivot))>1)
		j--;
		if (i<=j)
		{
			strcpy (temp, data[i]);
			strcpy (data[i], data[j]);
			strcpy (data[j], temp);
		       	i++;
		       	j--;
		}
	}
	while (i<=j);
	
       	if (low<j) quicksort(data, low,j);
	if (i<high) quicksort(data, i, high);
}

thank you for your attention!

> it does not seem to work even if i make MAXLINE and MAXWORD to be 100
10, 100, 1000000 - it's all the same as far as the code is concerned.
If it works for one, then it's likely it will work for all of them.
So pick small numbers to test with.

Code:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

#define MAXLINE 5
#define MAXWORD 100

void quicksort(char *data[], int low, int high);

int main(void)
{
  clock_t start , end;
  int i;
  char *data[MAXLINE], *tmp, buffer[MAXWORD];

  for (i = 0; i < MAXLINE; i++) {
    if (gets(buffer) == NULL) break;
    if ((tmp = malloc(strlen(buffer) + 1)) == NULL) exit(-1);
    strcpy(tmp, buffer);
    data[i] = tmp;
  }
  // this steps off the array
  // *(data+i) = NULL;

  start = clock();
  quicksort(data,0,MAXLINE-1);
  end = clock();

  // you know the count, so use it
  // rather than testing for mythical NULL
  for (i = 0; i < MAXLINE; i++) {
    fprintf(stdout, "%s\n", data[i]);
    free(data[i]);
  }

  fprintf(stderr, "\n****************\n%f sec\n****************\n",
      (double)(end - start) / CLOCKS_PER_SEC);
  return (0);
}


void quicksort(char *data[], int low, int high)
{
  char pivot[MAXWORD];
  int  i,j;
  i=low;
  j=high;

  strcpy (pivot, data[(low+high)/2]);

  do
  {
    // strcmp equality returns 0, not 1
    while ((strcmp(data[i],pivot))<0)
    i++;
    while ((strcmp(data[j],pivot))>0)
    j--;
    if (i<=j)
    {
      /* you just have pointers here, swap them */
      char *temp = data[i];
      data[i] = data[j];
      data[j] = temp;
      //strcpy (temp, data[i]);
      //strcpy (data[i], data[j]);
      //strcpy (data[j], temp);
      i++;
      j--;
    }
  }
  while (i<=j);

  if (low<j) quicksort(data, low,j);
  if (i<high) quicksort(data, i, high);
}


And my results
$ ./a.exe
now
is
the
time
for
for
is
now
the
time

****************
0.000000 sec
****************

Oh, and read the FAQ on why gets() is bad, and why you should always use fgets() to read input.

Thanks Salem... it did work eventually but... i dunno if the problem is with my computer or something, i cannot sort more than 10 lines with this program. I get the same error "segmentation fault (core dumped) when i attempt to sort more than 10 lines....sigh..i am supposed to sort 10 million lines...

Post your latest "working" code, with 10 line setup. What compiler are you using? My guess is some old fossil.


Quzah.