Question

Import a data set (txt file) then do the sorting algorithm using bubble sort, radix sort, insertion sort, and merge sort,

It must show how long it took and how many movements occurred.

Please write codes in C++

Here's data set (should be stored in txt file)

7426
4524
4737
9436
3997
2757
6288
5414
9590
5968
6638
3199
9514
1541
9866
2144
6731
911
2171
6135
6437
912
9417
2662
6606
6349
707
2890
5386
9718
3492
5068
9674
8578
8323
7789
4748
7576
2664
6352
7967
8556
4740
5737
6764
368
1070
3700
1291
5279
9429
9507
2575
3099
2147
9660
2515
2976
4086
8305
6913
1308
7123
7678
8971
7507
139
51
5980
1100
3976
7289
9249
1662
8659
2758
3605
1079
7829
2298
3671
8901
1176
9089
3350
7500
6702
8903
5279

Answer 1

#include<iostream>
#include<fstream>
#include<list>
#include<stdlib.h>
#include<math.h>
#include<conio.h>
#include<time.h>

using namespace std;
static int cm,cb,ci,cr;//variable for counting the number of moves
//display method
void display(int *array, int size)
{
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
//radix sort
void radixSort(int *arr, int n, int max)
{
int i, j, m, p = 1, index, temp, count = 0,s=0;
list<int> q[10]; //radix of decimal number is 10
for(i = 0; i< max; i++) {
m = pow(10, i+1);
p = pow(10, i);
for(j = 0; j<n; j++) {
temp = arr[j]%m;
index = temp/p; //find index for pocket array
q[index].push_back(arr[j]);
}
count = 0;
for(j = 0; j<10; j++) {
//delete from linked lists and store to array
while(!q[j].empty()) {
arr[count] = *(q[j].begin());
q[j].erase(q[j].begin());
count++;cr++;//count number of moves
}
}
}

}
//swapping method
void swapping(int &a, int &b) { //swap the content of a and b
int temp;
temp = a;
a = b;
b = temp;
}
//merge() method
void merge(int *array, int l, int m, int r)
{
int i, j, k, nl, nr;
//size of left and right sub-arrays
nl = m-l+1; nr = r-m;
int larr[nl], rarr[nr];
//fill left and right sub-arrays
for(i = 0; i<nl; i++)
larr[i] = array[l+i];
for(j = 0; j<nr; j++)
rarr[j] = array[m+1+j];
i = 0; j = 0; k = l;
//marge temp arrays to real array
while(i < nl && j<nr) {
if(larr[i] <= rarr[j]) {
array[k] = larr[i]; cm++; //count the number of moves
i++;
}else{
array[k] = rarr[j]; cm++;//count the number of moves
j++;
}
k++;
}
while(i<nl) { //extra element in left array
array[k] = larr[i]; cm++;//count the number of moves
i++; k++;
}
while(j<nr) { //extra element in right array
array[k] = rarr[j]; cm++;//count the number of moves
j++; k++;
}
}
//recursive method to mergesort
void mergeSort(int *array, int l, int r) {
int m;
if(l < r) {
int m = l+(r-l)/2;
// Sort first and second arrays
mergeSort(array, l, m);
mergeSort(array, m+1, r);
merge(array, l, m, r);
}

}
//insertion sort
void insertionSort(int *array, int size) {
int key, j;
for(int i = 1; i<size; i++) {
key = array[i];//take value
j = i;
while(j > 0 && array[j-1]>key) {
array[j] = array[j-1]; ci++; //count the number of moves
j--;
}
array[j] = key; //insert in right place
}

}

void bubbleSort(int *array, int size) {
     
for(int i = 0; i<size; i++) {
int swaps = 0; //flag to detect any swap is there or not
for(int j = 0; j<size-i-1; j++) {
if(array[j] > array[j+1]) { //when the current item is bigger than next
swapping(array[j], array[j+1]); cb++;
swaps = 1; //set swap flag
}
}
if(!swaps)
break; // No swap in this pass, so array is sorted
}

}
//driver program
int main()
{
    int a[200],b[200],c[200],d[200],x,i=0,n;
    ifstream in;
    clock_t begin, end;
double tr,tm,ti,tb;
    //open the files in read mode
   in.open("D://data.txt");
   //if not open
   if(!in)
   {
      cout<<endl<<"Unable to open the source file";
          exit(0);
   }
     
   //read the strings from file
   while(! in.eof())
        {
        in>>x;
        a[i]=x; //store the number in four arrays
        b[i]=x;
        c[i]=x;
        d[i]=x;
           i++;  
       }
       n=i;
   cout<<endl<<"\t\tRADIX SORT\n";
cout <<endl << "Data before Sorting: ";
display(a, n);
//clock begins
    begin = clock();
radixSort(a, n, 4);
end = clock(); //clock ends
//total time taken
tr = (double)(end - begin)/CLOCKS_PER_SEC;

cout <<endl<<"Data after Sorting: ";
display(a, n);


cout<<endl<<"\t\tMERGE SORT\n";

cout <<endl<< "Data before Sorting: ";
display(b, n);
//clock begins
begin = clock();
mergeSort(b, 0, n-1);
end = clock();//clock ends
//total time taken
tm = (double)(end - begin)/CLOCKS_PER_SEC;
cout <<endl<< "Data after Sorting: ";
display(b, n);

cout<<endl<<"\t\tINSERTION SORT\n";
cout <<endl<< "Data before Sorting: ";
display(c, n);
//clock begins
begin = clock();
insertionSort(c, n);   
end = clock();//clock ends
//total time taken
ti = (double)(end - begin)/CLOCKS_PER_SEC;
cout <<endl<< "Data after Sorting: ";
display(c, n);
cout<<endl<<"\t\tBUBBLE SORT\n";
cout <<endl<< "Data before Sorting: ";
display(d, n);
//clock begins
begin = clock();
bubbleSort(d, n);   
end = clock();//clock ends
//total time taken
tb = (double)(end - begin)/CLOCKS_PER_SEC;
cout <<endl<< "Data after Sorting: ";
display(d, n);
//display the times taken by sorting methods
    cout<<endl<<"Total time taken by Radix Sort is : "<<tr;
    cout<<endl<<"Total time taken by merge Sort is : "<<tm;
    cout<<endl<<"Total time taken by insertion Sort is : "<<ti;
    cout<<endl<<"Total time taken by bubble Sort is : "<<tb;
    //display the moves during the sorting methods          
cout<<endl<<cr<<" Number of moves used during radix sort.";
cout<<endl<<cm<<" Numbers of moves used during merge sort.";
cout<<endl<<cb<<" Numbers of moves used during bubble sort.";
cout<<endl<<ci<<" Numbers of moves used during insertion sort.";
  
}

OUTPUT