PROWAREtech
C++: Sort Algorithm Study
A study of several sorting algorithms.
QuickSort, using "Big O" notation, is O(n•log2(n)), which is about as fast as a sort algorithm can sort an entire array of random data. RadixSort is the same while BubbleSort is O(n ) on most data but in the right circumstance is linear, or O(n). SelectionSort is O(n²) and slow no matter the data. In this study, BubbleSort (optimized) was modified to attack the array on both ends so if having only a few items out of sort then it sorts them in about linear time, or O(n). InsertionSort is the fastest of the O(n²) algorithms and is used here with QuickSort to increase performance by 20% when compared to QuickSort alone. BubbleSort (reversed) was modified to start at the end of the array and sort the last item in the array. This is more practical than starting from the front of the array as new items are typically added to the end of an array. The array based data structure/algorithm on this site uses a combination of QuickSort and InsertionSort to perform the initial sort of an entirely unsorted array, and then BubbleSort (reversed) to maintain the array after each time an item is added to the end of the array.
Use an online graphing calculator like on desmos to graph:
y = x•log2(x)
y = x
y = x²
y = x3
#include <iostream>
#include <iomanip>
#include <string>
#include <ctime>
#include <sstream>
using namespace std;
class CRandomMersenne { // encapsulate random number generator
#if 0
// define constants for MT11213A:
// (32 bit constants cannot be defined as enum in 16-bit compilers)
#define MERS_N 351
#define MERS_M 175
#define MERS_R 19
#define MERS_U 11
#define MERS_S 7
#define MERS_T 15
#define MERS_L 17
#define MERS_A 0xE4BD75F5
#define MERS_B 0x655E5280
#define MERS_C 0xFFD58000
#else
// or constants for MT19937:
#define MERS_N 624
#define MERS_M 397
#define MERS_R 31
#define MERS_U 11
#define MERS_S 7
#define MERS_T 15
#define MERS_L 18
#define MERS_A 0x9908B0DF
#define MERS_B 0x9D2C5680
#define MERS_C 0xEFC60000
#endif
public:
CRandomMersenne(unsigned long seed) { // constructor
RandomInit(seed);
}
void RandomInit(unsigned long seed); // re-seed
void RandomInitByArray(unsigned long seeds[], int length); // seed by more than 32 bits
int IRandom(int min, int max); // output random integer
double Random(); // output random float
unsigned long BRandom(); // output random bits
private:
unsigned long mt[MERS_N]; // state vector
int mti; // index into mt
enum TArch { LITTLEENDIAN, BIGENDIAN, NONIEEE };
TArch Architecture; // conversion to float depends on computer architecture
};
void CRandomMersenne::RandomInit(unsigned long seed) {
// re-seed generator
mt[0] = seed;
for (mti = 1; mti < MERS_N; mti++) {
mt[mti] = (1812433253UL * (mt[mti - 1] ^ (mt[mti - 1] >> 30)) + mti);
}
// detect computer architecture
union { double f; unsigned long i[2]; } convert;
convert.f = 1.0;
// Note: Old versions of the Gnu g++ compiler may make an error here,
// compile with the option -fenum-int-equiv to fix the problem
if (convert.i[1] == 0x3FF00000)
Architecture = LITTLEENDIAN;
else if (convert.i[0] == 0x3FF00000)
Architecture = BIGENDIAN;
else
Architecture = NONIEEE;
}
void CRandomMersenne::RandomInitByArray(unsigned long seeds[], int length) {
// seed by more than 32 bits
int i, j, k;
RandomInit(19650218UL);
if (length <= 0) return;
i = 1; j = 0;
k = (MERS_N > length ? MERS_N : length);
for (; k; k--) {
mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1664525UL)) + seeds[j] + j;
i++; j++;
if (i >= MERS_N) { mt[0] = mt[MERS_N - 1]; i = 1; }
if (j >= length) j = 0;
}
for (k = MERS_N - 1; k; k--) {
mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1566083941UL)) - i;
if (++i >= MERS_N) { mt[0] = mt[MERS_N - 1]; i = 1; }
}
mt[0] = 0x80000000UL; // MSB is 1; assuring non-zero initial array
}
unsigned long CRandomMersenne::BRandom() {
// generate 32 random bits
unsigned long y;
if (mti >= MERS_N) {
// generate MERS_N words at one time
const unsigned long LOWER_MASK = (1LU << MERS_R) - 1; // lower MERS_R bits
const unsigned long UPPER_MASK = -1L << MERS_R; // upper (32 - MERS_R) bits
static const unsigned long mag01[2] = { 0, MERS_A };
int kk;
for (kk = 0; kk < MERS_N - MERS_M; kk++) {
y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
mt[kk] = mt[kk + MERS_M] ^ (y >> 1) ^ mag01[y & 1];
}
for (; kk < MERS_N - 1; kk++) {
y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK);
mt[kk] = mt[kk + (MERS_M - MERS_N)] ^ (y >> 1) ^ mag01[y & 1];
}
y = (mt[MERS_N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK);
mt[MERS_N - 1] = mt[MERS_M - 1] ^ (y >> 1) ^ mag01[y & 1];
mti = 0;
}
y = mt[mti++];
// Tempering (May be omitted):
y ^= y >> MERS_U;
y ^= (y << MERS_S) & MERS_B;
y ^= (y << MERS_T) & MERS_C;
y ^= y >> MERS_L;
return y;
}
double CRandomMersenne::Random() {
// output random float number in the interval 0 <= x < 1
union { double f; unsigned long i[2]; } convert;
unsigned long r = BRandom(); // get 32 random bits
switch (Architecture) {
case LITTLEENDIAN:
convert.i[0] = r << 20;
convert.i[1] = (r >> 12) | 0x3FF00000;
return convert.f - 1.0;
case BIGENDIAN:
convert.i[1] = r << 20;
convert.i[0] = (r >> 12) | 0x3FF00000;
return convert.f - 1.0;
case NONIEEE:
default:
;
}
// This somewhat slower method works for all architectures, including
// non-IEEE floating point representation:
return (double)r * (1. / ((double)(unsigned long)(-1L) + 1.));
}
int CRandomMersenne::IRandom(int min, int max) {
// output random integer in the interval min <= x <= max
int r;
r = int((max - min + 1) * Random()) + min; // multiply interval with random and truncate
if (r > max) r = max;
if (max < min) return 0x80000000;
return r;
}
class SortArray
{
private:
int *pArrayNum;
unsigned int array_size;
void delete_arrays();
public:
SortArray() { pArrayNum = 0; }
~SortArray() { delete_arrays(); }
void allocate(const unsigned int array_size);
void randomize_array();
int *get_ptr_array() const { return pArrayNum; }
unsigned int get_array_size() const { return array_size; }
void make_array_sorted();
int quick_sort(); // return the number of milliseconds the sort took
int quick_insertion_sort(); // return the number of milliseconds the sort took
int quick_selection_sort(); // return the number of milliseconds the sort took
int radix_sort(); // return the number of milliseconds the sort took
int bubble_sort(); // return the number of milliseconds the sort took
int bubble_sort_reversed(); // return the number of milliseconds the sort took
int bubble_sort_optimized(); // return the number of milliseconds the sort took
int selection_sort(); // return the number of milliseconds the sort took
int insertion_sort(); // return the number of milliseconds the sort took
};
void SortArray::delete_arrays() {
if (pArrayNum) {
delete[]pArrayNum;
pArrayNum = 0;
}
array_size = 0;
}
enum errors_t { ERROR_OUT_OF_MEMORY }; // used for throwing exceptions
void SortArray::allocate(const unsigned int array_size) {
if (!pArrayNum || this->array_size < array_size) {
delete_arrays();
pArrayNum = new int[array_size]; // THIS WILL RETURN AN ADDRESS FOR ZERO SIZE ARRAYS
if (!pArrayNum)
throw ERROR_OUT_OF_MEMORY;
}
this->array_size = array_size;
}
void SortArray::make_array_sorted()
{
for (unsigned int index = 0; index < array_size; index++)
pArrayNum[index] = index;
}
void SortArray::randomize_array()
{
static CRandomMersenne mersenne(static_cast<unsigned long>(time(0)));
for (unsigned int index = 0; index < array_size; pArrayNum[index++] = mersenne.IRandom(0, array_size));
}
void qsort_int_optimized(int array[], const unsigned int siz) {
if (siz < 2)
return;
int pivot = array[siz / 2];
int *left = array;
int *right = array + siz - 1;
while (1) {
while ((left <= right) && (*left < pivot)) left++;
while ((left <= right) && (*right > pivot)) right--;
if (left > right) break;
int temp = *left;
*left++ = *right;
*right-- = temp;
}
qsort_int_optimized(array, right - array + 1);
qsort_int_optimized(left, array + siz - left);
}
void insertion_sort(int array[], const unsigned int siz) {
for (unsigned int i = 1; i < siz; ++i) {
int tmp = array[i];
unsigned int j = i;
while (j > 0 && tmp < array[j - 1]) {
array[j] = array[j - 1];
j--;
}
array[j] = tmp;
}
}
void qsort_insertion_int(int array[], const unsigned int siz) {
if (siz >= 2)
{
if (siz <= 30)
insertion_sort(array, siz);
else
{
int pivot = array[siz / 2];
int *left = array;
int *right = array + siz - 1;
while (1) {
while ((left <= right) && (*left < pivot)) left++;
while ((left <= right) && (*right > pivot)) right--;
if (left > right) break;
int temp = *left;
*left++ = *right;
*right-- = temp;
}
qsort_insertion_int(array, right - array + 1);
qsort_insertion_int(left, array + siz - left);
}
}
}
void selection_sort(int array[], const int size) {
int indexMin = 0, valueMin = 0;
const int bottom = (size - 1);
for (int top = 0; top < bottom; top++) {
indexMin = top;
valueMin = array[top];
for (int seekMin = top + 1; seekMin < size; seekMin++)
if (array[seekMin] < valueMin) {
valueMin = array[seekMin];
indexMin = seekMin;
}
array[indexMin] = array[top];
array[top] = valueMin;
}
}
void qsort_selection_int(int array[], const unsigned int siz) {
if (siz >= 2)
{
if (siz <= 30)
selection_sort(array, siz);
else
{
int pivot = array[siz / 2];
int *left = array;
int *right = array + siz - 1;
while (1) {
while ((left <= right) && (*left < pivot)) left++;
while ((left <= right) && (*right > pivot)) right--;
if (left > right) break;
int temp = *left;
*left++ = *right;
*right-- = temp;
}
qsort_selection_int(array, right - array + 1);
qsort_selection_int(left, array + siz - left);
}
}
}
void bubble_sort(int array[], const int size) {
int keepswapping; int temp;
do {
keepswapping = false;
for (int count = 0; count < (size - 1); count++)
if (array[count] > array[count + 1]) {
temp = array[count];
array[count] = array[count + 1];
array[count + 1] = temp;
keepswapping = true;
}
} while (keepswapping);
}
void bubble_sort_reversed(int array[], const int size) {
int keepswapping; int count, temp;
do {
keepswapping = false;
for (count = size - 1; count > 0; count--)
if (array[count] < array[count - 1]) {
temp = array[count];
array[count] = array[count - 1];
array[count - 1] = temp;
keepswapping = true;
}
} while (keepswapping);
}
void bubble_sort_optimized(int array[], const int size) {
int keepswapping; int count, temp; const int end = size - 1;
do {
for (count = end; count > 0; count--)
if (array[count] < array[count - 1]) {
temp = array[count];
array[count] = array[count - 1];
array[count - 1] = temp;
}
keepswapping = false;
for (count = 0; count < end; count++)
if (array[count] > array[count + 1]) {
temp = array[count];
array[count] = array[count + 1];
array[count + 1] = temp;
keepswapping = true;
}
} while (keepswapping);
}
class CRadixSort
{
private:
CRadixSort() { ; }
static void rad_sort_u(unsigned int *from, unsigned int *to, unsigned int bit)
{
if (!bit || to < from + 1) return;
unsigned int *ll = from, *rr = to - 1, tmp;
while (1) {
while (ll < rr && !(*ll & bit)) ll++;
while (ll < rr && (*rr & bit)) rr--;
if (ll >= rr) break;
tmp = *ll;
*ll = *rr;
*rr = tmp;
}
if (!(bit & *ll) && ll < to) ll++;
bit >>= 1;
rad_sort_u(from, ll, bit);
rad_sort_u(ll, to, bit);
}
public:
static void radix_sort(int *array, const unsigned int len)
{
unsigned int i, *x = (unsigned int*)array;
for (i = 0; i < len; i++)
x[i] ^= -2147483648;
rad_sort_u(x, x + len, -2147483648);
for (i = 0; i < len; i++)
x[i] ^= -2147483648;
}
static void radix_sort_unsigned(unsigned int *array, const unsigned int len)
{
rad_sort_u(array, array + len, (unsigned int)-2147483648);
}
};
int SortArray::radix_sort() // return the number of milliseconds the sort took
{
int milliseconds = clock();
CRadixSort::radix_sort(pArrayNum, array_size);
return (clock() - milliseconds);
}
int SortArray::quick_sort() // return the number of milliseconds the sort took
{
int milliseconds = clock();
::qsort_int_optimized(pArrayNum, array_size);
return (clock() - milliseconds);
}
int SortArray::quick_insertion_sort() // return the number of milliseconds the sort took
{
int milliseconds = clock();
::qsort_insertion_int(pArrayNum, array_size);
return (clock() - milliseconds);
}
int SortArray::quick_selection_sort() // return the number of milliseconds the sort took
{
int milliseconds = clock();
::qsort_selection_int(pArrayNum, array_size);
return (clock() - milliseconds);
}
int SortArray::bubble_sort() // return the number of milliseconds the sort took
{
int milliseconds = clock();
::bubble_sort(pArrayNum, array_size);
return (clock() - milliseconds);
}
int SortArray::bubble_sort_reversed() // return the number of milliseconds the sort took
{
int milliseconds = clock();
::bubble_sort_reversed(pArrayNum, array_size);
return (clock() - milliseconds);
}
int SortArray::bubble_sort_optimized() // return the number of milliseconds the sort took
{
int milliseconds = clock();
::bubble_sort_optimized(pArrayNum, array_size);
return (clock() - milliseconds);
}
int SortArray::selection_sort() // return the number of milliseconds the sort took
{
int milliseconds = clock();
::selection_sort(pArrayNum, array_size);
return (clock() - milliseconds);
}
int SortArray::insertion_sort() // return the number of milliseconds the sort took
{
int milliseconds = clock();
::insertion_sort(pArrayNum, array_size);
return (clock() - milliseconds);
}
void showArray(int * const array, int size) {
for (int count = 0; count < 5; count++)
cout << array[count] << ' ';
cout << ". . . ";
for (int count = size - 5; count < size; count++)
cout << array[count] << ' ';
cout << endl;
}
void swap_first_last_elements(SortArray &sort_array)
{
int temp = sort_array.get_ptr_array()[0];
sort_array.get_ptr_array()[0] = sort_array.get_ptr_array()[sort_array.get_array_size() - 1];
sort_array.get_ptr_array()[sort_array.get_array_size() - 1] = temp;
}
int main() {
const char *COLUMNHEADERS100K = "\r\n----------------------------------------------------------\r\n";
const char *COLUMNHEADERS20M = "\r\n------------------------------------------------------------\r\n";
const int ARRAYSIZES100K[] = { 3125,6250,12500,25000,50000,100000,0 };
const int ARRAYSIZES20M[] = { 1250000,2500000,5000000,10000000,20000000,0 };
SortArray sort_array;
int outerloop = 1, innerloop, i;
while (outerloop)
{
cout << "Q. to quit\r\n1. Use 20,000,000 element array\r\n2. Use 100,000 element array\r\n>";
string choice;
getline(cin, choice);
switch (choice[0])
{
case '1':
sort_array.allocate(20000000);//pre allocate the array
innerloop = 1;
while (innerloop)
{
cout << "\r\n---=== USING " << sort_array.get_array_size() << " ELEMENT ARRAY ===---\r\n";
cout << "Q. to quit.\r\n";
cout << "1. Swap first/last elements & compare QUICK, RADIX, INSERTION and BUBBLE SORT.\r\n";
cout << "2. Assign last value to first element of sorted array and run BUBBLE SORT.\r\n";
cout << "3. Assign first value to last element of sorted array, run BUBBLE SORT REVERSED\r\n";
cout << "4. Compare QUICK, RADIX, INSERTION and BUBBLE SORT.\r\n>";
getline(cin, choice);
switch (choice[0])
{
case '1':
cout << setw(15) << " ";
for (i = 0; ARRAYSIZES20M[i]; cout << setw(9) << ARRAYSIZES20M[i++]);
cout << COLUMNHEADERS20M;
cout << setw(15) << "insertion";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(9) << sort_array.insertion_sort();
}
cout << endl;
cout << setw(15) << "radix";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(9) << sort_array.radix_sort();
}
cout << endl;
cout << setw(15) << "quick";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(9) << sort_array.quick_sort();
}
cout << endl;
cout << setw(15) << "quick w/insert";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(9) << sort_array.quick_insertion_sort();
}
cout << endl;
cout << setw(15) << "quick w/select";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(9) << sort_array.quick_selection_sort();
}
cout << endl;
cout << setw(15) << "bubble optimzed";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(9) << sort_array.bubble_sort_optimized();
}
cout << endl;
break;
case '2':
sort_array.make_array_sorted();
sort_array.get_ptr_array()[0] = sort_array.get_array_size();
cout << "SHOW ARRAY\r\n";
showArray(sort_array.get_ptr_array(), sort_array.get_array_size());
cout << endl;
cout << "BUBBLE SORT TIME: " << sort_array.bubble_sort_optimized() << "ms" << endl;
cout << "\r\nSHOW ARRAY\r\n";
showArray(sort_array.get_ptr_array(), sort_array.get_array_size());
cout << endl;
break;
case '3':
sort_array.make_array_sorted();
sort_array.get_ptr_array()[sort_array.get_array_size() - 1] = -1;
cout << "SHOW ARRAY\r\n";
showArray(sort_array.get_ptr_array(), sort_array.get_array_size());
cout << endl;
cout << "BUBBLE SORT REVERSED TIME: " << sort_array.bubble_sort_reversed() << "ms" << endl;
cout << "\r\nSHOW ARRAY\r\n";
showArray(sort_array.get_ptr_array(), sort_array.get_array_size());
cout << endl;
break;
case '4':
cout << setw(15) << "ALGORITHM";
for (i = 0; ARRAYSIZES20M[i]; cout << setw(9) << ARRAYSIZES20M[i++]);
cout << COLUMNHEADERS20M;
cout << "SORTED ARRAY" << endl;
cout << setw(15) << "insertion";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.make_array_sorted();
cout << setw(9) << sort_array.insertion_sort();
}
cout << endl;
cout << setw(15) << "bubble";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.make_array_sorted();
cout << setw(9) << sort_array.bubble_sort();
}
cout << endl;
cout << setw(15) << "radix";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.make_array_sorted();
cout << setw(9) << sort_array.radix_sort();
}
cout << endl;
cout << setw(15) << "quick";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.make_array_sorted();
cout << setw(9) << sort_array.quick_sort();
}
cout << endl;
cout << setw(15) << "quick w/insert";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.make_array_sorted();
cout << setw(9) << sort_array.quick_insertion_sort();
}
cout << endl;
cout << setw(15) << "quick w/select";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.make_array_sorted();
cout << setw(9) << sort_array.quick_selection_sort();
}
cout << endl;
cout << "RANDOM ARRAY" << endl;
cout << setw(15) << "radix";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.randomize_array();
cout << setw(9) << sort_array.radix_sort();
}
cout << endl;
cout << setw(15) << "quick";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.randomize_array();
cout << setw(9) << sort_array.quick_sort();
}
cout << endl;
cout << setw(15) << "quick w/insert";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.randomize_array();
cout << setw(9) << sort_array.quick_insertion_sort();
}
cout << endl;
cout << setw(15) << "quick w/select";
for (i = 0; ARRAYSIZES20M[i]; i++)
{
sort_array.allocate(ARRAYSIZES20M[i]);
sort_array.randomize_array();
cout << setw(9) << sort_array.quick_selection_sort();
}
cout << endl;
break;
case 'Q':
case 'q':
innerloop = false;
break;
}
}
break;
case '2':
sort_array.allocate(100000); //PRE ALLOC THE ARRAY
innerloop = 1;
while (innerloop)
{
cout << "\r\n---=== USING " << sort_array.get_array_size() << " ELEMENT ARRAY ===---\r\n";
cout << "Q. to quit.\r\n";
cout << "1. Randomize the array and run the sorting algorithms.\r\n";
cout << "2. Sort the array and run the sorting algorithms.\r\n";
cout << "3. Sort the array, modify first element, run the sorting algorithms.\r\n";
cout << "4. Sort the array, modify last element, run the sorting algorithms.\r\n";
cout << "5. Sort the array, swap first/last element, run the sorting algorithms.\r\n>";
getline(cin, choice);
switch (choice[0])
{
case '1':
cout << setw(16) << " ";
for (i = 0; ARRAYSIZES100K[i]; cout << setw(7) << ARRAYSIZES100K[i++]);
cout << COLUMNHEADERS100K;
cout << setw(16) << "insertion";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.randomize_array();
cout << setw(7) << sort_array.insertion_sort();
}
cout << endl;
cout << setw(16) << "selection";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.randomize_array();
cout << setw(7) << sort_array.selection_sort();
}
cout << endl;
cout << setw(16) << "bubble";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.randomize_array();
cout << setw(7) << sort_array.bubble_sort();
}
cout << endl;
cout << setw(16) << "bubble optimized";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.randomize_array();
cout << setw(7) << sort_array.bubble_sort_optimized();
}
cout << endl;
cout << setw(16) << "bubble reversed";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.randomize_array();
cout << setw(7) << sort_array.bubble_sort_reversed();
}
cout << endl;
cout << setw(16) << "quick";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.randomize_array();
cout << setw(7) << sort_array.quick_sort();
}
cout << endl;
cout << setw(16) << "quick w/insert";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.randomize_array();
cout << setw(7) << sort_array.quick_insertion_sort();
}
cout << endl;
cout << setw(16) << "radix";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.randomize_array();
cout << setw(7) << sort_array.radix_sort();
}
cout << endl;
break;
case '2':
cout << setw(16) << " ";
for (i = 0; ARRAYSIZES100K[i]; cout << setw(7) << ARRAYSIZES100K[i++]);
cout << COLUMNHEADERS100K;
cout << setw(16) << "insertion";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
cout << setw(7) << sort_array.insertion_sort();
}
cout << endl;
cout << setw(16) << "selection";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
cout << setw(7) << sort_array.selection_sort();
}
cout << endl;
cout << setw(16) << "bubble";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
cout << setw(7) << sort_array.bubble_sort();
}
cout << endl;
cout << setw(16) << "bubble optimized";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
cout << setw(7) << sort_array.bubble_sort_optimized();
}
cout << endl;
cout << setw(16) << "bubble reversed";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
cout << setw(7) << sort_array.bubble_sort_reversed();
}
cout << endl;
cout << setw(16) << "quick";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
cout << setw(7) << sort_array.quick_sort();
}
cout << endl;
cout << setw(16) << "quick w/insert";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
cout << setw(7) << sort_array.quick_insertion_sort();
}
cout << endl;
cout << setw(16) << "radix";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
cout << setw(7) << sort_array.radix_sort();
}
cout << endl;
break;
case '3':
cout << setw(16) << " ";
for (i = 0; ARRAYSIZES100K[i]; cout << setw(7) << ARRAYSIZES100K[i++]);
cout << COLUMNHEADERS100K;
cout << setw(16) << "insertion";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[0] = sort_array.get_array_size();
cout << setw(7) << sort_array.insertion_sort();
}
cout << endl;
cout << setw(16) << "selection";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[0] = sort_array.get_array_size();
cout << setw(7) << sort_array.selection_sort();
}
cout << endl;
cout << setw(16) << "bubble";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[0] = sort_array.get_array_size();
cout << setw(7) << sort_array.bubble_sort();
}
cout << endl;
cout << setw(16) << "bubble optimized";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[0] = sort_array.get_array_size();
cout << setw(7) << sort_array.bubble_sort_optimized();
}
cout << endl;
cout << setw(16) << "bubble reversed";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[0] = sort_array.get_array_size();
cout << setw(7) << sort_array.bubble_sort_reversed();
}
cout << endl;
cout << setw(16) << "quick";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[0] = sort_array.get_array_size();
cout << setw(7) << sort_array.quick_sort();
}
cout << endl;
cout << setw(16) << "quick w/insert";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[0] = sort_array.get_array_size();
cout << setw(7) << sort_array.quick_insertion_sort();
}
cout << endl;
cout << setw(16) << "radix";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[0] = sort_array.get_array_size();
cout << setw(7) << sort_array.radix_sort();
}
cout << endl;
break;
case '4':
cout << setw(16) << " ";
for (i = 0; ARRAYSIZES100K[i]; cout << setw(7) << ARRAYSIZES100K[i++]);
cout << COLUMNHEADERS100K;
cout << setw(16) << "insertion";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[sort_array.get_array_size() - 1] = 0;
cout << setw(7) << sort_array.insertion_sort();
}
cout << endl;
cout << setw(16) << "selection";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[sort_array.get_array_size() - 1] = 0;
cout << setw(7) << sort_array.selection_sort();
}
cout << endl;
cout << setw(16) << "bubble";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[sort_array.get_array_size() - 1] = 0;
cout << setw(7) << sort_array.bubble_sort();
}
cout << endl;
cout << setw(16) << "bubble optimized";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[sort_array.get_array_size() - 1] = 0;
cout << setw(7) << sort_array.bubble_sort_optimized();
}
cout << endl;
cout << setw(16) << "bubble reversed";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[sort_array.get_array_size() - 1] = 0;
cout << setw(7) << sort_array.bubble_sort_reversed();
}
cout << endl;
cout << setw(16) << "quick";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[sort_array.get_array_size() - 1] = 0;
cout << setw(7) << sort_array.quick_sort();
}
cout << endl;
cout << setw(16) << "quick w/insert";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[sort_array.get_array_size() - 1] = 0;
cout << setw(7) << sort_array.quick_insertion_sort();
}
cout << endl;
cout << setw(16) << "radix";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
sort_array.get_ptr_array()[sort_array.get_array_size() - 1] = 0;
cout << setw(7) << sort_array.radix_sort();
}
cout << endl;
break;
case '5':
cout << setw(16) << " ";
for (i = 0; ARRAYSIZES100K[i]; cout << setw(7) << ARRAYSIZES100K[i++]);
cout << COLUMNHEADERS100K;
cout << setw(16) << "insertion";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(7) << sort_array.insertion_sort();
}
cout << endl;
cout << setw(16) << "selection";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(7) << sort_array.selection_sort();
}
cout << endl;
cout << setw(16) << "bubble";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(7) << sort_array.bubble_sort();
}
cout << endl;
cout << setw(16) << "bubble optimized";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(7) << sort_array.bubble_sort_optimized();
}
cout << endl;
cout << setw(16) << "bubble reversed";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(7) << sort_array.bubble_sort_reversed();
}
cout << endl;
cout << setw(16) << "quick";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(7) << sort_array.quick_sort();
}
cout << endl;
cout << setw(16) << "quick w/insert";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(7) << sort_array.quick_insertion_sort();
}
cout << endl;
cout << setw(16) << "radix";
for (i = 0; ARRAYSIZES100K[i]; i++)
{
sort_array.allocate(ARRAYSIZES100K[i]);
sort_array.make_array_sorted();
swap_first_last_elements(sort_array);
cout << setw(7) << sort_array.radix_sort();
}
cout << endl;
break;
case 'Q':
case 'q':
innerloop = false;
break;
}
}
break;
case 'Q':
case 'q':
outerloop = false;
break;
}
}
return 0;
}
Program output:
Q. to quit
1. Use 20,000,000 element array
2. Use 100,000 element array
>1
---=== USING 20000000 ELEMENT ARRAY ===---
Q. to quit.
1. Swap first/last elements & compare QUICK, RADIX, INSERTION and BUBBLE SORT.
2. Assign last value to first element of sorted array and run BUBBLE SORT.
3. Assign first value to last element of sorted array, run BUBBLE SORT REVERSED
4. Compare QUICK, RADIX, INSERTION and BUBBLE SORT.
>1
1250000 2500000 5000000 10000000 20000000
--------------------------------------------------------------------
insertion 8 12 19 26 49
radix 26 51 104 208 415
quick 16 35 72 148 307
quick w/insert 12 26 55 115 240
bubble optimzed 5 9 19 39 77
---=== USING 20000000 ELEMENT ARRAY ===---
Q. to quit.
1. Swap first/last elements and compare QUICK, RADIX and BUBBLE SORT.
2. Assign last value to first element of sorted array and run BUBBLE SORT.
3. Assign first value to last element of sorted array, run BUBBLE SORT REVERSED
4. Compare QUICK, RADIX, INSERTION and BUBBLE SORT.
>4
ALGORITHM 1250000 2500000 5000000 10000000 20000000
--------------------------------------------------------------------
SORTED ARRAY
insertion 5 11 10 17 34
bubble 0 2 3 5 11
radix 26 52 103 208 415
quick 17 35 72 148 308
quick w/insert 13 27 55 117 241
RANDOM ARRAY
radix 106 219 454 940 1942
quick 88 182 378 770 1640
quick w/insert 71 147 308 656 1335
---=== USING 20000000 ELEMENT ARRAY ===---
Q. to quit.
1. Swap first/last elements and compare QUICK, RADIX and BUBBLE SORT.
2. Assign last value to first element of sorted array and run BUBBLE SORT.
3. Assign first value to last element of sorted array, run BUBBLE SORT REVERSED
4. Compare QUICK, RADIX, INSERTION and BUBBLE SORT.
>q
Q. to quit
1. Use 20,000,000 element array
2. Use 100,000 element array
>2
---=== USING 100000 ELEMENT ARRAY ===---
Q. to quit.
1. Randomize the array and run the sorting algorithms.
2. Sort the array and run the sorting algorithms.
3. Sort the array, modify first element, run the sorting algorithms.
4. Sort the array, modify last element, run the sorting algorithms.
5. Sort the array, swap first/last element, run the sorting algorithms.
>1
3125 6250 12500 25000 50000 100000
--------------------------------------------------------------------
insertion 3 12 23 82 327 1303
selection 3 16 51 186 705 2735
bubble 9 44 204 865 3569 14539
bubble optimized 7 32 135 553 2233 8948
bubble reversed 8 44 203 879 3609 14718
quick 0 1 1 2 3 6
quick w/insert 0 1 0 1 2 5
radix 0 0 1 1 4 7
---=== USING 100000 ELEMENT ARRAY ===---
Q. to quit.
1. Randomize the array and run the sorting algorithms.
2. Sort the array and run the sorting algorithms.
3. Sort the array, modify first element, run the sorting algorithms.
4. Sort the array, modify last element, run the sorting algorithms.
5. Sort the array, swap first/last element, run the sorting algorithms.
>2
3125 6250 12500 25000 50000 100000
--------------------------------------------------------------------
insertion 0 1 0 0 1 0
selection 6 21 44 164 655 2604
bubble 0 0 0 0 0 0
bubble optimized 0 0 0 0 0 0
bubble reversed 0 0 0 0 0 0
quick 0 0 0 0 1 1
quick w/insert 0 0 1 0 0 1
radix 0 0 0 0 1 2
---=== USING 100000 ELEMENT ARRAY ===---
Q. to quit.
1. Randomize the array and run the sorting algorithms.
2. Sort the array and run the sorting algorithms.
3. Sort the array, modify first element, run the sorting algorithms.
4. Sort the array, modify last element, run the sorting algorithms.
5. Sort the array, swap first/last element, run the sorting algorithms.
>3
3125 6250 12500 25000 50000 100000
--------------------------------------------------------------------
insertion 0 0 0 1 0 1
selection 6 23 41 162 646 2609
bubble 0 0 0 0 0 0
bubble optimized 0 0 0 0 0 1
bubble reversed 6 20 81 327 1305 5246
quick 0 0 0 0 1 1
quick w/insert 0 0 0 0 0 1
radix 0 0 0 1 1 2
---=== USING 100000 ELEMENT ARRAY ===---
Q. to quit.
1. Randomize the array and run the sorting algorithms.
2. Sort the array and run the sorting algorithms.
3. Sort the array, modify first element, run the sorting algorithms.
4. Sort the array, modify last element, run the sorting algorithms.
5. Sort the array, swap first/last element, run the sorting algorithms.
>4
3125 6250 12500 25000 50000 100000
--------------------------------------------------------------------
insertion 0 0 0 0 1 0
selection 6 25 41 165 650 2603
bubble 6 21 82 326 1304 5200
bubble optimized 0 0 0 0 0 0
bubble reversed 0 0 0 0 0 1
quick 0 0 1 0 1 1
quick w/insert 0 0 0 0 0 1
radix 0 0 0 0 1 3
---=== USING 100000 ELEMENT ARRAY ===---
Q. to quit.
1. Randomize the array and run the sorting algorithms.
2. Sort the array and run the sorting algorithms.
3. Sort the array, modify first element, run the sorting algorithms.
4. Sort the array, modify last element, run the sorting algorithms.
5. Sort the array, swap first/last element, run the sorting algorithms.
>5
3125 6250 12500 25000 50000 100000
--------------------------------------------------------------------
insertion 0 0 0 0 0 0
selection 6 25 66 163 652 2602
bubble 5 21 82 325 1303 5203
bubble optimized 0 0 0 0 1 0
bubble reversed 5 21 82 328 1303 5242
quick 0 0 0 1 0 2
quick w/insert 0 1 0 0 0 0
radix 0 0 1 0 1 2
---=== USING 100000 ELEMENT ARRAY ===---
Q. to quit.
1. Randomize the array and run the sorting algorithms.
2. Sort the array and run the sorting algorithms.
3. Sort the array, modify first element, run the sorting algorithms.
4. Sort the array, modify last element, run the sorting algorithms.
5. Sort the array, swap first/last element, run the sorting algorithms.
>
Comment
