fork download
copy 
  1. // LAB 11 QUICK SORT
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include <time.h>
  6.  
  7. // Function to merge two subarrays into a single sorted array
  8. void merge(int arr[], int left, int mid, int right) {
  9.     int n1 = mid - left + 1;
  10.     int n2 = right - mid;
  11.  
  12.     // Create temporary arrays
  13.     int L[n1], R[n2];
  14.  
  15.     // Copy data to temporary arrays L[] and R[]
  16.     for (int i = 0; i < n1; i++)
  17.         L[i] = arr[left + i];
  18.     for (int j = 0; j < n2; j++)
  19.         R[j] = arr[mid + 1 + j];
  20.  
  21.     // Merge the temporary arrays back into arr[left..right]
  22.     int i = 0, j = 0, k = left;
  23.     while (i < n1 && j < n2) {
  24.         if (L[i] <= R[j]) {
  25.             arr[k] = L[i];
  26.             i++;
  27.         } else {
  28.             arr[k] = R[j];
  29.             j++;
  30.         }
  31.         k++;
  32.     }
  33.  
  34.     // Copy the remaining elements of L[], if any
  35.     while (i < n1) {
  36.         arr[k] = L[i];
  37.         i++;
  38.         k++;
  39.     }
  40.  
  41.     // Copy the remaining elements of R[], if any
  42.     while (j < n2) {
  43.         arr[k] = R[j];
  44.         j++;
  45.         k++;
  46.     }
  47. }
  48.  
  49. // Function to perform Merge Sort
  50. void mergeSort(int arr[], int left, int right) {
  51.     if (left < right) {
  52.         // Find the middle point
  53.         int mid = left + (right - left) / 2;
  54.  
  55.         // Recursively sort the first and second halves
  56.         mergeSort(arr, left, mid);
  57.         mergeSort(arr, mid + 1, right);
  58.  
  59.         // Merge the sorted halves
  60.         merge(arr, left, mid, right);
  61.     }
  62. }
  63.  
  64. // Function to generate a random array of integers
  65. void generateRandomArray(int arr[], int n) {
  66.     for (int i = 0; i < n; i++) {
  67.         arr[i] = rand() % 10000;  // random integers between 0 and 9999
  68.     }
  69. }
  70.  
  71. // Function to plot the graph using gnuplot
  72. void plotGraph(int n_values[], double time_taken[], int num_tests) {
  73.     // Open a pipe to gnuplot
  74.     FILE *gnuplot = popen("gnuplot -persistent", "w");
  75.     if (gnuplot == NULL) {
  76.         fprintf(stderr, "Error opening gnuplot\n");
  77.         return;
  78.     }
  79.  
  80.     // Send commands to gnuplot
  81.     fprintf(gnuplot, "set title 'Time Complexity of Merge Sort'\n");
  82.     fprintf(gnuplot, "set xlabel 'Number of Elements (n)'\n");
  83.     fprintf(gnuplot, "set ylabel 'Time Taken (seconds)'\n");
  84.     fprintf(gnuplot, "plot '-' with linespoints title 'Time vs n'\n");
  85.  
  86.     // Send the data points to gnuplot
  87.     for (int i = 0; i < num_tests; i++) {
  88.         fprintf(gnuplot, "%d %lf\n", n_values[i], time_taken[i]);
  89.     }
  90.  
  91.     // End the plot
  92.     fprintf(gnuplot, "e\n");
  93.     fclose(gnuplot);
  94. }
  95.  
  96. int main() {
  97.     // Seed the random number generator
  98.     srand(time(NULL));
  99.  
  100.     // Set the values for n (can be modified or read from a file)
  101.     int n_values[] = {5000, 10000, 15000, 20000, 25000};  // example values of n
  102.     int num_tests = sizeof(n_values) / sizeof(n_values[0]);
  103.     double time_taken[num_tests];  // Array to store time taken for each n
  104.  
  105.     // Loop over different values of n
  106.     for (int test = 0; test < num_tests; test++) {
  107.         int n = n_values[test];
  108.  
  109.         // Generate an array of random integers of size n
  110.         int *arr = (int *)malloc(n * sizeof(int));
  111.         if (arr == NULL) {
  112.             printf("Memory allocation failed!\n");
  113.             return 1;
  114.         }
  115.         generateRandomArray(arr, n);
  116.  
  117.         // Record the start time
  118.         clock_t start_time = clock();
  119.  
  120.         // Call the mergeSort function
  121.         mergeSort(arr, 0, n - 1);
  122.  
  123.         // Record the end time
  124.         clock_t end_time = clock();
  125.  
  126.         // Calculate the time taken (in seconds)
  127.         time_taken[test] = ((double)(end_time - start_time)) / CLOCKS_PER_SEC;
  128.  
  129.         // Output the results
  130.         printf("Time taken to sort an array of size %d: %f seconds\n", n, time_taken[test]);
  131.  
  132.         // Free the dynamically allocated memory
  133.         free(arr);
  134.     }
  135.  
  136.     // Plot the graph using gnuplot
  137.     plotGraph(n_values, time_taken, num_tests);
  138.  
  139.     return 0;
  140. }
  141.  
Success #stdin #stdout #stderr 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Time taken to sort an array of size 5000: 0.000000 seconds
Time taken to sort an array of size 10000: 0.001050 seconds
Time taken to sort an array of size 15000: 0.001051 seconds
Time taken to sort an array of size 20000: 0.002855 seconds
Time taken to sort an array of size 25000: 0.002101 seconds
stderr
copy 
sh: 1: gnuplot: not found
https://ideone.com/Mak8A2
language:
C (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!