Hi, I need to create a program in C that meets the following requirements but I\

Question

Hi, I need to create a program in C that meets the following requirements but I'm lost on how to do it.

1) Create an array of size 20 and initialize it with random numbers between 1-100.
2) Sort the array using Insertion Sort, and print out the sorted array and the time it took your algorithm to sort it (in milliseconds).
3) Sort the original array again, this time using Selection Sort, and print out the sorted array and the time it took your algorithm to sort it (in milliseconds).
4) Sort the original array again, this time using Bubble Sort, and print out the sorted array and the time it took your algorithm to sort it (in milliseconds).
5) Divide the original array into 2 arrays of size 10, and sort the array again, this time using Merge Sort, and print out the sorted array and the time it took your algorithm to sort it (in milliseconds).

Explanation / Answer

#include <sys/time.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

float timedifference_msec(struct timeval t0, struct timeval t1)
{
return (t1.tv_sec - t0.tv_sec) * 1000.0f + (t1.tv_usec - t0.tv_usec) / 1000.0f;
}

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;
}
}
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
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]);
}
}

void printArray(int arr[], int n)
{
int i;
for (i=0; i < n; i++)
printf("%d ", arr[i]);
printf(" ");
}
void bubbleSort( int a[], int n )
{   
int i, j;
for(i = 0; i < n; i++)
{
for(j = 1; j < (n-i); j++)
{
if(a[j-1] > a[j])   
swap(&a[j-1],&a[j]);   
}
}
}
int main()
{
   struct timeval t0;
   struct timeval t1;
   float elapsed;

   int arr[20];
   int i;
   for(i=0; i<20; i++){
       arr[i] = (rand()%100)+1;
   }
int n = sizeof(arr)/sizeof(arr[0]);

   printArray(arr, n);

   gettimeofday(&t0, 0);
insertionSort(arr, n);
   gettimeofday(&t1, 0);

   printArray(arr, n);

   elapsed = timedifference_msec(t0, t1);
   printf("Executed insertionSort in %f milliseconds. ", elapsed);

   gettimeofday(&t0, 0);
selectionSort(arr, n);
   gettimeofday(&t1, 0);

   printArray(arr, n);

   elapsed = timedifference_msec(t0, t1);
   printf("Executed selectionSort in %f milliseconds. ", elapsed);

   gettimeofday(&t0, 0);
bubbleSort(arr, n);
   gettimeofday(&t1, 0);

   printArray(arr, n);

   elapsed = timedifference_msec(t0, t1);
   printf("Executed bubbleSort in %f milliseconds. ", elapsed);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

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