Programming Forums > Application Development > C

AusTex · Apr 30th, 2005, 8:11 PM

I am working on a merge sort of two files of integers, and am fuzzy on some of the logic\syntax. I need two threads, each of which will open a file, read its contents into an array, and then sort the array using qsort. One thread will operate on file f1.dat(10000 numbers) and leave its sorted contents in array x, while the other will use file f2.dat(11999 numbers) and array y. When the threads have finished, I need to merge x and y into array z so that z is also sorted. Also, I am wanting to use one function for both threads, passing the array, its size, and the name of the file in a structure.

Currently, I have a struct set up with the arrays, their sizes, and the name of the two files, a comparison function for qsort, a sort function for the contents of the files, a merge sort for the z array, and of course the creation of the threads.

I think the biggest area I have questions about is how to properly pass a structure to a generalized sort function and then sort data using that structure parameter.

So far:

(Toggle Plain Text)

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <pthread.h>

typedef struct Data
{
  int x[10000];
  int y[12000];
  int size;
  char *filename;
} data_t;


// Comparison function for qsort
int cmpint (int *a, int *b)
{
  if (*a < *b)
     return -1;
  else
     if (*a > *b)
       return 1;
     else
       return 0;
}


// Sort contents of files
// How to generalize this to work with two separate arrays???????
void *sort(void *data)
{
  FILE *fp;
  //long lSize = ftell (fp);
  fp = fopen(filename.x[], "rb");
  fread(x, 10000, size, fp);

  // data_t *my_data = (data_t *) data;

  qsort(x,1000,sizeof(int),cmpint);
  pthread_exit(0);

}


int main()  {

  int i=0,j=0,k=0;
  char z[22000];
  pthread_t px, py;

  pthread_create(&px, NULL, sort, (void *) &data_x);
  pthread_create(&py, NULL, sort, (void *) &data_x);

  pthread_join(px, 0);
  pthread_join (py, 0);

  // Merge x and y into z, sorted
  while (i<1000 || j < 1000)
  {
    if (j == 1000)
       z[k++]=x[i++];

    else
       if (i<1000 && (x[i]<y[j]))
          z[k++]=x[i++];
    else
          z[k++]=y[j++];
  }


}

mackenga · May 1st, 2005, 4:58 PM

Hmm. You call qsort(). So do I take this to mean you want to have two threads each quicksort half of the array, then merge the two together? I'm doubtful of the point in this unless you have multiple processors and your system will arrange for each thread to run on one of them.

Well, I think the way to do this would be to load half of the file into one array and half into another, then have your threads each take one and qsort() it, then wait for the threads to end (with pthread_join() if my memory serves me intermittently, but don't trust me on this). Then the main program could do the merge into one big array.

I hope this answer belongs more to the solution set than the problem set.

Apr 30th, 2005, 8:11 PM	#1
AusTex Newbie Join Date: Feb 2005 Posts: 7 Rep Power: 0	threaded merge sort help I am working on a merge sort of two files of integers, and am fuzzy on some of the logic\syntax. I need two threads, each of which will open a file, read its contents into an array, and then sort the array using qsort. One thread will operate on file f1.dat(10000 numbers) and leave its sorted contents in array x, while the other will use file f2.dat(11999 numbers) and array y. When the threads have finished, I need to merge x and y into array z so that z is also sorted. Also, I am wanting to use one function for both threads, passing the array, its size, and the name of the file in a structure. Currently, I have a struct set up with the arrays, their sizes, and the name of the two files, a comparison function for qsort, a sort function for the contents of the files, a merge sort for the z array, and of course the creation of the threads. I think the biggest area I have questions about is how to properly pass a structure to a generalized sort function and then sort data using that structure parameter. So far: (Toggle Plain Text) #include <stdio.h> #include <unistd.h> #include <stdlib.h> #include <pthread.h> typedef struct Data { int x[10000]; int y[12000]; int size; char filename; } data_t; // Comparison function for qsort int cmpint (int a, int b) { if (a < b) return -1; else if (a > b) return 1; else return 0; } // Sort contents of files // How to generalize this to work with two separate arrays???????* void sort(void data) { FILE fp; //long lSize = ftell (fp); fp = fopen(filename.x[], "rb"); fread(x, 10000, size, fp); // data_t my_data = (data_t ) data; qsort(x,1000,sizeof(int),cmpint); pthread_exit(0); } int main() { int i=0,j=0,k=0; char z[22000]; pthread_t px, py; pthread_create(&px, NULL, sort, (void ) &data_x); pthread_create(&py, NULL, sort, (void ) &data_x); pthread_join(px, 0); pthread_join (py, 0); // Merge x and y into z, sorted while (i<1000 \|\| j < 1000) { if (j == 1000) z[k++]=x[i++]; else if (i<1000 && (x[i]<y[j])) z[k++]=x[i++]; else z[k++]=y[j++]; } } #include <stdio.h> #include <unistd.h> #include <stdlib.h> #include <pthread.h> typedef struct Data { int x[10000]; int y[12000]; int size; char filename; } data_t; // Comparison function for qsort int cmpint (int a, int b) { if (a < b) return -1; else if (a > b) return 1; else return 0; } // Sort contents of files // How to generalize this to work with two separate arrays??????? void sort(void data) { FILE fp; //long lSize = ftell (fp); fp = fopen(filename.x[], "rb"); fread(x, 10000, size, fp); // data_t my_data = (data_t ) data; qsort(x,1000,sizeof(int),cmpint); pthread_exit(0); } int main() { int i=0,j=0,k=0; char z[22000]; pthread_t px, py; pthread_create(&px, NULL, sort, (void ) &data_x); pthread_create(&py, NULL, sort, (void *) &data_x); pthread_join(px, 0); pthread_join (py, 0); // Merge x and y into z, sorted while (i<1000 \|\| j < 1000) { if (j == 1000) z[k++]=x[i++]; else if (i<1000 && (x[i]<y[j])) z[k++]=x[i++]; else z[k++]=y[j++]; } }

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

May 1st, 2005, 4:58 PM	#2
mackenga Professional Programmer Join Date: Mar 2005 Location: Glasgow, Scotland Posts: 314 Rep Power: 4	Hmm. You call qsort(). So do I take this to mean you want to have two threads each quicksort half of the array, then merge the two together? I'm doubtful of the point in this unless you have multiple processors and your system will arrange for each thread to run on one of them. Well, I think the way to do this would be to load half of the file into one array and half into another, then have your threads each take one and qsort() it, then wait for the threads to end (with pthread_join() if my memory serves me intermittently, but don't trust me on this). Then the main program could do the merge into one big array. I hope this answer belongs more to the solution set than the problem set.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Programming Forums > Application Development > C

threaded merge sort help