it is used clock to test the time and compare number of swap.the running of the program is below.
I want to modify this program to add these sorting algorithms inthe c program. please modify this program in order to compare theperformance of these 4 algorithms.
1-Insertion sort algorithm(G1). already available2. Selection sort algorithm(G2). already available3. Quick sort algorithm(G3).4. Heap-sort algorithm (G4).
and then test the program on two data sets
Dataset 1: Run your program on values from 1 to n where n=10,000 (i.e. input numbers are sorted and there is no need to readfrom an input file). Print the execution time on the screen withwell-explained messages for each algorithm.c. Dataset 2: Read the first 10,000 entries only found in“test_dat.txt” and Run your program. Print the sorted input andexecution time to 4 output files called (G1.txtx, G2.txt, G3.txtx,and G4.txt).
this means that add the input reading from file also and writethe sorting on file. the file test_dat.txt I have it.
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>#include <string.h>#include <time.h>
void getRandomArray(int arr[], int n, int max); //initiate an arraywith random numbersvoid cloneArray(int arrB[], int arrA[], int size); //copy an arrayto anothervoid printArray(int arr[], int size); //print all elements of anarrayvoid swap(int *xp, int *yp);void bubbleSort(int arr[], int n); //bubble sortvoid selectionSort(int arr[], int n); //selection sortvoid insertionSort(int list[], int n); //insertion sort
int main(int argc, char *argv[]) {int SIZE, MAX;printf("Enter SIZE and MAX: ");scanf("%d%d", &SIZE, &MAX);
//int arrA[SIZE], arrB[SIZE];int* arrA = (int*)malloc(SIZE * sizeof(int));int* arrB = (int*)malloc(SIZE * sizeof(int));puts("\nGet an array: ");getRandomArray(arrA, SIZE, MAX);cloneArray(arrB, arrA, SIZE);printArray(arrA, SIZE);
clock_t start = clock();bubbleSort(arrB, SIZE);printf("Time = %f ms\n",1000.0*(clock()-start)/CLOCKS_PER_SEC);printArray(arrB, SIZE);
cloneArray(arrB, arrA, SIZE);start = clock();selectionSort(arrB, SIZE);printf("Time = %f ms\n",1000.0*(clock()-start)/CLOCKS_PER_SEC);printArray(arrB, SIZE);
cloneArray(arrB, arrA, SIZE);start = clock();insertionSort(arrB, SIZE);printf("Time = %f ms\n",1000.0*(clock()-start)/CLOCKS_PER_SEC);printArray(arrB, SIZE);free(arrA);free(arrB);}
//=======================================================
void getRandomArray(int arr[], int n, int max) {srand((int)clock());for (int i = 0; i < n; i++) {arr = rand() % max;}}
void cloneArray(int arrB[], int arrA[], int size) {for (int i = 0; i < size; i++)arrB = arrA;}
void printArray(int arr[], int size) {for (int i=0; i < size; i++)printf("%d ", arr);printf("\n");}
void swap(int *xp, int *yp) {int temp = *xp;*xp = *yp;*yp = temp;}
//=======================================================
void bubbleSort(int arr[], int n) {puts("\n==== Bubble Sort ");int comp = 0, swp = 0;bool swapped;for (int i = 0; i < n-1; i++) {swapped = false;for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {swap(&arr[j], &arr[j+1]);swapped = true;swp++;}comp++;}if (swapped == false) break;}printf("No. comparisons = %d; No. swaps = %d\n", comp, swp);}
void selectionSort(int arr[], int n) {puts("\n==== Selection Sort ");int comp = 0, swp = 0;int min_idx;for (int i = 0; i < n-1; i++) {min_idx = i;for (int j = i+1; j < n; j++)if (arr[j] < arr[min_idx]) {min_idx = j;comp++;}swap(&arr[min_idx], &arr);swp++;}printf("No. comparisons = %d; No. swaps = %d\n", comp, swp);}
void insertionSort(int list[], int n) {puts("\n==== Insertion Sort ");int comp = 0, assg = 0;for (int h = 1; h < n; h++) {int key = list[h];int k = h - 1; //start comparing with previous itemwhile (k >= 0 && key < list[k]) {list[k + 1] = list[k];comp++;assg++;--k;}list[k + 1] = key;}printf("No. comparisons = %d; No. assignments = %d\n", comp,assg);} //end insertionSort
- Below Is The Program For Bubble Sort Insertion Sort And Selection Sort To Compare The Performance This Program Get Th 1 (210.12 KiB) Viewed 39 times