Question

c++

Run the following sorting algorithms:
1. Bubble sort
2. Insertion sort
3. Quicksort
4. Mergesort
Under the following scenarios for input data:
1. Uniform random
2. Almost sorted (90% sorted – 1 in 10 is out of place)
3. Reverse sorted
On data of sizes 5,000, 10,000, … in increments of 5,000 up to …, 50,000

-Attach a screenshot of a program compilation below

-Attach a screenshot of a successful program run below

-Attach a graph (either line graph or bar graph) below.

3.2 90% Sorted Data (10% of data are out of their sorted position)
--Attach a graph below
3.3 Reverse-Sorted (sorted in non-increasing order) Data
--Attach a graph below

template code:

• //a main template file
  
  #include <iostream>
  #include <iomanip>
  #include <ctime>
  #include <string>
  #include "Sort.h"
  
  using namespace std;
  
  void init_and_run(double**, int*, const int, const int, const int, const int);
  void print(double**, int*, const int, const int, const int, const int);
  
  int main()
  {
  
  int size[] = {100, 1000, 5000, 10000, 50000};
  const int NUM_SIZES = 7;
  const int NUM_SORT_ALGO = 7;
  const int NUM_DATA_TYPES = 3;
  const int NUM_REPEAT = 5;
  
  double* totalSortTime[NUM_DATA_TYPES];
  
  
  init_and_run(totalSortTime, size, NUM_SIZES, NUM_DATA_TYPES, NUM_SORT_ALGO, NUM_REPEAT);
  print(totalSortTime, size, NUM_SIZES, NUM_DATA_TYPES, NUM_SORT_ALGO, NUM_REPEAT);
  
  return 0;
  
  }
  
  void init_and_run(double**totalSortTime, int* size, const int NUM_SIZES, const int NUM_DATA_TYPES, const int NUM_SORT_ALGO, const int NUM_REPEAT)
  
  {
  
  clock_t time;
  
  for(int d = 0; d < NUM_DATA_TYPES; d++) {
  totalSortTime[d] = new double [NUM_SIZES * NUM_SORT_ALGO];
  for(int i = 0; i < NUM_SIZES * NUM_SORT_ALGO; i++)
  totalSortTime[d][i] = 0;
  }
  
  
  for(int d = 0; d < NUM_DATA_TYPES; d++) { //data types
  for(int s = 0; s < NUM_SIZES; s++) { //input sizes
  for(int r = 0; r < NUM_REPEAT; r++) { //repetitions
  Sort st(size[s], d);
  for(int t = 0; t < NUM_SORT_ALGO; t++) { //sort algorithms
  st.setSortType(t);
  time = clock();
  st.run();
  //st.print();
  time = clock() - time;
  totalSortTime[d][s * NUM_SORT_ALGO + t] += time;
  }
  }
  }
  }
  
  for(int d = 0; d < NUM_DATA_TYPES; d++) {
  delete [] totalSortTime[d];
  
  }
  }
  void print(double**totalSortTime, int* size, const int NUM_SIZES, const int NUM_DATA_TYPES, const int NUM_SORT_ALGO, const int NUM_REPEAT)
  {
  //cout << string(25, '=') << " AVG SORTING TIME " << string(25, '=') << endl;
  cout << "\nEach value displayed below shows the average sorting time with five instances.\n";
  cout << "The values may vary depending on the system and the implementation.\n";
  cout << "The relative performances, however, should be the same.\n";
  cout << "So are the performances of those algorithms as N or % of sorted numbers grows." << endl;
  
  string dataType[NUM_DATA_TYPES] = {
  " RANDOM_TBL_SIZE ",
  // " TBL_SIZE_PARTIAL_SORT_25 ",
  // " TBL_SIZE_PARTIAL_SORT_50 ",
  // " TBL_SIZE_PARTIAL_SORT_75 ",
  " TBL_SIZE_PARTIAL_SORT_95 ",
  " REVERSE_SORTED "
  };
  
  string sortAlgo[NUM_SORT_ALGO] = {
  "INSERTION",
  "MERGESORT",
  "QUICKSORT_L",
  "QUICKSORT_R",
  "COUNTING"
  "BUBBLE",
  "SELECTION"
  };
  
  
  cout << fixed << setprecision(2) << endl;
  for(int d = 0; d < NUM_DATA_TYPES; d++) {
  cout << string(25, '-') << left << setw(26) << dataType[d] << string(25, '-') << endl;
  cout << right << setw(7) << "N";
  for(int a = 0; a < NUM_SORT_ALGO; a++)
  cout << right << setw(14) << sortAlgo[a];
  cout << endl;
  
  for(int s = 0; s < NUM_SIZES; s++) {
  cout << right << setw(7) << size[s];
  for(int t = 0; t < NUM_SORT_ALGO; t++)
  cout << right << setw(14) << totalSortTime[d][s * NUM_SORT_ALGO + t]/NUM_REPEAT;
  cout << endl;
  }
  cout << endl;
  }
  }

• //DATAGEN_H template file

  
  #ifndef DATAGEN_H
  #define DATAGEN_H
  
  class DataGen {
  private:
  int modType;
  int sortType;
  int dataType;
  
  int** data;
  int inputSize;
  int arraySize;
  int partialSortSize;
  
  void getRandom();
  void copy();
  void partialSort();
  public:
  DataGen();
  DataGen(int*[], int, int, int);
  void generateData();
  //void partialSort();
  
  };
  
  #endif

• //DataGen.h template file

  
  #include "DataGen.h"
  
  class Sort
  {
  friend class DataGen;
  private:
  int* numbers[5];
  int algo_types;
  int size;
  DataGen *dg;
  
  void (Sort::*fp) ();
  void insertionSort();
  void bubbleSort();
  void selectionSort();
  
  void mergeSort();
  void quickSort_L();
  void quickSort_R();
  void countingSort();
  
  void partition_L(int, int, int&, int&);
  void partition_R(int, int, int&, int&);
  
  void merge(int, int, int[]);
  void recursive_mergeSort(int, int, int[]);
  void recursive_quickSort_L(int, int);
  void recursive_quickSort_R(int, int);
  
  void clear();
  public:
  Sort(int, int);
  ~Sort();
  void setSortType(int);
  void run();
  void print();
  };
  #endif

Answer 1

1.Bubble Sort :-

Code:-

#include<iostream>
using namespace std;
int main()
{
int n, i, j, temp;
cin >> n;
int arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
for(i = 0; i < n - 1; i++)
{
for(j = 0; j < n - i - 1; j++)
{
if(arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
for(i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}

Output:-

Input- 8 5 2 6 12

Output- 2 5 6 8 12

2.Insertion Sort:-

Code:-

#include<iostream>
using namespace std;
int main()
{
int i, n, j, temp, min, key;
cin >> n;
int arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
// comparing whether the first element is greater than the second element
// if yes, then store the largest element to the next position
while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
// storing the smallest element in the correct position
arr[j + 1] = key;
}
for(i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}
Output:-

Input- 5 12 3 4 9 6

Output- 3 4 6 9 12

3.Quick Sort:-

Code:-

#include<iostream>
using namespace std;
int partition(int arr[], int low, int high)
{
int temp;
int pivot = arr[high]; // assuming last element of the array as the pivot element
int i = (low - 1); // assuming the index of i pointer as one position less than the first element
for (int j = low; j <= high - 1; j++) // assuming the index of j pointer as the first position
{

// If current element is smaller than or equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of i pointer and swap the elemets at index i and j
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

// swapping the pivot (last) element and element at i + 1 index
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;

// returning the index of pivot element having lesser elements to the left and greater elements to the right
return (i + 1);
}
void quick_sort(int arr[], int low, int high)
{
if (low < high)
{

// partitioning the single array into two sub-arrays
int pi = partition(arr, low, high);

// sorting the sub-arrays
quick_sort(arr, low, pi - 1);
quick_sort(arr, pi + 1, high);
}
}
int print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}

int main()
{
int n, i;
cin >> n;
int arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
quick_sort(arr, 0, n - 1);
print(arr, n);
}
Output:-

Input- 12 3 1 6 23 7

Output- 1 3 6 7 12 23

4.Merge Sort:-

Code:-

#include <iostream>
using namespace std;
int merge(int arr[], int start, int mid, int end)
{
int i, j, k;
int num1 = mid - start + 1;
int num2 = end - mid;
// create temporary arrays
int arr1[num1], arr2[num2];
// Copy data to temporary arrays arr1[] and arr2[]
for (i = 0; i < num1; i++)
arr1[i] = arr[start + i];
for (j = 0; j < num2; j++)
arr2[j] = arr[mid + 1 + j];
// Merge the temp arrays back into arr[]
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = start; // Initial index of merged subarray
while (i < num1 && j < num2)
{
if (arr1[i] <= arr2[j])
{
arr[k] = arr1[i];
i++;
}
else
{
arr[k] = arr2[j];
j++;
}
k++;
}

// Copy the remaining elements of arr1[], if there are any
while (i < num1)
{
arr[k] = arr1[i];
i++;
k++;
}

// Copy the remaining elements of arr2[], if there are any
while (j < num2)
{
arr[k] = arr2[j];
j++;
k++;
}
}
int divide(int arr[], int start, int end)
{
if(start < end)
{
int mid;
mid = (start + end) / 2;
divide(arr, start, mid);
divide(arr, mid + 1, end);
merge(arr, start, mid, end);
}
}
int print(int arr[], int n)
{
for(int i = 0; i < n; i++)
{
cout << arr[i] << " ";
}
}

int main()
{
int n, i;
cin >> n;
int arr[n];
for(i = 0; i < n; i++)
{
cin >> arr[i];
}
divide(arr, 0, n - 1);
print(arr, n);
}
Output:-

Input- 4 8 13 2 23 16

Output- 2 4 8 13 16 23