Thread: Learning Merge Sort Technique

  1. #1
    *this
    Join Date
    Mar 2005
    Posts
    498

    Learning Merge Sort Technique

    I am beginning to learn the merge sort technique, i will be applying the concepts to a recursive function, but currently i have a linear function that takes in two arrays and merges them. is my interpretation correct, the program works fine no errors, correct output, but have i used too many steps, just making sure i have it correct. thanks.

    btw, ap header files are used, same datatypes can be found in iostream, vector....etc....you know.....

    Code:
    #include <iostream>
    #include <iomanip>
    #include <dice.h>
    #include <apvector.h> 
    using namespace std;
    
    const int SIZE = 200;
    
    void fillArray (apvector<int> &temp);
    void screenOutput (const apvector<int> &temp);
    void swap (int &a, int &b);
    void selectionSort (apvector<int> &list);
    void mergeSort(apvector<int> &listA, 
                   apvector<int> &listB, 
                   apvector<int> &listC);
    
    main()
    {
          apvector<int> listA(SIZE+1); 
          apvector<int> listB(SIZE+1);
          apvector<int> listC((2*SIZE)+1);
          fillArray (listA);
          fillArray (listB);
          selectionSort (listA);
          selectionSort (listB);
          mergeSort (listA, listB, listC);
          screenOutput (listC);
          system("pause");
          return 0;
    }
    
    void fillArray (apvector<int> &temp)
    {
          int  size; 
          cout << "How many numbers to you wish to generate? ";
          cin >> temp[0];
          cout << "Largest integer to generate? ";
          cin >> size;
          cout << endl;
          dice die(size);      // allocate dice object
          for (int loop=1; loop<=temp[0]; loop++)
                temp[loop] = die.roll();
    } 
    
    void screenOutput (const apvector<int> &temp)
    {
          cout << setiosflags (ios::right) << endl;
          for (int loop=1; loop<=temp[0]; loop++)
          {
                cout << setw(4) << temp[loop];
                if (loop % 20 == 0) cout << endl;
          }
          cout << endl;
    } 
    
    void swap (int &a, int &b)
    {
          int temp = a;
          a = b;
          b = temp;
    } 
    
    void selectionSort (apvector<int> &list)
    {
       int flag;
       
       for (int outer = 1; outer < list[0]; outer++)
       {
          flag = outer;
          for (int inner = outer + 1; inner <= list[0]; inner++)
          {
             if (list[inner] < list[flag])
             {
                flag = inner;
             }
          }
          swap(list[outer], list[flag]);
       }
    }
    
    void mergeSort(apvector<int> &listA, 
                   apvector<int> &listB, 
                   apvector<int> &listC)
    {
       listC[0] = listA[0] + listB[0];
       int indexA = 1, indexB = 1, indexC = 1;
       while (indexA <= listA[0] && indexB <= listB[0])
       {
          if (listA[indexA] < listB[indexB])
          {   
             listC[indexC] = listA[indexA];
             indexA++;
             indexC++;
          }
          if (listB[indexB] <= listA[indexA])
          {
             listC[indexC] = listB[indexB];
             indexB++;
             indexC++;
          }
       }
       if (indexA > listA[0])
          for (indexB; indexB <= listB[0]; indexB++)
          {
             listC[indexC] = listB[indexB];
             indexC++;
          }
       else if (indexB > listB[0])
          for (indexA; indexA <= listA[0]; indexA++)
          {
             listC[indexC] = listA[indexA];
             indexC++;
          }
    }

  2. #2
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    715
    At a first glance I'm a little suspicious.
    Will your program merge these two arrays
    A: 3 6 9
    B: 1 6 8 12
    into one array C: 1 3 6 6 8 9 12 ?
    Gotta love the "please fix this for me, but I'm not going to tell you which functions we're allowed to use" posts.
    It's like teaching people to walk by first breaking their legs - muppet teachers! - Salem

  3. #3
    *this
    Join Date
    Mar 2005
    Posts
    498
    tested it and worked

  4. #4
    *this
    Join Date
    Mar 2005
    Posts
    498
    so im guessing i have a correct interpretation...thanks?....

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  2. Natural Merge Sort
    By penny_731729 in forum C Programming
    Replies: 1
    Last Post: 04-28-2003, 04:12 PM
  3. sort algorithm (merge?)
    By mouse163 in forum C++ Programming
    Replies: 1
    Last Post: 04-07-2003, 08:05 AM
  4. help with merge sort
    By maloy in forum C Programming
    Replies: 4
    Last Post: 03-04-2002, 06:22 PM
  5. merge sort
    By Unregistered in forum C Programming
    Replies: 6
    Last Post: 03-01-2002, 03:16 PM