Generate three unsorted lists of data of different sizes: 100, 500, and 1000 ite

Question

Generate three unsorted lists of data of different sizes: 100, 500, and 1000 items. The unsorted lists will consist of a data structure that contains the key – an integer, and a random double number.
Put the structure into an array and sort each array using the 4 different sorts. For each array, you are to determine the Big-O value for each sort for each data size. This is to be calculated and written out by hand. In the sorting routines, you are to calculate the time it takes for each sort. (Printing time is not included). This should be printed in your output. Print the output from each sort into a file. The files should be named selsxxx.dat, sinsxxx.dat, bubxxx.dat, and quickxxx.dat where xxx is the size of the file sorted. You will also use the same data to insert into a binary tree and use the in-order traversal to print the tree. The time to insert the data into the tree and the traversal time should be calculated for each dataset. Along with your calculated Big-O values for each sort, you should show the time it takes for each sort to be performed. Analyze the data and explain your results. Does the actual time agree with your calculations? Which sort is faster? Does the data size make a difference?

Explanation / Answer

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <ctime>
#include <conio.h>
#include <sstream>

using namespace std;

struct data{
   int key;
   double val;
};

struct BST{
private:
   struct node{
       data d;
       node *left;
       node *right;
   };
   node *head;
   void add(node *temp, node *newone){
       if (temp->d.val > newone->d.val){
           if (temp->left == NULL){
               temp->left = newone;
           }
           else{
               add(temp->left, newone);
           }
       }
       else{
           if (temp->right == NULL){
               temp->right = newone;
           }
           else{
               add(temp->right, newone);
           }
       }
   }

public:
   BST(){
       head = NULL;
   }
   void add(int key, int val){
       data d;
       d.key = key;
       d.val = val;
       node *newone = new node;
       newone->d = d;
       newone->left = NULL;
       newone->right = NULL;
       if (head == NULL){
           head = newone;
       }
       else{
           add(head, newone);
       }
   }
};

data *getRandomData(int size){
   data *arr = new data[size];
   for (int i = 0; i < size; ++i){
       arr[i].key = i;
       arr[i].val = rand();
   }
   return arr;
}

void swap(data *arr, int i, int j){
   data temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
}

void bubbleSort(data *arr, int size){
   for (int i = 0; i < size; ++i){
       for (int j = 0; j < size - 1; ++j){
           if (arr[j].val > arr[j + 1].val){
               swap(arr, j, j + 1);
           }
       }
   }
}

void insertionSort(data *arr, int size){
   for (int i = 1; i < size; ++i){
       for (int j = i; j > 0; --j){
           if (arr[j].val < arr[j - 1].val){
               swap(arr, j, j - 1);
           }
           else{
               break;
           }
       }
   }
}

void selectionSort(data *arr, int size){
   int minInd;
   for (int i = 0; i < size - 1; ++i){
       minInd = i;
       for (int j = i; j < size; ++j){
           if (arr[minInd].val > arr[j].val){
               minInd = j;
           }
       }
       swap(arr, i, minInd);
   }
}

void quickSort(data *arr, int left, int right) {
   int i = left, j = right;
   int tmp;
   int pivot = arr[(left + right) / 2].val;

   while (i <= j) {
       while (arr[i].val < pivot)
           i++;
       while (arr[j].val > pivot)
           j--;
       if (i <= j) {
           swap(arr, i, j);
           i++;
           j--;
       }
   };

   if (left < j)
       quickSort(arr, left, j);
   if (i < right)
       quickSort(arr, i, right);
}

data *copyData(data *arr, int size){
   data *newarr = new data[size];
   for (int i = 0; i < size; ++i){
       newarr[i] = arr[i];
   }
   return newarr;
}

void printOutputToFile(string fileName, data *arr, int size){
   string type = fileName;
   stringstream ss;
   ss << fileName << size << ".txt";
   fileName = ss.str();
   ofstream out;
   out.open(fileName.c_str());
   out << "Normal Array is" << endl;
   for (int i = 0; i < size; ++i){
       out << arr[i].val << " ";
   }
   out << endl << endl;
   time_t startTime, endTime;
   int seconds;
   if (type == "sels"){
       time(&startTime);
       selectionSort(arr, size);
       time(&endTime);
       seconds = difftime(endTime, startTime);
   }
   else if (type == "sins"){
       time(&startTime);
       insertionSort(arr, size);
       time(&endTime);
       seconds = difftime(endTime, startTime);
   }
   else if (type == "bub"){
       time(&startTime);
       bubbleSort(arr, size);
       time(&endTime);
       seconds = difftime(endTime, startTime);
   }
   else if (type == "quick"){
       time(&startTime);
       quickSort(arr, 0, size - 1);
       time(&endTime);
       seconds = difftime(endTime, startTime);
   }
   out << "Sorted Array is" << endl;
   for (int i = 0; i < size; ++i){
       out << arr[i].val << " ";
   }
   out << endl << endl;
   out << "It took " << seconds << " Seconds" << endl;
   out.close();
}

int main(){
   srand(time(NULL));
   data *arr, *copy;
   for (int size = 100; size <= 1000;){
       arr = getRandomData(size);
       copy = copyData(arr, size);
       printOutputToFile(string("sels"), arr, size);
       delete[] arr;
       arr = copy;
       copy = copyData(arr, size);
       printOutputToFile(string("sins"), arr, size);
       delete[] arr;
       arr = copy;
       copy = copyData(arr, size);
       printOutputToFile(string("bub"), arr, size);
       delete[] arr;
       arr = copy;
       printOutputToFile(string("quick"), arr, size);
       delete[] arr;
       if (size == 100){
           size = 500;
       }
       else if (size == 500){
           size = 1000;
       }
       else if (size == 1000){
           size = 2000;
       }
   }

   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.