Write Program in C++ Instructions… For this assignment you will write your own v

Question

Write Program in C++

Instructions…

For this assignment you will write your own version of a merge sort and a bubble sort -- sorting files of numbers.

   Your programs should read a file integers into an array of integers, sort them from least to greatest, then print the sorted list out.

       (note: you do not have to sort "in-place" -- you can sort into a newly allocated array)

   For you program to allocate a large enough array up front, you may want to have the first number in your data files be the count of how many random numbers are in the file.

      …Or it could be a command line parameter to your program.

   Your version of these programs should include keeping count every time your program compares two items from the list.

     Print the count of comparisons when the programs ends.

      It is up to you how you keep the "count of comparisons" separated from the sorted output list.

      On Linux, you might use stdout and stderr…

      …or you might give filenames as command line args to your programs, and the only stdout form your program will be the stats on how many comparison steps were used to sort the      list.

      …or you might have a command line arg with a filename specifically to **append** stats to

Explanation / Answer

1) Merge Sort

#include<iostream>
#include<stdio.h>
#include<conio.h>
using namespace std;

int count = 0; //Number of comparisons
int n = 0;
const int SIZE = 100;
void merge(int values[], int left_First, int left_Last, int right_First, int right_Last);
void print_array( int a[], int n);
void merge_sort(int a[], int start, int end){
  
if(start < end){
int mid = (start+end)/2;
merge_sort(a,start, mid);
merge_sort(a,mid+1,end);
merge(a, start,mid, mid+1, end);
}
}
void merge(int values[], int left_First, int left_Last, int right_First, int right_Last){
int temp_array[SIZE];
int index = left_First;
int saveFirst = left_First;

while((left_First <= left_Last) && ( right_First <= right_Last)){//Two sub arrays are compared for smallest element

if(values[left_First] < values[right_First]){
temp_array[index] = values[left_First]; //smallest element is assigned to temp
left_First++;
}
else
{
temp_array[index] = values[right_First];
right_First++;
}
index++;
count++; //count of comaparisons per iteration of while loop.
}
  
while(left_First <= left_Last){

temp_array[index] = values[left_First];
left_First++;
index++;
  
}
while(right_First <= right_Last){
temp_array[index] = values[right_First];
right_First++;
index++;
  
}
  
for(index = saveFirst; index <= right_Last; index++)//copies from temp array to values array
values[index] = temp_array[index];
print_array(values,n);
cout << endl;

}

void print_array( int a[], int n){
for (int i=0; i < n; i++)
cout << a[i] << " ";
}

int main(){
  
clrscr();
cout << "Enter number of elements to be sorted : ";
cin >>n;

int a[SIZE];
for (int i=0; i < n; i++){
if(i==0)
cout << "Enter the first element: ";
else
cout << "Enter the next element: ";
cin >> a[i];
}
  
  
int start = 0;
int end = n-1;
merge_sort(a, start, end);
print_array(a, n);
cout << endl;
cout << "Total number of comparisons done during mergesort : "<< count << endl;
getch();
}

2) Bubble Sort

#include<iostream>

using namespace std;

int main()
{
int array[50],num,i,j,temp;
   int count=0; // Number of Comparisons
cout<<"Enter number of elements to be sorted: ";
cin>>num;
cout<<"Enter the elements: "<<endl;

for(i=0;i<num;++i)
   cin>>array[i];

for(i=1;i<num;++i)
{
   for(j=0;j<(num-i);++j)
   {
   if(array[j]>array[j+1])
   {
       temp=array[j];
       array[j]=array[j+1];
       array[j+1]=temp;

   }
   count++; //count of comaparisons per iteration of inner for loop.
   }
}
cout<<"Array after bubble sort:";
for(i=0;i<num;++i)
   cout<<" "<<array[i];
cout<<endl;
cout<<"Total number of comparisons done during Bubble Sort: "<<count;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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