Thread: Quicksort-1000000-lines problem

  1. #1
    Registered User
    Join Date
    May 2006
    Posts
    6

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

  2. #2
    Awesomefaceradcore bivhitscar's Avatar
    Join Date
    Apr 2006
    Location
    Melbourne, Australia
    Posts
    210
    Could you at least tell us what the errors seem to be. Is it crashing? What errors are being displayed by your compiler?
    it's ironic considerate rarity patron of love higher knowledge engulfs me...

  3. #3
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,817
    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?
    Last edited by hk_mp5kpdw; 06-08-2006 at 05:34 AM.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > char pivot[1000000],temp[1000000],i,j;
    Especially as this is in a recursive function!
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    May 2006
    Posts
    6
    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.....

  6. #6
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Post your latest example which uses 100 as the base size
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  7. #7
    Registered User
    Join Date
    May 2006
    Posts
    6
    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!

  8. #8
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  9. #9
    Registered User
    Join Date
    May 2006
    Posts
    6

    I really cannot get it

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

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Post your latest "working" code, with 10 line setup. What compiler are you using? My guess is some old fossil.


    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 11
    Last Post: 10-07-2008, 06:19 PM
  2. Line Counting
    By 00Sven in forum C Programming
    Replies: 26
    Last Post: 04-02-2006, 08:59 PM
  3. Replies: 6
    Last Post: 05-12-2005, 03:39 AM
  4. Beginner problem with counting lines in a file
    By edd1986 in forum C Programming
    Replies: 3
    Last Post: 03-25-2005, 06:47 PM
  5. Simulation Problem
    By wu_weidong in forum C Programming
    Replies: 1
    Last Post: 03-10-2005, 01:21 AM