Please do not copy the other same problem answers because they are all wrong. Th
ID: 3593583 • Letter: P
Question
Please do not copy the other same problem answers because they are all wrong. They didn't help me at all. It is my 4th time posting this question. It is supposed to be done in C or C++
Problem #5. (Programming) Sorting (30 pts) Implement Bubble Sort, Insertion Sort, Merge Sort, Heap Sort, and Quicksort for a list of integers. Your program will get 3 arguments in the command line which are 1) a character indicating the sorting method, 2) input file name, and 3) output file name, as follows: >> Your_Executable.exe Qinput_sort.txt output_sort.txt where 'Q' indicates Quicksort, and "input_sort.txt" and "output_sort.txt" are input and output file names, respectively. You must use ‘B', ‘I', ‘M", ,, and ‘Q' for Bubble Sort, Insertion Sort, Merge Sort, Heap Sort, and Quicksort, respectively You will have the number of objects N followed by the numbers a,a2, .., av in the input file. The output format is similar but the items should be sorted. Refer the following example: my_list.txt my_list sorted.txt 10 1 223 45889 10 54123 10988 2 Assume that the number of objects N ranges 1sN 10,000,000 and the objects are 32-bit integers. You are also required to report the running time to the console. For instance >> Your_Executable.exe Qmy list.txt my list sorted.txt Quicksort for 10 integers took 0.265512 seconds. Note that, you need to measure the computational time only for sorting by excluding times for I/O. You are additionally asked to perform a simple empirical analysis on running times of four different sorting algorithms with respect to the number of items N = 100, 1000, 10000, 10000000 Utilize randomly distributed lists for the experiment and provide a resulting table as follows 100 1,000 Xxxx ms Xxxx ms XxxX ms 10,000 Xxxx ms Xxxx ms XxxX ms 100,000 N/A N/A 1,000,000 10,000,000 N/A NIA N/A N/A Bubble SorXxxx ms Insertion SortXxxx ms Merge Sort Heap Sort uicksort You can fill "N/A" if the algorithm is too slow (e.g., > 10 sec) to solve the problem. Note that, you are recommeded to build your program in the release mode for a faster performance.Explanation / Answer
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<malloc.h>
int *Quicksort(int number[],int first,int last){
int i, j, pivot, temp;
if(first<last){
pivot=first;
i=first;
j=last;
while(i<j){
while(number[i]<=number[pivot]&&i<last)
i++;
while(number[j]>number[pivot])
j--;
if(i<j){
temp=number[i];
number[i]=number[j];
number[j]=temp;
}
}
temp=number[pivot];
number[pivot]=number[j];
number[j]=temp;
Quicksort(number,first,j-1);
Quicksort(number,j+1,last);
}
}
void Mergesort(int number[],int i1,int j1,int i2,int j2){
int temp[100];
int i,j,k;
i=i1;
j=i2;
k=0;
while(i<=j1 && j<=j2)
{
if(number[i]<number[j])
temp[k++]=number[i++];
else
temp[k++]=number[j++];
}
while(i<=j1)
temp[k++]=number[i++];
while(j<=j2)
temp[k++]=number[j++];
for(i=i1,j=0;i<=j2;i++,j++)
number[i]=temp[j];
}
int *sort(int number[],int i,int j) {
int mid;
if(i<j)
{
mid=(i+j)/2;
sort(number,i,mid);
sort(number,mid+1,j);
Mergesort(number,i,mid,mid+1,j);
}
return number;
}
int *Bubblesort(int number[],int n){
int i, j, swap;
for (i = 0 ; i < ( n - 1 ); i++){
for (j = 0 ; j < n-i-1; j++){
if (number[j] > number[j+1]){
swap = number[j];
number[j] = number[j+1];
number[j+1] = swap;
}
}
}
return number;
}
int *Insertionsort(int number[],int n){
int i, j, swap;
for (i = 1;i <= n-1; i++) {
j = i;
while ( j > 0 && number[j] < number[j-1]) {
swap = number[j];
number[j] = number[j-1];
number[j-1] = swap;
j--;
}
}
return number;
}
void down_adjust(int number[],int i){
int j,temp,n,flag=1;
n=number[0];
while(2*i<=n && flag==1)
{
j=2*i;
if(j+1<=n && number[j+1] > number[j])
j=j+1;
if(number[i] > number[j])
flag=0;
else
{
temp=number[i];
number[i]=number[j];
number[j]=temp;
i=j;
}
}
}
void create(int number[]){
int i,n;
n=number[0];
for(i=n/2;i>=1;i--)
down_adjust(number,i);
}
int main(int argc , char *argv[]){
char sort_type,input[20],output[20];int i=0,n;int flag = 0;
sort_type = *argv[1];
strcpy(input,argv[2]);
strcpy(output,argv[3]);
FILE *input_file;
input_file = fopen(input,"r");
if(input_file == NULL){
printf("cannot open the file! ");
exit(0);
}
fscanf(input_file,"%d",&n);
int *number =(int *)malloc(sizeof(int)*n);
while(i < n){
fscanf(input_file,"%d",&number[i++]);
}
if(sort_type == 'Q' || sort_type == 'q'){
printf(" Quicksort ");
Quicksort(number,0,n-1);
flag = 1;
}
else if(sort_type == 'M' || sort_type == 'm'){
printf(" Mergesort ");
sort(number,0, n-1);
flag = 1;
}else if(sort_type == 'H' || sort_type == 'h'){
printf(" Heapsort ");
int last,temp;
number[0]=n;
create(number);
while(number[0] > 1){
last=number[0];
temp=number[1];
number[1]=number[last];
number[last]=temp;
number[0]--;
down_adjust(number,1);
}
flag = 1;
}else if(sort_type == 'B' || sort_type == 'b'){
printf(" Bubblesort ");
Bubblesort(number,n);
flag = 1;
}else if(sort_type == 'I' || sort_type == 'i'){
printf(" Insertionsort ");
Insertionsort(number,n);
flag = 1;
}else
printf("Sorry this sorting Algorithm is not available. ");
if(flag){
FILE *output_file;
output_file = fopen(output,"w+");
i=0;
fprintf(output_file," %d ",n);
while(i < n){
fprintf(output_file," %d ",number[i++]);
}
fclose(output_file);
}
fclose(input_file);
return 0;
}