# Data Structures 1 Code

### Data Structures 1 Code (C++)

main.cpp

``````#include <iostream>
#include <string>
#include <chrono>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;
using std::chrono::duration_cast;
using std::chrono::milliseconds;

const int maxNumber = 100000;						//max number that can be in the vector
const int loopNum = 10;								//number of times the program will loop (2 for debugging, 5 for real testing)
const int data_loopNum = 11;						//how many times dataMultiplier will multiply dataIncrement	(5 for debugging, 15 for real)
const int dataMultiplier = 2;						//how much the dataIncrement is multiplied by each loop
const int dataIncriment = 100;						//how much the data increments by each time
//total number of samples = (incriment * multiplier) = incriment (run data_loopNum times)

//function declarations
int generateNums(int choice, int dataSize, vector <int>numbers);
int bubbleSort(vector<int> numbers);
void printVector(vector<int> numbers);
void exportResults(int time_taken[data_loopNum][loopNum], string filepath);

void main() {
int choice = 0;
int time_taken[data_loopNum][loopNum];
int counter = 0;
int dataSize = dataIncriment;
string filepath;
std::vector<int> numbers;

cout << endl << "Which sort would you like to test?" << endl;
cout << "1 -> Radix Sort" << endl;
cout << "2 -> Bubble Sort" << endl << endl;
cin >> choice;

switch (choice) {
default: return;
for (counter = 0; counter < loopNum; counter++) {
for (int data_counter = 0; data_counter < data_loopNum; data_counter++)
{
cout << "-----------------------------------------------" << endl;
cout << "Current number of loops for each data size: " << loopNum << endl;
for (counter = 0; counter < loopNum; counter++) {
time_taken[data_counter][counter] = generateNums(choice, dataSize, numbers);
}

dataSize = dataSize * dataMultiplier;								//every time the program has looped 5 times for a data size, this will increment the data size by dataIncriment
}
exportResults(time_taken, filepath);									//write the time taken to the .csv file
}
break;
case 2: //call bubble sort
filepath = "bubble_sort_times.csv";
for (int data_counter = 0; data_counter < data_loopNum; data_counter++)
{
cout << "-----------------------------------------------" << endl;
cout << "Current number of loops for each data size: " << loopNum << endl;
for (counter = 0; counter < loopNum; counter++) {
time_taken[data_counter][counter] = generateNums(choice, dataSize, numbers);
}

dataSize *= dataMultiplier;									//every time the program has looped 5 times for a data size, this will increment the data size by dataIncriment
}
exportResults(time_taken, filepath);							//write the time taken to the .csv file
break;
}
}

int generateNums(int choice, int dataSize, vector<int> numbers) {
int time_taken;

srand(time(NULL));

cout << "Generating random numbers..." << endl;

numbers.empty();

// Start timing
the_clock::time_point start = the_clock::now();

for (int counter = 0; counter < dataSize; counter++)
{
int x = rand() % maxNumber + 1;	//Generates a random number between 1 & maxNumber
numbers.push_back (x);
}

// Stop timing
the_clock::time_point end = the_clock::now();
// Compute the difference between the two times in milliseconds
auto time_taken_sort = duration_cast<milliseconds>(end - start).count();

cout << "Current data size: " << numbers.size() << endl;

cout << "Number generation complete (" << time_taken_sort << "ms)" << endl;

if (choice == 1)
{
}
else if (choice == 2)
{
time_taken = bubbleSort(numbers);
}
return time_taken;
}

vector<int>::iterator i;

// find the max number in the given list (used in loop termination)
int maxNumber = 0;

// Start timing
the_clock::time_point start = the_clock::now();

for (i = numbers.begin(); i != numbers.end(); i++)
{
if (*i > maxNumber)
maxNumber = *i;
}

//run the loop for each of the decimal places
int exp = 1;
int *tmpBuffer = new int[numbers.size()];
while (maxNumber / exp > 0)
{
int decimalBucket = { 0 };
//count the occurences in this decimal digit
for (i = numbers.begin(); i != numbers.end(); i++)
{
decimalBucket[*i / exp % 10]++;			//gets the value of the exp and counts it by adding 1 to the corresponding place in the array
}
//Prepare the position counters to be used for re-ordering the numbers for this decimal place
for (int counter = 1; counter < 10; counter++)
{
decimalBucket[counter] += decimalBucket[counter - 1];
}
//Re order the numbers in the tmpbuffer and later copy back to original buffer
for (i = numbers.end() - 1; i >= numbers.begin(); i--)
{
tmpBuffer[--decimalBucket[*i / exp % 10]] = *i;

if (i == numbers.begin())				//checks if the iterator is at the start of the vector to prevent overflow
{
break;
}
}
int counter = 0;
for (i = numbers.begin(); i != numbers.end(); i++)
{
*i = tmpBuffer[counter];
counter++;
}
exp *= 10;									//multiply exp by 10 to move to next decimal place

}

// Stop timing
the_clock::time_point end = the_clock::now();

//printVector(numbers);							//(used for debugging)

// Compute the difference between the two times in milliseconds
auto time_taken = duration_cast<milliseconds>(end - start).count();

cout << "Sorting Complete (" << time_taken << "ms)" << endl << endl;

return time_taken;
}

int bubbleSort(vector<int> numbers) {
int counter = 0;
int swaps = -1;

// Start timing
the_clock::time_point start = the_clock::now();

while (swaps != 0) {
counter = 0;																		//sets counter back to 0 at the start of each run
swaps = 0;

for (vector<int>::iterator i = numbers.begin(); i != numbers.end(); i++) {			//for all items in the vector

if (i != numbers.end() && (i + 1) == numbers.end())								//checks if the iterator is at the end of the vector to prevent crash
{
break;
}
else if (*i > *(i + 1))															//if current value > next value
{
//iter_swap(numbers.begin() + *i, numbers.begin() + *i + 1);				//old code
swap(numbers[counter], numbers[counter + 1]);								//swap them

swaps++;
}

}
}

// Stop timing
the_clock::time_point end = the_clock::now();
// Compute the difference between the two times in milliseconds
auto time_taken = duration_cast<milliseconds>(end - start).count();

cout << "Sorting Complete (" << time_taken << "ms)" << endl << endl;

//printVector(numbers);																	//used for debugging (not to be used with large samples of data)

return time_taken;
}

void exportResults(int time_taken[data_loopNum][loopNum], string filepath) {
ofstream myfile;
int counter = 0;
int dataSize = dataIncriment;
cout << "Writing to file..." << endl;

myfile.open(filepath);
myfile << "Data Size,";

for (int data_counter = 0; data_counter < data_loopNum; data_counter++)
{
myfile << (dataSize) << ",";															//prints data size
dataSize *= dataMultiplier;
}

for (counter = 0; counter < loopNum; counter++)
{
myfile << endl << "Run " << counter + 1 << "(ms)";										//outputs the run number for each time
for (int data_counter = 0; data_counter < data_loopNum; data_counter++)
{
myfile << "," << time_taken[data_counter][counter];									//prints time for each data size
}
}

myfile.close();																				//closes the file

cout << "Writing to file complete." << endl << endl;

return;
}

void printVector(vector<int> numbers) {
for (std::vector<int>::iterator i = numbers.begin(); i != numbers.end(); ++i)
{
cout << *i << ", ";
}

cout << endl;

return;
}

// Start timing
//the_clock::time_point start = the_clock::now();

// Stop timing
//the_clock::time_point end = the_clock::now();

// Compute the difference between the two times in milliseconds
//auto time_taken = duration_cast<milliseconds>(end - start).count();

`````` ### Written by Zack-Not-Zac

4th Year Ethical Hacking Student at Abertay University

Updated