# PROWAREtech

articles » current » c-plus-plus » algorithms » sorting-study

## 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);
}

{
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;

}
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();
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 << 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 << "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 << 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 << 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 << 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 << 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 << 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.
>
```

 This site uses cookies. Cookies are simple text files stored on the user's computer. They are used for adding features and security to this site. Read the privacy policy.