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

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

Edited 5 Years Ago by Ancient Dragon: n/a

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

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.

Edited 5 Years Ago by Ancient Dragon: n/a

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.

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

Edited 3 Years Ago by Reverend Jim: Fixed formatting

This article has been dead for over six months. Start a new discussion instead.