1.11M Members

** SORTING EXERCISE HELP **

 
0
 

Ok... Got a lab to generate 150 random numbers and then sort the 1st 50 by BUBBLE SORT, the 2nd 50 by SHELL SORT, and the 3rd 50 by SELECTION SORT. After I get those three to work correctly then I need to MERGE SORT the three of them together.

I've got the 150 random numbers and the bubble sort working, but the shell & selection are off....
I'm sure I have issues with the merge as well but I guess I'll worry about that after the three lists are correct.

ANy ideas/suggestions?

/////////////////////////////////////////////////////////////////////////////////
//*******************************************************************************
//
//   TITLE:             Lab6 - Main Program
//   FILENAME:          Main.cpp
//   PREPARED FOR:      CS230
//   PROGRAMMER(S):     
//   DEVELOPMENT DATE:  12/08/12
//   COMPILER USED:     MS Visual C++ 2010 Express - Version 10
//   TARGET PLATFORM:   x86 Windows Platform
//
//*******************************************************************************
/////////////////////////////////////////////////////////////////////////////////
//
//  *** TEST PLAN ***
//
// 1)  Generate 150 random numbers from between 0 - 1000 and display them
//
// 2)  Take the 1st 50 and display them, then BUBBLE SORT them and display again
//
// 3)  Take the 2nd 50 and display them, then SHELL SORT them and display again
//
// 4)  Take the 3rd 50 and display them, then SELECTION SORT them and display again
//
// 5)  Take the 3 sorted lists and MERGE SORT then together and display final list
//
/////////////////////////////////////////////////////////////////////////////////
#include <cmath>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <windows.h>
using namespace std;


void BubbleSort(int ArraySort_1[ ]);
void ShellSort(int ArraySort_2[ ]);
void SelectionSort(int ArraySort_3[ ]);
void MergeSort(int ArraySort_1[ ],int ArraySort_2[ ], int ArraySort_3[ ]);

void main( )
{
    int InitArray[150], ArraySort_1[50], ArraySort_2[50], ArraySort_3[50];
    cout << endl << "\t   --->  THIS IS THE RANDOMLY GENERATED ARRAY OF 150 ELEMENTS  <---" << endl;
    cout << "\t   ----------------------------------------------------------------" << endl;

    srand ((unsigned) time(0)); 

    for (int i = 0; i < 150; i++)
        {
            InitArray[i] = rand( ) %1000;
            cout << InitArray[i] << " ";
            Sleep(1);
        }

//////////////////////            Bubble Sort            //////////////////////
    cout << endl << endl << endl << endl << "\t * 1A:  THIS IS THE FIRST 50 ELEMENTS OF THE UNSORTED ARRAY  *"<< endl;
    cout << "\t -------------------------------------------------------------" << endl;

    for (int i = 0; i < 50; i++) 
        {
            ArraySort_1[i] = InitArray[i];
            cout << ArraySort_1[i] << " ";
        }

    cout << endl << endl << "\t * 1B:  THIS IS THE BUBBLE SORT OF THE FIRST 50 ARRAY  *" << endl;

    BubbleSort(ArraySort_1);

    for (int i = 0; i < 50; i++)
        {
            cout << ArraySort_1[i] << " ";
        }

//////////////////////            Shell Sort            ////////////////////// 
    cout << endl << endl << endl << endl << "\t ** 2A:  THIS IS THE SECOND 50 ELEMENTS OF THE UNSORTED ARRAY  **" << endl;
    cout << "\t ----------------------------------------------------------------" << endl;

    for (int i = 50; i < 99; i++)
        {
            ArraySort_2[i - 50] = InitArray[i];
            cout << ArraySort_2[i] << " ";
        } 

    cout << endl << endl <<"\t ** 2B:  THIS IS THE SHELL SORT OF THE SECOND 50 ARRAY  **" << endl;

    ShellSort(ArraySort_2);

    for (int i = 0; i < 49; i++)
        {
            cout << ArraySort_2[i] << " ";
        }

//////////////////////            Selection Sort            ////////////////////// 
    cout << endl << endl << endl << endl << "\t *** 3A:  THIS IS THE THIRD 50 ELEMENTS OF THE UNSORTED ARRAY  ***" << endl;
    cout << "\t -----------------------------------------------------------------" << endl;

    for (int i = 100; i < 149; i++)
        {
            ArraySort_3[i - 100] = InitArray[i];
            cout << ArraySort_3[i] << " ";
        }

    cout << endl << endl << "\t *** 3B:  THIS IS THE SELECTION SORT OF THE THIRD 50 ARRAY  ***" << endl;

    SelectionSort(ArraySort_3);

    for (int i = 0; i < 49; i++)
        {  
            cout << ArraySort_3[i] << " ";
        }

//////////////////////            Merge Sort            ////////////////////// 
    cout << endl << endl << endl << endl << "\t **** 4A:  THIS IS THE MERGE SORT OF THE THREE PREVIOUSLY SORTED ARRAYS  ****" << endl;
    cout << "\t --------------------------------------------------------------------------" << endl;

    MergeSort(ArraySort_1, ArraySort_2, ArraySort_3);

    for (int i = 0; i < 99; i++)
        {
            cout << ArraySort_3[i] << " ";
        }

    cout << endl << endl << endl << endl << "\t";
    system ("pause");
    return;
}


//////////////////////            FREEE FUNCTIONS            //////////////////////
void BubbleSort(int ArraySort_1[ ])
{
    int tmp;

    for (int i = 0; i < 49; i++)
        {
            for (int x = 0; x < 49; x++)
                {
                    if (ArraySort_1[x] > ArraySort_1[x + 1])
                        {
                            tmp = ArraySort_1[x];
                            ArraySort_1[x] = ArraySort_1[x + 1];
                            ArraySort_1[x + 1] = tmp;
                        }
                }
        }
}

void ShellSort(int ArraySort_2[ ])
{
    int h, i, j, k, hCnt;
    int increments[20];

    for (h = 1, i = 0; h < 49; i++)
        {
            increments[i] = h;
            h = 3 * h + 1;
        }

    for (i--; i >= 0; i--)
        {
            h = increments[i];

            for (hCnt = h; hCnt < 2 * h; hCnt++)
                {
                    for (j = hCnt; j < 49;)
                        {
                            int tmp = ArraySort_2[j];
                            k = j;

                            while (k - h >= 0 && tmp < ArraySort_2[k - h])
                                {
                                    ArraySort_2[k] = ArraySort_2[k - h];
                                    k -= h;
                                }

                            ArraySort_2[k] = tmp;
                            j += h;
                        }
                }
        }
}

void SelectionSort(int ArraySort_3[ ])
{
    int tmp, min;

    for (int i = 0; i < 50; i++)
        {
            min = i;

            for (int x = i; x < 50; x++)
                {
                    if (ArraySort_3[x] < ArraySort_3[min])
                        {
                            min = x;
                        }
                }

            tmp = ArraySort_3[i];
            ArraySort_3[i] = ArraySort_3[min];
            ArraySort_3[min] = tmp;
        }
}

void MergeSort(int ArraySort_1[ ],int ArraySort_2[ ], int ArraySort_3[ ])
{
    int Tmp1[100];
    int i = 0;

    while ((ArraySort_1[i] < 50) && (ArraySort_2[i] < 50))
        {
            if (ArraySort_1[i] < ArraySort_2[i])
                {
                    Tmp1[i] = ArraySort_1[i];
                    ArraySort_1[i]++;
                    cout << ArraySort_1 << " ";
                }

            else
                {
                    Tmp1[i] = ArraySort_2[i];
                    ArraySort_2[i]++;
                    cout << ArraySort_2 << " ";
                }

            Tmp1[i]++;
        }

    while (Tmp1[i] < 100)
        {
            Tmp1[i] = ArraySort_1[i];
            ArraySort_1[i]++;
            ArraySort_3[i]++;
        }

    while (ArraySort_2[i] < 100)
        {
            Tmp1[i] = ArraySort_2[i];
            ArraySort_2[i]++;
            ArraySort_3[i]++;
        }
}
 
0
 

First off:

void main( )

that's bad, you should use

int main()

This is also bad:

for (int x = i; x < 50; x++)

you shouldn't implicity hard-code these values, it should be the SIZE of the array and not 50 (even though your array length is 50) .. What if more values are added?

EDIT: Just re-read the function, my bad.

 
-1
 

Bump...Bump...

 
0
 

Ok, I've made progress. The BUBBLE, SHELL, and SELECTION SORTS all work and create three new sorted arrays (ArraySort_Bub[ ],ArraySort_She[ ], ArraySort_Sel[ ]). Now I need to MERGE SORT the three sorted arrays into a new sorted array. My MERGE SORT seems to have issues and outputs crap...

Any ideas/comments?

PS - thanks to DECEPTIKON

#include <cmath>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <windows.h>
using namespace std;


const int size = 150;               //total initial array size
const int parts = 50;               //the array divided into three parts
void BubbleSort(int InitArray[ ], int size);
void ShellSort(int InitArray[ ], int size);
void SelectionSort(int InitArray[ ], int size);
void MergeSort(int ArraySort_Bub[ ],int ArraySort_She[ ], int ArraySort_Sel[ ], int parts);


int main( )
{
    int InitArray[size], ArraySort_Bub[parts], ArraySort_She[parts], ArraySort_Sel[parts];

//////////////////////            Random # Generator            //////////////////////
    srand ((unsigned) time(0)); 
    for (int i = 0; i < size; i++)
        {
            InitArray[i] = rand( ) %1000;
            Sleep(1);
        }

//////////////////////            Initial Array            //////////////////////
    cout << endl << "\t   --->  THIS IS THE RANDOMLY GENERATED ARRAY OF 150 ELEMENTS  <---" << endl;
    cout << "\t   ----------------------------------------------------------------" << endl;

    for (int i = 0; i < 50; ++i)
        cout << InitArray[i] << " ";
    cout << endl << endl << "\n";

    for (int i = 50; i < 100; ++i)
        cout << InitArray[i] << " ";
    cout << endl << endl << "\n";

    for (int i = 100; i < 150; ++i)
        cout << InitArray[i] << " ";
    cout << endl << endl << "\n";

//////////////////////            Bubble Sort            //////////////////////
    BubbleSort(InitArray, 50);
    cout << endl << endl << "\t *  THIS IS THE BUBBLE SORT OF THE FIRST 50  *" << endl;
    cout << "\t ---------------------------------------------" << endl;
    for (int i = 0; i < 50; ++i)
    {
        cout << InitArray[i] << " ";
        ArraySort_Bub[i] = InitArray[i];            //put 1st 50 into ArraySort_Bub
    }
    cout << endl << endl << "\n";

//////////////////////            Shell Sort            ////////////////////// 
    ShellSort(InitArray + 50, 50);
    cout << endl << endl <<"\t **  THIS IS THE SHELL SORT OF THE SECOND 50  **" << endl;
    cout << "\t -----------------------------------------------" << endl;   
    for (int i = 50; i < 100; ++i)
    {
        cout << InitArray[i] << " ";
        ArraySort_She[i - 50] = InitArray[i];       //put 2nd 50 into ArraySort_She
    }
    cout << endl << endl << "\n";

//////////////////////            Selection Sort            ////////////////////// 
    cout << endl << endl << "\t *** 3B:  THIS IS THE SELECTION SORT OF THE THIRD 50  ***" << endl;
    cout << "\t --------------------------------------------------------" << endl;
    SelectionSort(InitArray + 100, 50);
    for (int i = 100; i < 150; ++i)
    {
        cout << InitArray[i] << " ";
        ArraySort_Sel[i - 100] = InitArray[i];      //put 3rd 50 into ArraySort_Sel
    }
    cout << endl;


    cout << endl << endl << endl << "\t ***************************  sample output three new arrays[50]  ***************************" << endl;
    for (int i = 0; i < 50; ++i)
        cout << ArraySort_Bub[i] << " ";
    cout << endl << endl << "\n";

    for (int i = 0; i < 50; ++i)
        cout << ArraySort_She[i] << " ";
    cout << endl << endl << "\n";

    for (int i = 0; i < 50; ++i)
        cout << ArraySort_Sel[i] << " ";
    cout << endl << endl << "\n";


//////////////////////            Merge Sort            ////////////////////// 
    cout << endl << endl << endl << endl << "\t ****  THIS IS THE MERGE SORT OF THE THREE PREVIOUSLY SORTED ARRAYS  ****" << endl;
    cout << "\t ------------------------------------------------------------------------" << endl;
    MergeSort(ArraySort_Bub, ArraySort_She, ArraySort_Sel, 50);

    for (int i = 0; i < size; i++)
        {
            cout << InitArray[i] << " ";
        }

    cout << endl << endl << endl << endl << "\t";
    system ("pause");
    return 0;
}


//////////////////////            FREE FUNCTIONS            //////////////////////
void BubbleSort(int InitArray[ ], int size)
{
    int tmp;

    for (int i = 0; i < size - 1; i++)
        {
            for (int x = 0; x < size - 1; x++)
                {
                    if (InitArray[x] > InitArray[x + 1])
                        {
                            tmp = InitArray[x];
                            InitArray[x] = InitArray[x + 1];
                            InitArray[x + 1] = tmp;
                        }
                }
        }
}

void ShellSort(int InitArray[ ], int size)
{
    int h, i;
    int increments[100];

    for (h = 1, i = 0; h < size - 1; i++) 
    {
        increments[i] = h;
        h = 3 * h + 1;
    }

    for (i--; i >= 0; i--) 
    {
        h = increments[i];
        for (int hCnt = h; hCnt < 2 * h; hCnt++) 
        {
            for (int j = hCnt; j < size;) 
            {
                int tmp = InitArray[j];
                int k = j;

                while (k - h >= 0 && tmp < InitArray[k - h]) 
                {
                    InitArray[k] = InitArray[k - h];
                    k -= h;
                }

                InitArray[k] = tmp;
                j += h;
            }
        }
    }
}

void SelectionSort(int InitArray[ ], int size)
{
    for (int i = 0; i < size; i++) 
    {
        int min = i;

        for (int x = i; x < size; x++) 
        {
            if (InitArray[x] < InitArray[min])
                min = x;
        }

        int tmp = InitArray[i];
        InitArray[i] = InitArray[min];
        InitArray[min] = tmp;
    }
}

void MergeSort(int ArraySort_Bub[ ],int ArraySort_She[ ], int ArraySort_Sel[ ], int parts)
{
    int Tmp1[100];
    int i = 0;

    while ((ArraySort_Bub[i] < size) && (ArraySort_She[i] < size))
        {
            if (ArraySort_Bub[i] < ArraySort_She[i])
                {
                    Tmp1[i] = ArraySort_Bub[i];
                    ArraySort_Bub[i]++;
                    cout << ArraySort_Bub << " ";
                }

            else
                {
                    Tmp1[i] = ArraySort_She[i];
                    ArraySort_She[i]++;
                    cout << ArraySort_She << " ";
                }

            Tmp1[i]++;
        }

    while (Tmp1[i] < 100)
        {
            Tmp1[i] = ArraySort_Bub[i];
            ArraySort_Bub[i]++;
            ArraySort_Sel[i]++;
        }

    while (ArraySort_She[i] < 100)
        {
            Tmp1[i] = ArraySort_She[i];
            ArraySort_She[i]++;
            ArraySort_Sel[i]++;
        }
}
 
0
 

So it looks like you're not actually doing a full merge sort, you're just merging together three arrays that are already sorted. Really the only tricky part of this is taking what you know about merging two arrays and extending it into three. Here's a two way merge:

int dst[size * 2], n = 0;

while (i < size && j < size) {
    if (a[i] <= b[j])
        dst[n++] = a[i++];
    else
        dst[n++] = b[j++];
}

while (i < size) dst[n++] = a[i++];
while (j < size) dst[n++] = b[j++];

I'll let you take a shot at doing the three way merge, but there are three steps:

  1. Find the smallest item from the three arrays until one of them is exhausted.
  2. Perform a two way merge on the remaining two arrays until one of them is exhausted.
  3. Exhaust the remaining array, if there are still items.

That means you're essentially taking a two way merge and adding a preliminary three way merge until there are two arrays left. So something like this:

while (i < size && j < size && k < size) {
    if (a[i] <= b[j] && a[i] <= c[k])
        dst[n++] = a[i++];
    else if (b[j] <= a[i] && b[j] < c[k])
        dst[n++] = b[j++];
    else
        dst[n++] = c[k++];
}

After that it's a simple matter to determine which array was exhausted and perform a two way merge on the remaining two arrays.

 
0
 

Got it working merging 2 lists ok.
3 lists almost works.. Sometimes it has random incorrect numbers in the sorted list (like -82341)?

Going to class - will check back later

Thanks,

/////////////////////////////////////////////////////////////////////////////////
//
//  *** TEST PLAN ***
//
// 1)  Generate 150 random numbers from between 0 - 1000 and display them
//
// 2)  Take the 1st 50 and display them, then BUBBLE SORT them and display again
//
// 3)  Take the 2nd 50 and display them, then SHELL SORT them and display again
//
// 4)  Take the 3rd 50 and display them, then SELECTION SORT them and display again
//
// 5)  Take the 3 sorted lists and MERGE SORT then together and display final list
//
/////////////////////////////////////////////////////////////////////////////////
#include <cmath>
#include <ctime>
#include <iomanip>
#include <cstdlib>
#include <iostream>
#include <windows.h>
using namespace std;


const int size = 150;               //total initial array size
const int parts = 50;               //the array divided into three parts
void BubbleSort(int InitArray[ ], int size);
void ShellSort(int InitArray[ ], int size);
void SelectionSort(int InitArray[ ], int size);
void MergeSort(int ArraySort_Bub[ ],int ArraySort_She[ ], int ArraySort_Sel[ ], int parts);


int main( )
{
    int InitArray[size], ArraySort_Bub[parts], ArraySort_She[parts], ArraySort_Sel[parts];

//////////////////////            Random Number Generator            //////////////////////
    srand ((unsigned) time(0)); 
    for (int i = 0; i < size; i++)
        {
            InitArray[i] = rand( ) %1000;
            //Sleep(1);
        }

//////////////////////            Initial Array            //////////////////////
    cout << endl << "\t   --->  THIS IS THE RANDOMLY GENERATED ARRAY OF 150 ELEMENTS  <---" << endl;
    cout << "\t   ----------------------------------------------------------------" << endl;

    for (int i = 0; i < 50; ++i)
        cout << InitArray[i] << " ";
    cout << endl << endl << "\n";

    for (int i = 50; i < 100; ++i)
        cout << InitArray[i] << " ";
    cout << endl << endl << "\n";

    for (int i = 100; i < 150; ++i)
        cout << InitArray[i] << " ";
    cout << endl << endl << "\n";

//////////////////////            Bubble Sort            //////////////////////
    BubbleSort(InitArray, 50);
    cout << endl << endl << "\t *  THIS IS THE BUBBLE SORT OF THE FIRST 50  *" << endl;
    cout << "\t ---------------------------------------------" << endl;
    for (int i = 0; i < 50; ++i)
    {
        cout << InitArray[i] << " ";
        ArraySort_Bub[i] = InitArray[i];            //put 1st 50 into ArraySort_Bub
    }
    cout << endl << endl << "\n";

//////////////////////            Shell Sort            ////////////////////// 
    ShellSort(InitArray + 50, 50);
    cout << endl << endl <<"\t **  THIS IS THE SHELL SORT OF THE SECOND 50  **" << endl;
    cout << "\t -----------------------------------------------" << endl;   
    for (int i = 50; i < 100; ++i)
    {
        cout << InitArray[i] << " ";
        ArraySort_She[i - 50] = InitArray[i];       //put 2nd 50 into ArraySort_She
    }
    cout << endl << endl << "\n";

//////////////////////            Selection Sort            ////////////////////// 
    cout << endl << endl << "\t ***  THIS IS THE SELECTION SORT OF THE THIRD 50  ***" << endl;
    cout << "\t --------------------------------------------------------" << endl;
    SelectionSort(InitArray + 100, 50);
    for (int i = 100; i < 150; ++i)
    {
        cout << InitArray[i] << " ";
        ArraySort_Sel[i - 100] = InitArray[i];      //put 3rd 50 into ArraySort_Sel
    }
    cout << endl;

//////////////////////            Merge Sort            ////////////////////// 
    cout << endl << endl << endl << endl << "\t ****  THIS IS THE MERGE SORT OF THE THREE PREVIOUSLY SORTED ARRAYS  ****" << endl;
    cout << "\t ------------------------------------------------------------------------" << endl;
    MergeSort(ArraySort_Bub, ArraySort_She, ArraySort_Sel, 50);

    cout << endl << endl << endl << endl << "\t";
    system ("pause");
    return 0;
}


//////////////////////            FREE FUNCTIONS            //////////////////////
void BubbleSort(int InitArray[ ], int size)
{
    int tmp;

    for (int i = 0; i < size - 1; i++)
        {
            for (int x = 0; x < size - 1; x++)
                {
                    if (InitArray[x] > InitArray[x + 1])
                        {
                            tmp = InitArray[x];
                            InitArray[x] = InitArray[x + 1];
                            InitArray[x + 1] = tmp;
                        }
                }
        }
}

void ShellSort(int InitArray[ ], int size)
{
    int h, i;
    int increments[100];

    for (h = 1, i = 0; h < size - 1; i++) 
    {
        increments[i] = h;
        h = 3 * h + 1;
    }

    for (i--; i >= 0; i--) 
    {
        h = increments[i];
        for (int hCnt = h; hCnt < 2 * h; hCnt++) 
        {
            for (int j = hCnt; j < size;) 
            {
                int tmp = InitArray[j];
                int k = j;

                while (k - h >= 0 && tmp < InitArray[k - h]) 
                {
                    InitArray[k] = InitArray[k - h];
                    k -= h;
                }

                InitArray[k] = tmp;
                j += h;
            }
        }
    }
}

void SelectionSort(int InitArray[ ], int size)
{
    for (int i = 0; i < size; i++) 
    {
        int min = i;

        for (int x = i; x < size; x++) 
        {
            if (InitArray[x] < InitArray[min])
                min = x;
        }

        int tmp = InitArray[i];
        InitArray[i] = InitArray[min];
        InitArray[min] = tmp;
    }
}


void MergeSort(int ArraySort_Bub[ ],int ArraySort_She[ ], int ArraySort_Sel[ ], int parts)
{
    int i = 0;
    int j = 0;
    int k = 0;
    int n = 0;
    int dst[size * 2];

    //////////////////////            2 array merge            //////////////////////
    //while (i < parts && j < parts) 
    //{
    //  if (ArraySort_Bub[i] <= ArraySort_She[j])
    //      dst[n++] = ArraySort_Bub[i++];

    //  else
    //      dst[n++] = ArraySort_She[j++];
 //   }

 //   while (i < size) dst[n++] = ArraySort_Bub[i++];
 //   while (j < size) dst[n++] = ArraySort_She[j++];

    //for (int i = 0; i < 100; i++)
    //  cout << dst[i] << " ";

    //cout << endl << endl << "\n";

    //////////////////////            3 array merge            //////////////////////
    while (i < parts && j < parts && k < parts) 
    {
        if (ArraySort_Bub[i] <= ArraySort_She[j] && ArraySort_Bub[i] <= ArraySort_Sel[k])
            dst[n++] = ArraySort_Bub[i++];

        else if (ArraySort_She[j] <= ArraySort_Bub[i]  && ArraySort_She[j] <= ArraySort_Sel[k])
            dst[n++] = ArraySort_She[j++];

        else
            dst[n++] = ArraySort_Sel[k++];
    }

    while (i < size) dst[n++] = ArraySort_Bub[i++];
    while (j < size) dst[n++] = ArraySort_She[j++];
    while (k < size) dst[n++] = ArraySort_Sel[k++];

    for (int i = 0; i < 150; ++i)
        cout << dst[i] << " ";

    cout << endl << endl << "\n";
}
 
0
 

I think I've got it - more to come once I clean it up and confirm...

 
0
 

Seems that I'm off on the merge sort by a smidge.... Oh so close!
Sometimes I run it and the output is perfect!
Other times I run it and one array fills in the last 2 - 3 items put they aren't in sorted order.

Here's the entire code one last time.

I'll try to attach the screen shots...

#include <cmath>
#include <ctime>
#include <iomanip>
#include <cstdlib>
#include <iostream>
using namespace std;


const int size = 150;               //total initial array size
const int parts = 50;               //the array divided into three parts
void BubbleSort(int InitArray[ ], int size);
void ShellSort(int InitArray[ ], int size);
void SelectionSort(int InitArray[ ], int size);
void MergeSort(int ArraySort_Bub[ ],int ArraySort_She[ ], int ArraySort_Sel[ ], int parts);


int main( )
{
    int InitArray[size], ArraySort_Bub[parts], ArraySort_She[parts], ArraySort_Sel[parts];

//////////////////////            Random Number Generator            //////////////////////
    srand ((unsigned) time(0)); 
    for (int i = 0; i < size; i++)
        {
            InitArray[i] = rand( ) %1000;
        }

//////////////////////            Initial Array            //////////////////////
    cout << endl << "\t   --->  THIS IS THE RANDOMLY GENERATED ARRAY OF 150 ELEMENTS  <---" << endl;
    cout << "\t   ----------------------------------------------------------------" << endl;

    for (int i = 0; i < 50; ++i)
        cout << InitArray[i] << " ";
    cout << endl << endl << "\n";

    for (int i = 50; i < 100; ++i)
        cout << InitArray[i] << " ";
    cout << endl << endl << "\n";

    for (int i = 100; i < 150; ++i)
        cout << InitArray[i] << " ";
    cout << endl << endl << "\n";

//////////////////////            Bubble Sort            //////////////////////
    BubbleSort(InitArray, parts);
    cout << endl << "\t *  THIS IS THE BUBBLE SORT OF THE FIRST 50  *" << endl;
    cout << "\t ---------------------------------------------" << endl;
    for (int i = 0; i < 50; ++i)
    {
        cout << InitArray[i] << " ";
        ArraySort_Bub[i] = InitArray[i];            //put 1st 50 into ArraySort_Bub
    }
    cout << endl << endl << "\n";

//////////////////////            Shell Sort            ////////////////////// 
    ShellSort(InitArray + 50, parts);
    cout <<"\t **  THIS IS THE SHELL SORT OF THE SECOND 50  **" << endl;
    cout << "\t -----------------------------------------------" << endl;   
    for (int i = 50; i < 100; ++i)
    {
        cout << InitArray[i] << " ";
        ArraySort_She[i - 50] = InitArray[i];       //put 2nd 50 into ArraySort_She
    }
    cout << endl << endl << "\n";

//////////////////////            Selection Sort            ////////////////////// 
    cout << "\t ***  THIS IS THE SELECTION SORT OF THE THIRD 50  ***" << endl;
    cout << "\t ----------------------------------------------------" << endl;
    SelectionSort(InitArray + 100, parts);
    for (int i = 100; i < 150; ++i)
    {
        cout << InitArray[i] << " ";
        ArraySort_Sel[i - 100] = InitArray[i];      //put 3rd 50 into ArraySort_Sel
    }
    cout << endl << endl << "\n";

//////////////////////            Merge Sort            ////////////////////// 
    cout << endl << "\t ****  THIS IS THE MERGE SORT OF THE THREE PREVIOUSLY SORTED ARRAYS  ****" << endl;
    cout << "\t ------------------------------------------------------------------------" << endl;
    MergeSort(ArraySort_Bub, ArraySort_She, ArraySort_Sel, parts);

    cout << endl << endl << endl << endl << "\t";
    system ("pause");
    return 0;
}

//////////////////////            FREE FUNCTIONS            //////////////////////
void BubbleSort(int InitArray[ ], int size)
{
    int tmp;

    for (int i = 0; i < size - 1; i++)
        {
            for (int x = 0; x < size - 1; x++)
                {
                    if (InitArray[x] > InitArray[x + 1])
                        {
                            tmp = InitArray[x];
                            InitArray[x] = InitArray[x + 1];
                            InitArray[x + 1] = tmp;
                        }
                }
        }
}

void ShellSort(int InitArray[ ], int size)
{
    int h, i;
    int increments[100];

    for (h = 1, i = 0; h < size - 1; i++) 
    {
        increments[i] = h;
        h = 3 * h + 1;
    }

    for (i--; i >= 0; i--) 
    {
        h = increments[i];
        for (int hCnt = h; hCnt < 2 * h; hCnt++) 
        {
            for (int j = hCnt; j < size;) 
            {
                int tmp = InitArray[j];
                int k = j;

                while (k - h >= 0 && tmp < InitArray[k - h]) 
                {
                    InitArray[k] = InitArray[k - h];
                    k -= h;
                }

                InitArray[k] = tmp;
                j += h;
            }
        }
    }
}

void SelectionSort(int InitArray[ ], int size)
{
    for (int i = 0; i < size; i++) 
    {
        int min = i;

        for (int x = i; x < size; x++) 
        {
            if (InitArray[x] < InitArray[min])
                min = x;
        }

        int tmp = InitArray[i];
        InitArray[i] = InitArray[min];
        InitArray[min] = tmp;
    }
}


void MergeSort(int ArraySort_Bub[ ],int ArraySort_She[ ], int ArraySort_Sel[ ], int parts)
{
    int i = 0;
    int j = 0;
    int k = 0;
    int n = 0;
    int dst[size];

//////////////////////            3 array merge            //////////////////////
    while (i < parts && j < parts && k < parts) 
    {
        if (ArraySort_Bub[i] <= ArraySort_She[j] && ArraySort_Bub[i] <= ArraySort_Sel[k])
            dst[n++] = ArraySort_Bub[i++];

        else if (ArraySort_She[j] <= ArraySort_Bub[i] && ArraySort_She[j] <= ArraySort_Sel[k])
            dst[n++] = ArraySort_She[j++];

        else
            dst[n++] = ArraySort_Sel[k++];
    }

    while (i < parts) dst[n++] = ArraySort_Bub[i++];
    while (j < parts) dst[n++] = ArraySort_She[j++];
    while (k < parts) dst[n++] = ArraySort_Sel[k++];

    for (int i = 0; i < size; ++i)
        cout << dst[i] << " ";
}
 
0
 

updated screen shots

Attachments Picture1.png 46.71KB Picture2.png 136.28KB
 
0
 

Rewrote the Merge and it works now!

Thanks for the help deceptikon!

Question Answered as of 1 Year Ago by phorce and deceptikon
You
This question has already been solved: Start a new discussion instead
Post:
Start New Discussion
Tags Related to this Article