#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <string.h>
#include <random>
#include <ctime>
using namespace std;
const int ARRAYSIZE = 1024 * 100; //1024; // * 1024;
unsigned long int itterations = 0;
int callDepth = 0;
int maxCallDepth = 0;
time_t start_time, end_time;
unsigned int duration;
/**
*
* @param aa
*/
void initRanArray(int arr[]) {
// create source of randomness, and initialize it with non-deterministic seed
std::random_device r;
std::seed_seq seed{r(), r(), r(), r(), r(), r(), r(), r()};
std::mt19937 eng{seed};
// a distribution that takes randomness and produces values in specified range
std::uniform_int_distribution<> dist(1, ARRAYSIZE);
//// Providing a seed value
//srand((unsigned) time(NULL));
for (int i = 0; i < ARRAYSIZE; i ++) {
// Get a random number
//aa[i] = rand();
arr[i] = dist(eng);
}
}
/**
*
* @param bestArr
* @param worstArr
*/
void initBestAndWorstCaseArrays(int bestArr[], int worstArr[]) {
for (int i = 0; i < ARRAYSIZE; i ++) {
bestArr[i] = i;
worstArr[i] = ARRAYSIZE - i;
}
}
/**
*
* @param aa
* @param bb
*/
void reinitArray(int tempateArray[], int destArray[]) {
for (int i = 0; i < ARRAYSIZE; i ++) {
destArray[i] = tempateArray[i];
}
}
/**
*
* @param a
*/
void printArray(int a[]) {
int incr = 1;
if (ARRAYSIZE > 200) {
incr = ARRAYSIZE / 20;
}
for (int i = 0; i < ARRAYSIZE; i += incr) {
cout << i << ": " << a[i] << endl;
}
}
/**
*
* @param valArr
* @param leftIndex
* @param rightIndex
*/
void quickSort(int valArr[], int leftIndex = 0, int rightIndex = ARRAYSIZE - 1) {
// *************************
auto swap = [](int & tmp1, int & tmp2) {
int tmp;
tmp = tmp1; tmp1 = tmp2; tmp2 = tmp;
};
// *************************
auto partition = [&swap](int a[], int lindex, int rindex) {
int pivotValue = a[rindex];
int i = lindex - 1;
for (int j = lindex; j < rindex; j ++) {
if (a[j] <= pivotValue) {
i ++;
swap(a[i], a[j]);
}
itterations ++;
}
swap (a[i + 1], a[rindex]);
return i + 1; // return new pivot index
};
// *************************
if (leftIndex < rightIndex) {
int pivotIndex = partition (valArr, leftIndex, rightIndex);
callDepth ++;
if (callDepth > maxCallDepth) {
maxCallDepth = callDepth;
}
quickSort(valArr, leftIndex, pivotIndex - 1);
quickSort(valArr, pivotIndex + 1, rightIndex);
callDepth --;
}
}
/**
*
* @param arr
* @param message
*/
void sortAndPrint(int arr[], string message) {
maxCallDepth = 0;
itterations = 0;
cout << "print :" << endl;
printArray(arr);
cout << "start " << message << " sort" << endl;
start_time = time(NULL);
quickSort(arr, 0, ARRAYSIZE - 1);
end_time = time(NULL);
duration = end_time - start_time;
cout << "end sort, print result" << endl;
printArray(arr);
cout << message << " sort duration: " << duration << endl;
cout << "itterations: " << itterations << endl;
cout << "max depth: " << maxCallDepth << endl;
cout << "*************************************" << endl;
cout << "*************************************" << endl;
}
/*
*
*/
int main(int argc, char** argv) {
cout << "main" << endl;
int * randNumbers = new int[ARRAYSIZE];
int * sortedNumbers = new int[ARRAYSIZE];
int * invSortedNumbers = new int[ARRAYSIZE];
cout << "start init" << endl;
initRanArray(randNumbers);
initBestAndWorstCaseArrays(invSortedNumbers, sortedNumbers);
sortAndPrint(randNumbers, "random numbers");
sortAndPrint(invSortedNumbers, "inv sorted numbers");
sortAndPrint(sortedNumbers, "sorted numbers");
delete randNumbers;
delete invSortedNumbers;
delete sortedNumbers;
return 0;
}
Related