Help with Sorting algorithms
i need to combine insertion, bubble, quick, merge, and shell sort into one program in a menu style so i can compare them, and so that i can choose which algorithm to use. i have the menu set up but i need help with adding the algorithms into the menu. they all are supposed to sort the same list (50 numbers) and say how many steps they took.
insert
Code:
#include <iostream>
#include <time.h>
#include <cstdlib>
using namespace std;
const int INSERTION =1, BUBBLE = 2, QUICK = 3, MERGE = 4, SHELL = 5, QUIT = 6;
void menu(int &option);
int main()
{
int choice;
menu(choice);
while(choice != QUIT)
{
if (choice == INSERTION)
{
}// close INSERTION if
if (choice == BUBBLE)
{
}// close BUBBLE if
if (choice == QUICK)
{
}// close QUICK if
if (choice == MERGE)
{
}// close MERGE if
if (choice == SHELL)
{
}// close SHELL if
}//close while
} //close int
void InsertionSort( apvector <int> &num)
{
int i, j, key, numLength = num.length( );
for(j = 1; j < numLength; j++) // Start with 1 (not 0)
{
key = num[j];
for(i = j - 1; (i >= 0) && (num[i] < key); i--) // Smaller values move up
{
num[i+1] = num[i];
}
num[i+1] = key; //Put key into its proper location
}
return;
}
void BubbleSort(apvector <int> &num)
{
int i, j, flag = 1; // set flag to 1 to start first pass
int temp; // holding variable
int numLength = num.length( );
for(i = 1; (i <= numLength) && flag; i++)
{
flag = 0;
for (j=0; j < (numLength -1); j++)
{
if (num[j+1] > num[j]) // ascending order simply changes to <
{
temp = num[j]; // swap elements
num[j] = num[j+1];
num[j+1] = temp;
flag = 1; // indicates that a swap occurred.
}
}
}
return; //arrays are passed to functions by address; nothing is returned
}
void QuickSort(apvector <int> &num, int top, int bottom)
{
// top = subscript of beginning of array
// bottom = subscript of end of array
int middle;
if (top < bottom)
{
middle = partition(num, top, bottom);
quicksort(num, top, middle); // sort first section
quicksort(num, middle+1, bottom); // sort second section
}
return;
}
//Function to determine the partitions
// partitions the array and returns the middle subscript
int partition(apvector <int> &array, int top, int bottom)
{
int x = array[top];
int i = top - 1;
int j = bottom + 1;
int temp;
do
{
do
{
j - -;
}while (x >array[j]);
do
{
i++;
} while (x <array[i]);
if (i < j)
{
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}while (i < j);
return j; // returns middle subscript
}
void MergeSort(apvector <int> &arrayA, apvector <int> &arrayB, apvector <int> &arrayC)
{
int indexA = 0; // initialize variables for the subscripts
int indexB = 0;
int indexC = 0;
while((indexA < arrayA.length( )) && (indexB < arrayB.length( ))
{
if (arrayA[indexA] < arrayB[indexB])
{
arrayC[indexC] = arrayA[indexA];
indexA++; //increase the subscript
}
else
{
arrayC[indexC] = arrayB[indexB];
indexB++; //increase the subscript
}
indexC++; //move to the next position in the new array
}
// Move remaining elements to end of new array when one merging array is empty
while (indexA < arrayA.length( ))
{
arrayC[indexC] = arrayA[indexA];
indexA++;
indexC++;
}
while (indexB < arrayB.length( ))
{
arrayC[indexC] = arrayB[indexB];
indexB++;
indexC++;
}
return;
}
void ShellSort( apvector <int> &num)
{
int i, temp, flag = 1, numLength = num.length( );
int d = numLength;
while( flag || (d > 1)) // boolean flag (true when not equal to 0)
{
flag = 0; // reset flag to 0 to check for future swaps
d = (d+1) / 2;
for (i = 0; i < (numLength - d); i++)
{
if (num[i + d] > num[i])
{
temp = num[i + d]; // swap positions i+d and i
num[i + d] = num[i];
num[i] = temp;
flag = 1; // tells swap has occurred
}
}
}
return;
}
void menu(int &option)
{
cout << "1 INSERTION" << endl;
cout << "2 BUBBLE" << endl;
cout << "3 QUICK" << endl;
cout << "4 MERGE" << endl;
cout << "5 SHELL" << endl;
cout << "Choose your algorithm" << endl;
cin >> option;
}
