Abstract Data Type Vector Sorting Functions
sort.h
#include iostream
#include "d_vector.h"
template < typename T >
void insertionSort(miniVector< T >& v, int n)//ascending order
{
int j;
T target;
for (int i = 1; i < n; i++)
{
target = v[i];
j = i-1;
while (j >= 0 && v[j]>target)
{
v[j+1] = v[j];
j--;
}
v[j+1] = target;
}
}
template < typename T >
void DinsertionSort(miniVector< T >& v, int n)//descending order
{
int j;
T target;
for (int i = 1; i < n; i++)
{
target = v[i];
j = i-1;
while (j >= 0 && v[j]
void bubbleSort(miniVector< T >& v, int n)//ascending order
{
T target;
for (int pass=1; pass < n; pass++)
{
for (int i=0; i < n-pass; i++)
{
if (v[i] > v[i+1])
{
// exchange elements
int temp = v[i]; v[i] = v[i+1]; v[i+1] = temp;
}
}
}
}
template < typename T >
void DbubbleSort(miniVector< T >& v, int n)//descending order
{
T target;
for (int pass=1; pass < n; pass++)
{
for (int i=0; i < n-pass; i++)
{
if (v[i] < v[i+1])
{
// exchange elements
int temp = v[i]; v[i] = v[i+1]; v[i+1] = temp;
}
}
}
}
template < typename T >
void selectionSort(miniVector< T >& v, int n)//ascending order
{
T target;
for (int pass=0; pass < n-1; pass++)
{
int potentialSmallest = pass; // assume this is smallest
//--- Look over remaining elements to find smallest.
for (int i = pass+1; i < n; i++)
{
if (v[i] < v[potentialSmallest])
{
// Remember index for latter swap.
potentialSmallest = i;
}
}
// Swap smallest remaining element
int temp = v[pass];
v[pass] = v[potentialSmallest];
v[potentialSmallest] = temp;
}
}
template < typename T >
void DselectionSort(miniVector< T >& v, int n)//descending order
{
T target;
for (int pass=0; pass < n-1; pass++)
{
int potentialLargest = pass; // assume this is largest
//--- Look over remaining elements to find largest.
for (int i = pass+1; i < n; i++)
{
if (v[i] > v[potentialLargest])
{
//--- Remember index for latter swap.
potentialLargest = i;
}
}
//--- Swap smallest remaining element
int temp = v[pass];
v[pass] = v[potentialLargest];
v[potentialLargest] = temp;
}
}
template < typename T >
void shellSort(miniVector< T >& v, int n) //shell sort accending
{
int temp;
int pass = n / 2;
while (pass > 0)
{
for (int i = pass; i < n; i++)
{
int j = i;
temp = v[i];
while ((j >= pass) && (v[j-pass] > temp))//more than temp value
{
v[j] = v[j - pass];
j = j - pass;
}
v[j] = temp;
}
if (pass == 2)
pass = 1;
else
pass = (int) (pass / 2.2);
}
}
template < typename T >
void DshellSort(miniVector< T >& v, int n) //shell sort descending
{
int temp;
int pass = n / 2;
while (pass > 0)
{
for (int i = pass; i < n; i++)
{
int j = i;
temp = v[i];
while ((j >= pass) && (v[j-pass] < temp))//less than temp value
{
v[j] = v[j - pass];
j = j - pass;
}
v[j] = temp;//swap values
}
if (pass == 2)
pass = 1;
else
pass = (int) (pass / 2.2);
}
}
template < typename T >
void exchangeSort(miniVector< T >& v, int n) //shell sort accending
{
int temp;
for (int i=0; i< (n-1); i++)
{
for(int j = (i+1); j < n; j++)
{
if (v[i] > v[j])
{
temp= v[i]; // swap values
v[i] = v[j];
v[j] = temp;
}
}
}
}
template < typename T >
void DexchangeSort(miniVector< T >& v, int n) //shell sort accending
{
int temp;
for (int i=0; i< (n-1); i++)
{
for(int j = (i+1); j < n; j++)
{
if (v[i] < v[j])
{
temp= v[i]; // swap values
v[i] = v[j];
v[j] = temp;
}
}
}
}
main.cpp
#include iostream
#include cstdlib
#include ctime
#include "d_vector.h"
#include "sort.h"
#include "timer.h"
using namespace std;
int main()
{
srand((unsigned)time(0));//for better random number creation
miniVector < int> ascend, ascend2, ascend3, ascend4, ascend5,
descend, descend2, descend3, descend4, descend5, random;
timer time;
for(int i = 0; i < 10000; i++)//assign values to each vector
{
int value1 = (rand()%10000)+1;
ascend.push_back(value1);
int value2 = (rand()%10000)+1;
descend.push_back(value2);
int value3 = (rand()%999999)+1;
random.push_back(value3);
}
ascend2 = ascend;
ascend3 = ascend;
ascend4 = ascend;
ascend5 = ascend;
descend2 = descend;
descend3 = descend;
descend4 = descend;
descend5 = descend;
time.start();
insertionSort(ascend, 10000);
time.stop();
cout << "It took " << time.time()
<< " seconds for an Insertion Sort to sort in ascending order\n" << endl;
time.start();
bubbleSort(ascend2, 10000);
time.stop();
cout << "It took " << time.time()
<<" seconds for a Bubble Sort to sort in ascending order\n" << endl;
time.start();
selectionSort(ascend3, 10000);
time.stop();
cout << "It took " << time.time()
<<" seconds for a Selection Sort to sort in ascending order\n" << endl;
time.start();
shellSort(ascend4, 10000);
time.stop();
cout << "It took " << time.time()
<<" seconds for a Shell Sort to sort in ascending order\n" << endl;
time.start();
exchangeSort(ascend5, 10000);
time.stop();
cout << "It took " << time.time()
<<" seconds for an Exchange Sort to sort in ascending order\n" << endl;
time.start();
DinsertionSort(descend, 10000);
time.stop();
cout << "It took " << time.time()
<< " seconds for an Insertion Sort to sort in descending order\n" << endl;
time.start();
DbubbleSort(descend2, 10000);
time.stop();
cout << "It took " << time.time()
<< " seconds for a Bubble Sort to sort in descending order\n" << endl;
time.start();
DselectionSort(descend3, 10000);
time.stop();
cout << "It took " << time.time()
<< " seconds for a Selection Sort to sort in descending order\n" << endl;
time.start();
DshellSort(descend4, 10000);
time.stop();
cout << "It took " << time.time()
<< " seconds for a Shell Sort to sort in descending order\n" << endl;
time.start();
DexchangeSort(descend5, 10000);
time.stop();
cout << "It took " << time.time()
<< " seconds for an Exchange Sort to sort in descending order\n" << endl;
return 0;