Write a C program that sorts an array of integers using the Bubble Sort, Selecti

Question

Write a C program that sorts an array of integers using the Bubble Sort, Selection Sort, and Insertion Sort. We will be sorting increasingly larger sets of integers, e.g., N = 10, 100, 1000, 10000, and 100000. To do this efficiently, create a single integer array large enough to hold the largest N, e.g. const int MAX = 100000; int array[MAX]; We will first utilize 10 elements of this array, then 100, then 1000, and ultimately the entire array when testing our sorting algorithms. Using a function, initialize an array with random integers. It is important that your function fill the array with the same set of “random” numbers with each call so that you can correctly compare the various sorting algorithms. You can ensure this by reseeding the random number generator each time you fill the array by using a constant value, e.g, srand(0). Your function should accept as parameters the integer array and the number of elements using the following prototype: void random_array_fill( int array[], int size ); Sort the array using each of the sorting algorithms (Bubble, Selection, and Insertion). Report the time taken to sort the array using each of the sorting algorithms. You must remember to reinitialize the array between sorts using your random_array_fill function, otherwise you will be sorting an array that is already in order! Sample output Generate a report of sorting times as shown below for each sorting algorithm: Bubble Sort N | Time (sec) -------------------- 10 | 0.54 100 | 6.90 1000 | ? 10000 | ? 100000 | ?

Explanation / Answer

#include<stdio.h>
#include <sys/time.h>
#include<stdlib.h>
#define MAX 100000
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 printArray(int arr[], int n)
{
   int i;
   for (i=0; i < n; i++)
       printf("%d ", arr[i]);
   printf(" ");
}
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
void bubbleSort(int arr[], int n)
{
   int i, j;
   for (i = 0; i < n-1; i++)    
       for (j = 0; j < n-i-1; j++)
           if (arr[j] > arr[j+1])
              swap(&arr[j], &arr[j+1]);
}
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]);
    }
}
int main()
{
    srand(time(NULL));
    int data[MAX];
    int i,j;
    struct timeval stop, start;
  
    printf("Enter value of n: ");
    int n;
    scanf("%d",&n)
    for (j = 0; j<n; j++){
           data[j] = rand() % 100;
    }

  
       printArray(data, n);
       gettimeofday(&start, NULL);
       insertionSort(data, n);
       gettimeofday(&stop, NULL);
       printf("Insertion sort took %lf ", (stop.tv_usec - start.tv_usec)/1000000);
       gettimeofday(&start, NULL);
       bubbleSort(data, n);
       gettimeofday(&stop, NULL);
       printf("Bubblesort sort took %lf ", (stop.tv_usec - start.tv_usec)/1000000);
       gettimeofday(&start, NULL);
       selectionSort(data, n);
       gettimeofday(&stop, NULL);
       printf("Selection sort took %lf ", (stop.tv_usec - start.tv_usec)/1000000);
       //return 0;
    

   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.