Question

Write a C++ program, ask the user about which sorting algorithm they would like to use in order to sort the vector. The four sorting algorithms your program should implement are: selection sort, merge sort, quick sort, and insertion sort. Once a sorting algorithm is selected, your program should display step by step every change that the sorting algorithm does on its journey to completely sorting the integer values of the vector

Your output file should then contain the sorted values of the vector with a single integer on each line.

For example:

Enter a file for input: Input1.txt

Enter a file for output: Output1.txt

What sorting algorithm would you like to use? 1. Selection Sort 2. Merge Sort 3. Quick Sort 4. Insertion Sort

(Enter an integer value for your selection): 2

Original Vector: [14, 7, 3, 12, 9, 11, 6, 2]

Vector is now being sorted:

[14, 7, 3, 12] [9, 11, 6, 2]

[14, 7] [3, 12] [9, 11] [6, 2]

[14] [7] [3] [12] [9] [11] [6] [2]

[7, 14] [3, 12] [9, 11] [2, 6]

[3, 7, 12, 14] [2, 6, 9, 11]

[2, 3, 6, 7, 9, 11, 12, 14]

Answer 1

// SpecialSort.cpp : This file contains the 'main' function. Program execution begins and ends there.

#include <iostream>
#include <fstream>
#include <string>
using namespace std;

// ------------------------------UTILITY FUNCTIONS-------------------------//

void swap(int *xp, int *yp)
{
   int temp = *xp;
   *xp = *yp;
   *yp = temp;
}
void printArray(int arr[], int size)
{
   int i;
   cout << endl;
   for (i = 0; i < size; i++)
       cout << arr[i] << " ";
   cout << endl;
}

// --------------------------------QUICK SORT ------------------------------//

int partition(int *&arr, int low, int high)
{
   int pivot = arr[high]; // pivot
   int i = (low - 1); // Index of smaller element

   for (int j = low; j <= high - 1; j++)
   {
      
       if (arr[j] < pivot)
       {
           i++; // increment index of smaller element
           swap(&arr[i], &arr[j]);
       }
   }
   swap(&arr[i + 1], &arr[high]);
   return (i + 1);
}

void quickSort(int *&arr, int low, int high)
{
   if (low < high)
   {
       /* pi is partitioning index, arr[p] is now
       at right place */
       int pi = partition(arr, low, high);
       printArray(arr, high + 1);
      
       quickSort(arr, low, pi - 1);
       printArray(arr, high + 1);
      
       quickSort(arr, pi + 1, high);
       printArray(arr, high + 1);
   }
}

//------------------------------MERGE SORT --------------------------------//

void merge(int *&arr, int l, int m, int r)
{
   int i, j, k;
   int n1 = m - l + 1;
   int n2 = r - m;

   /* create temp arrays */
   int *L = new int[n1];
   int *R = new int[n2];

  
   for (i = 0; i < n1; i++)
       L[i] = arr[l + i];
   for (j = 0; j < n2; j++)
       R[j] = arr[m + 1 + j];

  
   i = 0;
   j = 0;
   k = l;
   while (i < n1 && j < n2)
   {
       if (L[i] <= R[j])
       {
           arr[k] = L[i];
           i++;
       }
       else
       {
           arr[k] = R[j];
           j++;
       }
       k++;
   }

  
   while (i < n1)
   {
       arr[k] = L[i];
       i++;
       k++;
   }

  
   while (j < n2)
   {
       arr[k] = R[j];
       j++;
       k++;
   }
}

void mergeSort(int *&arr, int l, int r)
{
   if (l < r)
   {
  
       int m = l + (r - l) / 2;
       int n = r + 1;
  
       mergeSort(arr, l, m);
       printArray(arr, n);

       mergeSort(arr, m + 1, r);
       printArray(arr, n);

       merge(arr, l, m, r);
       printArray(arr, n);
   }
}

// -----------------------------INSERTION SORT-------------------------------//

   void insertionSort(int *&arr, int n){
       int i, key, j;
       for (i = 1; i < n; i++)
       {
           key = arr[i];
           j = i - 1;

          
           while (j >= 0 && arr[j] > key)
           {
               arr[j + 1] = arr[j];
               j = j - 1;
           }
           arr[j + 1] = key;
       }
       printArray(arr, n);
   }

  
//------------------------------SELECTION SORT ----------------------------//

   void selectionSort(int *&arr, int n)
   {
       int i, j, min_idx;

  
       for (i = 0; i < n - 1; i++)
       {
          
           min_idx = i;
           for (j = i + 1; j < n; j++)
               if (arr[j] < arr[min_idx])
                   min_idx = j;

          
           swap(&arr[min_idx], &arr[i]);
           printArray(arr, n);
       }
      
   }

  

int main()
{
   int *a = new int[2];
   cout << "Welcome to the sorting program. Enter your choice to sort." << endl;
   cout << "1 for Selection sort" << endl << "2 for Insertion sort"<<endl << "3 for Merge sort" << endl;
   cout << "4 for Quick Sort"<<endl << "Enter 0 to quit "<<endl;
  
   int choice;
   cin >> choice;
   cout << "Enter filename where Array/Vector is stored" << endl;
   string filename;
   cin >> filename;
  
  
   int size = 0;
   string line;
   ifstream myfile(filename);
  
   if (myfile.is_open())
   {
       while (getline(myfile, line))
       {
           size++;
       }
       //delete[]a;
       a = new int[size];
       int i = 0;
       myfile.close();
       myfile.open(filename);
       while (getline(myfile, line)) {
       //   cout << "hey";
               int temp = stoi(line.c_str());
               if (temp) {
                   a[i] = temp;
                   i++;
               }
               else {
                   cout << "File character invalid";
               }
          
       }
       myfile.close();
   }
   else cout << "Unable to open file";
   printArray(a, size);

   if (choice == 1) {
       cout << endl<<"Working on selection sort.." << endl;
       selectionSort(a, size);
   }
   if (choice == 2) {
       cout << endl << "Working on insertion sort.." << endl;
       insertionSort(a, size);

   }
   if (choice == 3) {
       cout << endl << "Working on merge sort.." << endl;
       mergeSort(a, 0, size - 1);

   }
   if (choice == 4) {
       cout << endl << "Working on quick sort.." << endl;
       quickSort(a, 0, size - 1);

   }
   else if (choice == 0) {
       exit(0);
   }

  
   //-------------------------WRITING TO FILE---------------//
   ofstream file;
   cout << "Enter name of file for writing"<<endl;
   string filenamew;
   cin >> filenamew;
   file.open(filenamew);
   if (file.is_open()) {
       for (int i = 0; i < size; i++) {
           file << a[i]<<endl;
       }
   }
   file.close();
}

COMMENT DOWN FOR ANY QUERIES AND<

LEAVE A THUMBS UP IF THIS ANSWER HELPS YOU.