help with mergersort im kind of confused

Question

Member #866461

15 Years Ago

I need to use mergesort to sort the data in a file that has the names and ages of 10 different people , first i have to sort the names in ascending ascii order and then i have to sort them by their age but im not sure how to do it this is what i have so far

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define NUMBER_OFPEOPLE 10

typedef struct{

char name[6] ;
int age ;

}people ; 



typedef char byte ; 

void memcopy( byte *to, byte *from, int count ) {  
  
  while (count-- > 0 ) 
    *to++ = *from++ ;

}

int compare_age(  byte *a , byte *b ) {
  
int aa ;
int bb ; 

 aa = ((people *)a)->age ;
 bb = ((people *)b)->age ;

 if (aa < bb) return 1 ;
 if (aa > bb) return -1 ;
   
return 0 ;
}

int compare_name(  byte *a , byte *b ) {

char aa[6] ;
char bb[6] ;

 strcpy(aa, ((people *)a)->name) ;
 strcpy(bb, ((people *)b)->name) ;

 return strcmp(aa, bb) ;

}

void merge_sort(byte data[], int n , int elementsize , int (*p_cmp_f)() ) ;



int main(void){

  int j, n = 10 , i;

people *A ;



people s ;



A=(people *)malloc(sizeof(people)*n) ; 

 if ( A == NULL ) { printf(" Error mallocing \n" ); return -1 ; } 


FILE *fp ;
fp = fopen("people","r") ;
for(j = 0 ; j < 10 ; j++){
fscanf(fp, "%s %d\n",&s.name,&s.age); 

}


  merge_sort( (byte *) A, n , sizeof(people) , compare_name ) ;

  for(j = 0 ; j < 10 ; j++ ) printf("%s"  "%d" , s.name,s.age) ;

  merge_sort( (byte *) A, n , sizeof(people) , compare_age ) ;

  for(i = 0 ; i < 10 ; i++ ) printf("%d"  "%s" , s.age,s.name) ;

return 0 ;

}


















void merge_sort( byte data[], int n, int elementsize, int (*p_cmp_f)( ) )  {

byte *firsthalf ; 
byte *endoffirsthalf ; 
byte *secondhalf ; 
byte *endofsecondhalf ;
byte *resultbuffer , *p_result ; 
int halfsize ; 

if(n <= 1) 
return ; 

halfsize = n/2 ; 
firsthalf = data ; 
secondhalf = data + halfsize * elementsize ; 

merge_sort(firsthalf ,halfsize,elementsize, p_cmp_f) ;
merge_sort(secondhalf,n-halfsize,elementsize,p_cmp_f) ; 

endoffirsthalf = secondhalf ; 
endofsecondhalf = data + n * elementsize ; 
resultbuffer = (byte *) malloc(n * elementsize); 
 p_result = resultbuffer ; 

while(firsthalf < endoffirsthalf && secondhalf < endofsecondhalf ){

if((*p_cmp_f)(firsthalf,secondhalf) < 0) {
memcopy(p_result , firsthalf , elementsize) ; 
firsthalf += elementsize ; 
} else{
memcopy(p_result , secondhalf , elementsize);
secondhalf += elementsize ; 
}

p_result += elementsize ;
 
}
while(firsthalf < endoffirsthalf){
memcopy(p_result,firsthalf,elementsize) ; 
firsthalf += elementsize ; 
p_result += elementsize ; 

}

while( secondhalf < endofsecondhalf){
memcopy(p_result , secondhalf , elementsize ) ; 
secondhalf += elementsize ; 
p_result += elementsize ; 

}
memcopy(data,resultbuffer, n * elementsize) ; 
free(resultbuffer) ;


}

c

3 Contributors
4 Replies
231 Views
5 Days Discussion Span
Latest Post 15 Years Ago Latest Post by Member #866461

Dani AI

Generated 7 Months Ago

Short summary and focused fixes tied to the thread: the actual causes were (a) unsafe/input-reading logic that never filled the array used for sorting and (b) a comparator contract mismatch. As discovered, a comparator for a comparison sort must return a negative value when the first element is “less than” the second, zero when equal, and positive when “greater” — the same convention used by C's sort APIs. For a stable merge, prefer taking the left element when equal (use <= rather than < in the merge decision) so earlier order is preserved. (en.cppreference.com)

Cleaner comparator examples (use direct casts; avoid copying the name strings before comparing):

int cmp_age(const void *a, const void *b) {
  const people *pa = a;
  const people *pb = b;
  if (pa->age < pb->age) return -1;
  if (pa->age > pb->age) return 1;
  return 0;
}

int cmp_name(const void *a, const void *b) {
  const people *pa = a;
  const people *pb = b;
  return strcmp(pa->name, pb->name);
}

Note: strcmp already documents the negative/zero/positive convention used above. Avoid copying into temporary buffers unless necessary. (en.cppreference.com)

Safer file input and buffer rules (avoid overflowing char name[6]): read lines with fgets, parse with sscanf or use fscanf with a field-width specifier, and always check return values of fopen, fgets/fscanf and malloc. Example pattern:

char line[128];
while (i < n && fgets(line, sizeof line, fp)) {
  char namebuf[64];
  int age;
  if (sscanf(line, "%63s %d", namebuf, &age) == 2) {
    strncpy(A[i].name, namebuf, sizeof A[i].name - 1);
    A[i].name[sizeof A[i].name - 1] = '\0';
    A[i].age = age;
    i++;
  }
}

fgets and %<width>s avoid buffer overflow risks; sscanf/fscanf have documented field-width behavior. (cppreference.com)

Extra practical tips: increase the name buffer (e.g., 32 or 64) rather than forcing truncation; check fopen/malloc return values and fscanf/sscanf return counts; use memcpy/memmove from <string.h> instead of custom memcopy unless there's a specific reason; and if the goal is a multi-key sort (age primary, name secondary) either (a) implement a comparator that compares age then name, or (b) rely on a stable merge and do the secondary-key sort first.

All 4 Replies

WolfPack 491 Posting Virtuoso

15 Years Ago

Please tell us what part you are having problems with. Data reading from the file part? Sorting the names in ascending order? or Sorting the ages?
If you are getting compile or link errors, post them.
If you are getting incorrect output, post the input and the output(both expected output and actual output).
It is boring to look through 160+ lines of code without having no idea what we are looking for..

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

Member #866461 · Answer 1 · 2011-03-05T08:14:53+00:00

It compiled I am having problems with the sorting part it doesnt sort anything it just prints out the the name at the bottom of the list 10 times when i run it

input would be something like this

noble 12
nolan 27
nicky 34
scott 38
simon 45
tylor 29
zenas 6
wells 55
vince 19
toney 24

and output would just print : toney 24 10 times

i think my compare_name and compare_age functions are not correct

Adak 419 Nearly a Posting Virtuoso · Answer 2 · 2011-03-05T09:07:37+00:00

When you run across the merry prankster who convinced you to use that sorting code, kick 'em in the a**.

I've looked through this a few times, and it's a toss up between cussing and laughing, I can tell you. ;)

By all means, narrow down the problem! The worst thing in programming, is to have 100 lines of code, in several functions, and then find out "oops!", and have NO IDEA where the error is.

Check major blocks of code, and all functions, as you're programming:

1) Are they syntactically correct (compile w/o errors)?
2) Are they accurate across the range of data you'll be dealing with?

You'd be amazed at how often stupid errors are not found early on, easily, simply because the programmer was "in a hurry". Later, it takes 5 X as long to find the error.

Member #866461 · Answer 3 · 2011-03-09T01:28:31+00:00

if you werent going to help why bother replying? this forum sucks no help at all

but anyways i fixed the mistakes i made i was just reading the data incorrectly and then i didnt do anything with the space i malloced up just copied the data to S and printed it instead of putting it in A and had to fix my compare function

heres my code

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
#define NUMBER_OFPEOPLE 10

typedef struct {

  char name[6] ;
  int age ;

} people ; 

typedef char byte ; 

void memcopy( byte *to, byte *from, int count ) {  
  
  while (count-- > 0 )  *to++ = *from++ ;

}

int compare_age(  byte *a , byte *b ) {
  
  int aa ;
  int bb ; 

   aa = ((people *)a) -> age ;
   bb = ((people *)b) -> age ;

  if (aa > bb) return 1 ;

  if (aa < bb) return -1 ;
   
  return 0 ;
}

int compare_name(  byte *a , byte *b ) {

  char aa[6] ;
  char bb[6] ;

 strcpy(aa, ((people *)a) -> name) ;
 strcpy(bb, ((people *)b) -> name) ;

 return strcmp(aa, bb) ;

}

void merge_sort(byte data[], int n , int elementsize , int (*p_cmp_f)() ) ;

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

  int j, n = 10  ;

  FILE *fp ;

  people *A ;

  people s ;

  A = (people *)malloc(sizeof(people) * n ) ; 

 if ( A == NULL ) { printf(" Error mallocing \n" ); return -1 ; } 

  fp = fopen("people","r") ;

  for ( j = 0 ; j < 10 ; j++ ) {

    fscanf(fp, "%s %d\n", &s.name[0], &s.age ) ; 

    A[j] = s ;

  }

  merge_sort( (byte *) A, n , sizeof(people) , compare_name ) ;

  for(j = 0 ; j < 10 ; j++ ) printf("%s   %d\n" , A[j].name, A[j].age) ;

  merge_sort( (byte *) A, n , sizeof(people) , compare_age ) ;

  printf("\n") ;

  for( j = 0 ; j < 10 ; j++ ) printf("%d  %s\n" , A[j].age, A[j].name) ;

  return 0 ;

}

void merge_sort( byte data[], int n, int elementsize, int (*p_cmp_f)( ) )  {

byte *firsthalf ; 
byte *endoffirsthalf ; 
byte *secondhalf ; 
byte *endofsecondhalf ;
byte *resultbuffer , *p_result ; 
int halfsize ; 

if(n <= 1) 
return ; 

halfsize = n/2 ; 
firsthalf = data ; 
secondhalf = data + halfsize * elementsize ; 

merge_sort(firsthalf ,halfsize,elementsize, p_cmp_f) ;
merge_sort(secondhalf,n-halfsize,elementsize,p_cmp_f) ; 

endoffirsthalf = secondhalf ; 
endofsecondhalf = data + n * elementsize ; 
resultbuffer = (byte *) malloc(n * elementsize); 
 p_result = resultbuffer ; 

while(firsthalf < endoffirsthalf && secondhalf < endofsecondhalf ){

if((*p_cmp_f)(firsthalf,secondhalf) < 0) {
memcopy(p_result , firsthalf , elementsize) ; 
firsthalf += elementsize ; 
} else{
memcopy(p_result , secondhalf , elementsize);
secondhalf += elementsize ; 
}

p_result += elementsize ;
 
}
while(firsthalf < endoffirsthalf){
memcopy(p_result,firsthalf,elementsize) ; 
firsthalf += elementsize ; 
p_result += elementsize ; 

}

while( secondhalf < endofsecondhalf){
memcopy(p_result , secondhalf , elementsize ) ; 
secondhalf += elementsize ; 
p_result += elementsize ; 

}
memcopy(data,resultbuffer, n * elementsize) ; 
free(resultbuffer) ;


}

help with mergersort im kind of confused

Dani AI

Recommended Answers Collapse Answers

All 4 Replies

Recommended Answers