Problem with sorting program

[churni]

hi guys, this is my first post to the forum although i do use this website regularly for help. now i have a problem with my code for a sorting program i am making.

basically the program is used to make a random number list and then you should be able to sort the list using bubble sort, merge sort, heap sort and a tree based sort (i have no idea how to implement the last two of these)

i am a beginner at c and my code might be a mess but any help would be greatly appreciated.

a problem i am having is -
when i open the program and create the random numbers and then do a bubble sort, all is well and everything gets sorted properly. but then when i close the program and re open it and then do a bubble sort on the same set of numbers, for some reason, the sorted list has a new entry of 0.000... at position 1

its as if i have to insert a -1 somewhere so that it deletes this first value but i don't know where, and also why this problem only occurs when i re open the program.

(there is no problem when merge sort tries to do this by the way)

i will insert the code in the next post.

thanks

[churni]

/************bubble sort******************************************************/
void bubblesort ( int i){
     
     int x,y,j;
     float temp;
     char buff[BUFSIZ];
     float a[N];
     FILE *in;
     in=fopen("rand.txt","r");
   
    i=0;
    while(fgets(buff,BUFSIZ,in)!=NULL){
          a[i]=atof(buff);
	      i++;
    }
     
    for(x = 0; x < i; x++)
      for(y = 0; y < i; y++){
            compares(1); //1 comparsion made
            if(a[y] > a[y+1]){
                  temp = a[y+1];
                  a[y+1] = a[y];
                  a[y] = temp;
                  moves(2);
            }// end of if
      }//end of for
      
      printf("%d floats merge sorted in %ld moves using %ld comparisons\n"
		                      ,i+1,moves(0),compares(0));
      if(dupe(i,a))
            printf("Duplicate keys found\n");
      else
            printf("All keys unique\n");
            
      getch();
  
       /* now output sorted data in a paged listing */
      for(j=0;j<=i;j++){
           if(j%20==0){
	       printf("press a key to continue\n");
	       
           getch();
	       system("cls"); 
	       }
      
      printf("number %d is %lf\n",j+1,a[j]);
      }
  
      getch();
}//end of bubble sort

[Ancient Dragon]

you will have to post the entire program because there is no way anyone can determine the problem from the little code you posted.

[Aia]

/************bubble sort******************************************************/
void bubblesort ( int i){
     
     int x,y,j;
     float temp;
     char buff[BUFSIZ];
     float a[N];
     FILE *in;
     in=fopen("rand.txt","r");
   
    i=0;
    while(fgets(buff,BUFSIZ,in)!=NULL){
          a[i]=atof(buff);
	      i++;
    }

Let me analyze the first fifteen lines. void bubblesort ( int i){ That i parameter will become a copy of the argument, since you assign 0 to it before using it, there's not much sense on that parameter.

void bublesort (void) {
    int i = 0;
}

There's no provision to prevent blowing out the array a.
If rand.txt contains more lines that N you would be writing into memory that you should not.

/* the while loop will continue even if a[] is full */
while(fgets(buff,BUFSIZ,in)!=NULL){
       /*
        * atof() returns 0.0 
        * if it can not convert successfully           
        * it needs to be checked before assigning it to a[]
        */
        a[i]=atof(buff);
        i++;

[churni]

sorry guys, thanks so much for taking a look at this.
like i said i'm really a newby to this and i don't know what some of the code is doing its just guess work really like that int i bit you commented on. i've inserted my code below and i know its a total mess and that my read in code needs to be put into another function but i've forgotten how to do that too!!

if someone could help on the original problem outlined i would appreciate it very much.

thanks

//* Basic Sort Function Program *//

// Date: 18th March 2010
// Version: 1.1
// ----------------------------------------------------------------------------

// include directory libraries -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>
#include <math.h>
#include <time.h>
#define N 5000
//-----------------------------------------------------------------------------



// declare maximum values -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-



//-----------------------------------------------------------------------------

// declare functions -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
int random (int i);  // creates random numbers

void sort(float *a,int low,int high);
   /* parameters: starting address of array and low and high indexes */
void merge(float *low1,float *high1, float *high2);
  /* parameters: pointers to low and high elements of half 1 
      calculates low element of half 2 as high1+1 and gets high
      element of half 2 directly */

long moves(int mode);

long compares(int mode);

int dupe(int i,float *a);

void bubblesort ( int i);

void merge(int i);    // does merge sort

char menu(void);  //displays main menu and returns option selected
//-----------------------------------------------------------------------------

// Main function -*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*-*
int main(void){
	int i, j;                         // number of records in database table
	int finish=0;                      // 0 means continue loop. 1 means quit
	char option='z';                   // menu option

//	PRODUCT db[10];                    // array storing database table
//	count=inputdb(db);                 // function to read in file

	do{                                // Do while loop to keep the menu always coming up after functions
		option=menu();
		switch(option){
			case 'r': case 'R':{       // when 'r' pressed
				random(i);     // the display function is done
				break;                 // and the do loop is broken out of
			}

			case 'm': case 'M':{       // when 'm' pressed
				merge(i);              // the merge function is done
				break;                 // and the do loop is broken out of
			}
			
			case 'b': case 'B':{       // when 'b' pressed
				bubblesort(i);              // the bubblesort function is done
				break;                 // and the do loop is broken out of
			}

			case 'q': case 'Q':{       // when 'q' pressed
                finish=1;              // finish is set to 1 meaning the loop breaks 
				break;                 // and the do loop is broken out of
			}
			default:{                  // when anything other than 'case' is pressed
				printf("option: %c not valid\n\n",option); // display a message to user
				break;                 // and the do loop is broken out of
			}
		}

	}while(! finish);                  // now the do is broken

	printf("press any key to exit\n\n"); // display a user message
	getch();                           // holds the screen display
	return 0;
}                                      // end of main

/*=========================DISPLAY MENU & INPUT==============================*/
char menu(void){                        //displays main menu and returns option selected
	char option='z';                    //option input : invalid default value z
	// display the menu - with formatting and user prompt 
    printf("         enter     for option\n");
	printf("         =====   ==============\n");
	printf("           r     generate Random numbers\n");
	printf("           b     Bubble sort\n");
	printf("           m     Merge sort\n");
	printf("           h     Hash table\n");
	printf("           t     Tree sort\n");
	printf("           c     Compare sorts\n");
	printf("           q     Quit */\n\n");
	printf(">> ");
    scanf("%c",&option);                // read in the input from the user
	fflush(stdin);                      // get rid of pesky newline from input buffer
	return option;                      // return the input selection to the main function
}                                       // end of menu function
/*===========================================================================*/

/*==========================Generate random numbers============================*/
int random (int i)
{
         time_t t;
         int num;
         float numbers;
         FILE *fh;
         fh=fopen("rand.txt","w");

         
         srand((unsigned) time (&t));
         do{
            printf("enter number of random numbers you wish to generate\n");
            printf("it must be either 100, 200, 500, 1000, 2000, or 5000:\n");
            scanf("%d",&num);
            fflush(stdin);                             //avoid using \n after enter number
            if (num != 10 && num != 100 && num != 200 && num != 500 && num != 1000 && num != 2000 && num != 5000) {
               printf("Error: you are trying to generate an invalid amount!\n\n");
               }
            } while ((num != 10 && num != 100 && num != 200 && num != 500 && num != 1000 && num != 2000 && num != 5000));
                          // while the number entered is incorrect, keep asking user for number
                                   
         printf("random numbers from 0 to 99:\n\n");
         for(i=0; i<num; i++){
                  numbers = ((long int)((double)rand()*(double)rand()) %1000000l) /10000.0;
                  printf("%lf\n",numbers);
                  fprintf(fh,"%lf\n",numbers);
         }
         
         fclose(fh);
         getch();
         return 0;
}                                       // end of random function
/*===========================================================================*/

///*===========================merge sort============================*/
void merge (int i) {

     int j;
     char buff[BUFSIZ];
     float a[N];
     FILE *in;
     in=fopen("rand.txt","r");
     FILE *out;
     out=fopen("mergesort.txt","w");
     FILE *out2;
     out2=fopen("comparemerge.txt","w");
  

  /* input numbers: reads up to 5000 floats in text format from rand.txt file
      into array a[] */
     i=0;
     while(fgets(buff,BUFSIZ,in)!=NULL){
           a[i]=atof(buff);
	       i++;
     }

     sort(a,0,--i); /* sort the array a[] into ascending order */

     printf("%d floats merge sorted in %ld moves using %ld comparisons\n"
		 ,i+1,moves(0),compares(0));
     if(dupe(i,a))
            printf("Duplicate keys found\n");
     else
            printf("All keys unique\n");
  
     fprintf(out2, "%d floats merge sorted in %ld moves using %ld comparisons\n"
		 ,i+1,moves(0),compares(0));
  
     getch();
             
             /* now output sorted data in a paged listing */
     for(j=0;j<=i;j++){
         if(j%20==0){
	          printf("press a key to continue\n");
	          getch();
	          system("cls"); 
	          }//end of if
         printf("number %d is %lf\n",j+1,a[j]);
	     fprintf(out,"%lf\n",a[j]);
     } //end of for
  
     getch();
} /* end of main function */

/*===========================================================================*/

/***************count number of moves*****************/
long moves(int mode){
	// adds to i in counting mode (>0), returns i
	static int i=0;
	if(mode)
		i+=mode;
	return i;
}
/***************count number of comparidsons*****************/
long compares(int mode){
    //adds to i in counting mode (>0), returns i
	static int i=0;
	if(mode)
		i+=mode;
	return i;
}
/*==========================WRITE OUT MERGE SORT TO A FILE========================*/
void outmerge(int count){       //outputs to db
	int i;
	FILE *out;
	out=fopen("mergesort.txt","w");           // write out to the file mergesort.txt

	fclose(out);
} 
                                          // end of outputdb function
///*===========================================================================*/
//
/*==========================write OUT compare info TO A FILE========================*/
void outcomparemerge(int count){       //outputs to db
	int i;
	FILE *out2;
	out2=fopen("comparemerge.txt","w");           // write out to the file mergesort.txt

	fclose(out2);
} 
                                          // end of outputdb function
///*===========================================================================*/

///*===========================================================================*/
void sort(float *a,int low,int high){
  /* sort numbers by sorting array in two halves then merging 2 halves */
  int mid;
  if(high==low) return; /* only 1 element, already sorted */
  mid=(low+high)/2;
  sort(a,low,mid);  /* sort 1st half of array */
  sort(a,mid+1,high);  /* sort 2nd half of array */
  merge(a+low,a+mid,a+high); /* merge 2 halves of array */
} /* end of sort function */

/***************check for duplicate keys*****************/
int dupe(int i,float *a){ /*returns 1 if duplicate keys found in sorted array
                   or a 0 if all keys unique*/
  int x=0;
  for(x=0;x<i-1;x++){
     if(a[x]==a[x+1])
     return 1;
  }
  return 0;    
}

//******************************************************************************
void merge(float *low1,float *high1, float *high2){
  float *low2=high1+1; /* bottom of second half starts at 
                                      next position after top of first half */
  float *low=low1; /* place to block copy merged data back */
  static float comb[N],*combpos; 
          /* pointer to combined storage for merged data */
  size_t combsize,i;
  combsize=(((size_t)high2-(size_t)low1)/sizeof(float))+1; /* number of floats */
  combpos=comb;

  while(low1<=high1&&low2<=high2){
    compares(1);   /* next statement is a comparison */
    if(*low1 <= *low2){
       /* copy next value from lower half to combined */
      *combpos=*low1;
      combpos++;
      low1++;
    } else {
       /* copy next value from upper half to combined */
      *combpos=*low2;
      combpos++;
      low2++;
    } /* end of else */
  } /* end of while */


  /* at most 1 of next 2 loops will operate */
  while(low1<=high1){ /* copy remaining items in 1st half to combined */
     *combpos=*low1;
     combpos++;
     low1++;
  }
  while(low2<=high2){ /* copy remaining items in 2nd half to combined */
     *combpos=*low2;
     combpos++;
     low2++;
  }

  /* copy merged data back from combined storage to original */
  for(i=0;i<combsize;i++){
    *(low+i)=*(comb+i);
    moves(2); /* each item had to be moved twice */

  }
} /* end of merge function */


/************bubble sort******************************************************/
void bubblesort ( int i){
     
     int x,y,j;
     float temp;
     char buff[BUFSIZ];
     float a[N];
     FILE *in;
     in=fopen("rand.txt","r");
   
    i=0;
    while(fgets(buff,BUFSIZ,in)!=NULL){
          a[i]=atof(buff);
	      i++;
    }
     
    for(x = 0; x < i; x++)
      for(y = 0; y < i; y++){
            compares(1); //1 comparsion made
            if(a[y] > a[y+1]){
                  temp = a[y+1];
                  a[y+1] = a[y];
                  a[y] = temp;
                  moves(2);
            }// end of if
      }//end of for
      
      printf("%d floats merge sorted in %ld moves using %ld comparisons\n"
		                      ,i+1,moves(0),compares(0));
      if(dupe(i,a))
            printf("Duplicate keys found\n");
      else
            printf("All keys unique\n");
            
      getch();
  
       /* now output sorted data in a paged listing */
      for(j=0;j<=i;j++){
           if(j%20==0){
	       printf("press a key to continue\n");
	       
           getch();
	       system("cls"); 
	       }
      
      printf("number %d is %lf\n",j+1,a[j]);
      }
  
      getch();
}//end of bubble sort

[Ancient Dragon]

line 61: the value of variable i has not been initialized. As Aia already mentioned, get rid of the i parameter in the three functions that are called from main() with it. Just declare the variable local to each of those functions.

I see that problem on the very first attempt. I asked it to generate 100 numbers and it said that it generated 101.

[edit]Ok, your program works ok, it's just that you are printing the wrong numnber

printf("%d floats merge sorted in %ld moves using %ld comparisons\n"
		                      ,i+1,moves(0),compares(0));

That i+1 should only be i because the value of i already contains the number of items in the array.
[/edit]

[churni]

ok i have done that but i am now still gettin issues when i use bubblesort. when i've made my 10 random numbers, merge sort will sort them 10 numbers fine in the same session or even when the program is closed and reopened whereas bubble sort is for some reason adding a value or adding a blank to the array so that there are 11 numbers being sorted if that makes sense

[WaltP]

Then look at your for loops. Are the middle comparisons correct?

[churni]

the i+1 is just so that the counting of the array prints out to start at 1. i don't think that has anything to do with the numbers in the array... or am i wrong?

and i have no idea if the comparisons are correct or not. thats something that one of my friends had helped me with. it seems to sort the numbers correctly. its just the issue of it adding a gap when it prints out the sorted list in bubble sort

[Ancient Dragon]

Yes, bubblesort() still has two more problems

First, the sort algorithm doesn't work right.

for(x = 0; x < i-1; x++)
      for(y = x+1; y < i; y++){
            compares(1); //1 comparsion made
            if(a[x] > a[y]){
                  temp = a[x];
                  a[x] = a[y];
                  a[y] = temp;
                  moves(2);
            }// end of if
      }//end of for

second, the loop is incorrect when displaying the array for(j=0;j<=i;j++){ that should be j < i not j <= i

[WaltP]

the i+1 is just so that the counting of the array prints out to start at 1. i don't think that has anything to do with the numbers in the array... or am i wrong?

and i have no idea if the comparisons are correct or not. thats something that one of my friends had helped me with. it seems to sort the numbers correctly. its just the issue of it adding a gap when it prints out the sorted list in bubble sort

Maybe this will help you understand the Bubble Sort better.

[churni]

i have changed my bubblesort code to what you have advised - but now the numbers are not being sorted. if you look at the output now, the numbers are jumbled up as if random.

and also, on the first run of bubble sort, it says there are 0 comparisons and 0 moves while on second run, it gives values.

the second error is fixed now though thanks.

[churni]

thanks, the original issue i had is now sorted. but now that i have changed the sort code as you've advised, the list is not being sorted - nor is it telling me how many comparisons are done on the firt time i do the bubble sort.

[WaltP]

Then you did it wrong. But my psychic powers aren't working today so I can't tell why.

[churni]

i'm so sorry to you both! DURH, i just read through the code and forgot to change one line!

can you please both help me one one more thing.

basically you can see how it says that there are so many moves and so many comparisons. well basically, each time that line is coming up, instead of showing how many comparisons there were, it seems to be adding the comparisons to any comparisons which were done in a previous test.

how would i change the code so that everytime the test is done, it resets the value before it prints out the comparisons?

[WaltP]

:icon_rolleyes:
Now you're getting really heavy into "I'm not going the think anymore, I'll just let them tell me what to do."

[churni]

haha, ok fair play. i think i'm getting a little bit excited about my first thread on here. sorry.

thanks for your help so far anyway. if there was any way i could give you more rep than i can, i would, but unfortunately i can't :(

[WaltP]

Have a beer for me. That'll do....

[churni]

not yet, once my programs done maybe... whenever that'll be!