MergeSort in C++, text file

[Lelly]

Hello,

How can I do this:

Implement the MergeSort algorithm in C++, Generate random numbers into a text file to read as input. The 2 parameters to the program are the input and output text files

Thanks

[Ancient Dragon]

The instructions are not clear enough. Do you have to generate two files that contain random numbers, such use a merge-sort altorithm to merge them into one sorted file? Or generate one large file, split it into two smaller files, then use merge-sort ?

You should start by reviewing these links

[Lelly]

Thanks for your response
the Question is:
Implement the MergeSort algorithm in c++. Generate 512 random numbers as input from http://stattrek.com/Tables/Random.aspx (min value = 0; max value = 99999; allow duplicate entries; no seed) Place these numbers into a text file to read as input. The 2 parameters to the program are the input and output text files.

I hope it is clear now

[Ancient Dragon]

If you only have one text file, what is to be merged? There is no need to merge a list of only 512 numbers. Merge-sort is used when there are millions, or even billions, of numbers because they can't be all in memory at the same time.

But I suppose for academic purposes you could take a file that contains 512 numbers, split the file into two files, sort each file, then merge them. I a real-life situation you would probably have to split the original file into many snaller files. To split the file in half read the first 256 numbers, save them in a text file, then read the remaining numbers and save them in another file.

[Lelly]

So how can I do that, please

[rbross]

Read about the STL template "merge" here.

[Ancient Dragon]

So how can I do that, please

Well, give it a shot and start to program. Start out simple -- first generate the list of random numbers. Only when you are finished with that -- and the program compiles correctly and tested -- should you begin the second part. The second part is to split the file into two smaller files.

We are not going to write the program for you -- just start writing, compiling and testing. You can always post the code you have written here is you come across a problem that you do not understand.

[Lelly]

Thank you very much
Actually i started the program and I almost done but i don't know how to write my sorted array on a text file
can anyone help me to do that, please
This is my program

#include <iostream>

#include <fstream>



      using namespace std;

      //Function Declarations
void mergeSort(int numbers[], int temp[], int array_size);
void m_sort(int numbers[], int temp[], int left, int right);
void merge(int numbers[], int temp[], int left, int mid, int right); 

      int main()

      {

      int j,i= 0 ;
      int a[512];
      int a1[512];


      char *file = "N.txt";

      ifstream txt(file);



      if (!txt) {

      cout << "Error"<< file << endl;

      return 0;

      }

      cout << file << endl;

      while (txt >> j) {

      a[i] = j;
      cout << a[i] << endl;

      i++;

      } cout << i << endl;






    mergeSort(a, a1, 512);

    for (int i = 0; i < 512; i++)
    {
        cout << a[i] <<  endl;

    }//end for


    cout << " The " << i << " random numbers are sorted" <<  endl;

  system( " pause" );
      return 0;
      }



// "Main" function of the sequence 
// From here on out everything is called recursively
void mergeSort(int numbers[], int temp[], int array_size)
{
  m_sort(numbers, temp, 0, array_size - 1);
}


void m_sort(int numbers[], int temp[], int left, int right)
{
  int mid;

  if (right > left)
  {
    mid = (right + left) / 2;
    m_sort(numbers, temp, left, mid);
    m_sort(numbers, temp, (mid+1), right);

    merge(numbers, temp, left, (mid+1), right);
  }
}

void merge(int numbers[], int temp[], int left, int mid, int right)
{
  int i, left_end, num_elements, tmp_pos;

  left_end = (mid - 1);
  tmp_pos = left;
  num_elements = (right - left + 1);

  while ((left <= left_end) && (mid <= right))
  {
    if (numbers[left] <= numbers[mid])
    {
      temp[tmp_pos] = numbers[left];
      tmp_pos += 1;
      left += 1;
    }
    else
    {
      temp[tmp_pos] = numbers[mid];
      tmp_pos += 1;
      mid += 1;
    }
  }

  while (left <= left_end)
  {
    temp[tmp_pos] = numbers[left];
    left += 1;
    tmp_pos += 1;
  }
  while (mid <= right)
  {
    temp[tmp_pos] = numbers[mid];
    mid += 1;
    tmp_pos += 1;
  }

  //modified
  for (i=0; i < num_elements; i++)
  {
    numbers[right] = temp[right];
    right -= 1;
  }
}