Question

1. Implement functions for insertion sort, quicksort, heapsort and merge sort that input an array of integers and sort it in-place.
2. Write a program that generates random integer arrays (hint: use seed appropriately to avoid generating same sequences) of lengths 10, 100, 1000, 10,000, 100,000, 1000,000, and then sorts each using each of the sorting functions from (a), and measures the time in nanoseconds. The program will repeat this process 30 times and will compute the average execution time for each (arraysize,sorting-function) pair, over these 30 iterations. Finally, the program will output all these numbers in a readable format, e.g., as a table, in the PDF file.
3. Are your computed numbers reasonable given your knowledge of the asymptotic complexity of each sorting algorithm? Explain. Put your answer in the PDF file.

Note:

• Complete all the functions for a and b in exercise_3.cpp, then submit this cpp file.

CODE:

#include <chrono>

#include <cstdio>

/*

* Implement the 4 in-place sort functions for exercise 3.a.

*/

void insertion_sort(int array[], size_t size) {

  // Implement here

}

void quick_sort(int array[], size_t size) {

  // Implement here

}

void heap_sort(int array[], size_t size) {

  // Implement here

}

void merge_sort(int array[], size_t size) {

  // Implement here

}

/*

* Generate random integers for exercise 3.b

*/

int *random_ints(size_t size) {

  int *numbers = new int[size];

  // Generate random numbers here

  return numbers;

}

/* Here is an example to measure a function's running time in nanoseconds

long long time_example() {

  auto start_time = std::chrono::high_resolution_clock::now();

  // Run function to measure the time in nanoseconds

  auto end_time = std::chrono::high_resolution_clock::now();

  auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(

      end_time - start_time);

  return elapsed.count();

}

*/

Answer 1

Solution :

Following are the commented C++ code for both the part :

3.a)

#include <chrono>
#include <cstdio>
#include <time.h>
/*

* Implement the 4 in-place sort functions for exercise 3.a.

*/

void insertion_sort(int array[], size_t size) {

  // Implement here
  
   for (int i = 1; i < size; i++) {
        int elem = array[i];
        int j    = i - 1;

        // Compare elem with the elements before it, and swap if necessary. 
        // Swapping is done by repeatedly moving the elements one unit back.
        while (j >= 0 and array[j] > elem) {
            array[j + 1] = array[j]; 
            j--;
        }
        array[j + 1] = elem;
    }

}
int partition (int arr[], int low, int high) 
{ 
    int pivot = arr[high];    // pivot 
    int i = (low - 1);  // Index of smaller element 
  
    for (int j = low; j <= high- 1; j++) 
    { 
        // If current element is smaller than or 
        // equal to pivot 
        if (arr[j] <= pivot) 
        { 
            i++;    // increment index of smaller element 
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[i + 1], &arr[high]); 
    return (i + 1); 
} 
void quickSorthelp(int arr[], int low, int high) 
{ 
    if (low < high) 
    { 
        /* pi is partitioning index, arr[p] is now 
           at right place */
        int p = partition(arr, low, high); 
  
        // Separately sort elements before 
        // partition and after partition 
        quickSorthelp(arr, low, p - 1); 
        quickSorthelp(arr, p + 1, high); 
    } 
} 
void quick_sort(int array[], size_t size) {

  // Implement here
    quickSorthelp(array,0,size-1);  

}

void heapify(int arr[], int n, int i) 
{ 
    int largest = i; // Initialize largest as root 
    int l = 2 * i + 1; // left = 2*i + 1 
    int r = 2 * i + 2; // right = 2*i + 2 
  
    // If left child is larger than root 
    if (l < n && arr[l] > arr[largest]) 
        largest = l; 
  
    // If right child is larger than largest so far 
    if (r < n && arr[r] > arr[largest]) 
        largest = r; 
  
    // If largest is not root 
    if (largest != i) { 
        swap(arr[i], arr[largest]); 
  
        // Recursively heapify the affected sub-tree 
        heapify(arr, n, largest); 
    } 
} 
  
void heap_sort(int array[], size_t size) {
    
  // Implement here
  // Build heap (rearrange array) 
    for (int i = size / 2 - 1; i >= 0; i--) 
        heapify(array, size, i); 
  
    // One by one extract an element from heap 
    for (int i = size - 1; i >= 0; i--) { 
        // Move current root to end 
        swap(array[0], array[i]); 
  
        // call max heapify on the reduced heap 
        heapify(array, i, 0); 
    } 
  

}

void merge(int arr[], int l, int m, int r)
{
    int n1 = m - l + 1;
    int n2 = r - m;
 
    // Create temp arrays 
    int L[n1], R[n2];
 
    // Copy data to temp arrays L[] and R[] 
    for(int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for(int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];
 
    // Merge the temp arrays back into arr[l..r]
     
    // Initial index of first subarray
    int i = 0; 
     
    // Initial index of second subarray
    int j = 0; 
     
    // Initial index of merged subarray
    int k = l;
     
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j]) 
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    // Copy the remaining elements of
    // L[], if there are any 
    while (i < n1) 
    {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    // Copy the remaining elements of
    // R[], if there are any 
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}
 
// l is for left index and r is 
// right index of the sub-array
// of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
    if (l < r)
    {
         
        // Same as (l+r)/2, but avoids 
        // overflow for large l and h
        int m = l + (r - l) / 2;
 
        // Sort first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
 
        merge(arr, l, m, r);
    }
}
void merge_sort(int array[], size_t size) {

  mergeSort(array,0,size-1);

}

}

3.b)

#include <chrono>
#include <cstdio>
#include<ctime>

/*

* Generate random integers for exercise 3.b

*/
int *random_ints(size_t size) {

  int *numbers = new int[size];

  //seeding
  srand(time(0));
  // Generate random numbers here
  for(int i=0;i<size;i++)
  numbers[i]=rand()%(INT_MAX);

  return numbers;

}

void test()
{
    //for insertion sort
    int array1[10]=random_ints(10);
    auto start_time = std::chrono::high_resolution_clock::now();
    insertion_sort(array1,10);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    int array2[100]=random_ints(100);
    auto start_time = std::chrono::high_resolution_clock::now();
    insertion_sort(array2,100);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    int array3[1000]=random_ints(1000);
    auto start_time = std::chrono::high_resolution_clock::now();
    insertion_sort(array3,1000);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    int array4[10000]=random_ints(10000);
    auto start_time = std::chrono::high_resolution_clock::now();
    insertion_sort(array4,10000);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    //for quick sort
    int array5[10]=random_ints(10);
    auto start_time = std::chrono::high_resolution_clock::now();
    quick_sort(array5,10);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    int array6[100]=random_ints(100);
    auto start_time = std::chrono::high_resolution_clock::now();
    quick_sort(array6,100);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    int array7[1000]=random_ints(1000);
    auto start_time = std::chrono::high_resolution_clock::now();
    quick_sort(array7,1000);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    int array8[10000]=random_ints(10000);
    auto start_time = std::chrono::high_resolution_clock::now();
    quick_sort(array8,10000);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    //for heap sort
    int array9[10]=random_ints(10);
    auto start_time = std::chrono::high_resolution_clock::now();
    heap_sort(array9,10);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    int array10[100]=random_ints(100);
    auto start_time = std::chrono::high_resolution_clock::now();
    heap_sort(array10,100);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    int array11[1000]=random_ints(1000);
    auto start_time = std::chrono::high_resolution_clock::now();
    heap_sort(array11,1000);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    int array12[10000]=random_ints(10000);
    auto start_time = std::chrono::high_resolution_clock::now();
    heap_sort(array12,10000);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();

    //for merge sort    
    int array13[10]=random_ints(10);
    auto start_time = std::chrono::high_resolution_clock::now();
    merge_sort(array13,10);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    int array14[100]=random_ints(100);
    auto start_time = std::chrono::high_resolution_clock::now();
    merge_sort(array14,100);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    int array15[1000]=random_ints(1000);
    auto start_time = std::chrono::high_resolution_clock::now();
    merge_sort(array15,1000);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    int array16[10000]=random_ints(10000);
    auto start_time = std::chrono::high_resolution_clock::now();
    merge_sort(array16,10000);
    auto end_time = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(
        end_time - start_time);
    cout<<"\n"<< elapsed.count();
    
    
}