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