Sort Algorithm Study

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(n2) on a most data but in the right circumstance is linear, or O(n). SelectionSort is O(n2) 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(n2) 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 = x2
y = x3
Pay attention only to the long running behavior of these graphs.

#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; 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.
>