This code uses a variety of sorting methods. This code compiles with Borland C++ 5.0 it's useful for seeing how to duplicate the algorithms in other languages. Each sort is found in a separate function called in the main function. This version uses a vector and can sort up to 5 million numbers(possibly more). I suggest larger vectors use the quicksort, unless you want to wait a few days. I find the code fairly concise it makes random numbers depending on the amount you specify for sorting and then outputs the time in seconds to sort the number vector.
It uses an option menu and makes use of
-Bubble Sort
-Selection Sort
-Insertion Sort
-Shell Sort
-Quick Sort
using namespace std;
// VIEW RESULTS
void view_sort(vector <int> arr, long max)
{
for(long x=0;x<max;x++)
{
cout<<arr[x]<<"\t";
}
}
// BUBBLE SORT
vector <int> bubble(vector <int> arr, long max){
int tmp;
for(long i=0;i<max;i++)
{
for(long x=0; x<max-1-i; x++)
{
if(arr[x] > arr[x+1])
{
//r.push_back(rnd);
tmp = arr[x];
arr[x] = arr[x+1];
arr[x+1] = tmp;
}
}
}
return arr;
}
// SELECTION SORT
vector <int> select(vector <int> arr, long max){
int tmp;
int min;
for(long i=0;i<max;i++)
{
min = i;
for(long x=i; x<max; x++)
{
if(arr[x] < arr[min])
{
min = x;
}
}
tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
return arr;
}
// INSERTION SORT
vector <int> insert(vector <int> arr, long max)
{
int i, j, index;
for(i=1; i < max;i++)
{
index = arr[i];
j = i;
while((j > 0) && (arr[j-1] > index))
{
arr[j] = arr[j-1];
j = j-1;
}
arr[j] = index;
}
return arr;
}
// SHELL SORT
vector <int> shell(vector <int> arr, long max){
int index, i, j;
for(i=1; i < max;i++)
{
index = arr[i];
j = i;
while((j > 0) && (arr[j-1] > index))
{
arr[j] = arr[j-1];
j = j-1;
}
arr[j] = index;
}
return arr;
}
/* ######## QUICK SORT ######### */
void quicksort(vector <int> & arr, int start, int end){
int pivot, starth, endh; // store pivot # keep start & end in memory for split
starth = start;
endh = end;
pivot = arr[start];
while(start < end)
{
while((arr[end] >= pivot) && (start < end))
end--;
if (start != end)
{
arr[start] = arr[end];
start++;
}
while ((arr[start] <= pivot) && (start < end))
start++;
if (start != end)
{
arr[end] = arr[start];
end--;
}
}
arr[start] = pivot;
pivot = start;
start = starth;
end = endh;
if(start < pivot)
quicksort(arr, start, pivot-1);
if(end > pivot)
quicksort(arr, pivot+1, end);
}
/* BEGIN MAIN */
int main(){
time_t start;
long rnd = rand()%1000+1;
vector <int> r;
//long r[200001];
long tmp;
long maxnum; // if you overload this variable, beware!
int option;
bool stop = false;
bool view = false;
while(!stop){
cout<<"\t\t\tAlgorithms For Sorting Numbers\n"<<endl;
cout<<"Choose Method:\n[1] Bubble\n[2] Selection\n[3] Insertion\n[4] Shell Sort\n[5] Quick Sort";
cin>>option;
// ARRANGE ARRAY
cout<<"Length (<=5000000 )\n";
cin>>maxnum;
if(maxnum == 1)
maxnum = 1000000;
for(long x=0;x<maxnum;x++)
{
long rnd = rand()%1000+1;
//cout<<rnd<<"\t";
r.push_back(rnd);
}
// END ARRANGE ARRAY
start = time(NULL);
if(option == 1)
r = bubble(r,maxnum);
if(option == 2)
r = select(r,maxnum);
if(option == 3)
r = insert(r,maxnum);
if(option == 4)
r = shell(r,maxnum);
if(option==5)
quicksort(r,0,maxnum-1);
time_t stopclock;
stopclock = time(NULL);
// print time result
cout<<endl<<double(stopclock)-start<<"[seconds]";
// view sort results?
cout<<"\nView the sorted numbers? [1=yes||0=no]";
int v;
cin>>v;
if(v == 1)
{
view = true;
view_sort(r,maxnum);
}
// end program?
cout<<endl<<"Press 0 to quit any key to continue";
int s;
cin>>s;
if(s == 0)
stop = true; clrscr();
}
}
