Question

Implement functions for insertion sort, quicksort, heapsort and merge sort that input an array of integers...

  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();

}

*/

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

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();
    
    
}
0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Java : Modify the selection sort algorithm to sort an array of integers in descending order....
Java : Modify the selection sort algorithm to sort an array of integers in descending order. describe how the skills you have gained could be applied in the field. Please don't use an already answered solution from chegg. I've unfortunately had that happen at many occasion ....... ........ sec01/SelectionSortDemo.java import java.util.Arrays; /** This program demonstrates the selection sort algorithm by sorting an array that is filled with random numbers. */ public class SelectionSortDemo { public static void main(String[] args) {...
*****C++ program***** Please implement the following, comments throughout code to explain, and provide screenshots of output...
*****C++ program***** Please implement the following, comments throughout code to explain, and provide screenshots of output for proof. Write a program for sorting a list of integers in ascending order using the bubble sort algorithm. Implement the following functions: Implement a function called readData int readData( int *arr) arr is a pointer for storing the integers. The function returns the number of integers. The function readData reads the list of integers from a file call data.txt into the array arr....
***C++ CODING*** Write a program for sorting a list of integers in ascending order using the...
***C++ CODING*** Write a program for sorting a list of integers in ascending order using the bubble sort algorithm. Requirements Implement the following functions: Implement a function called readData int *readData( )   The function returns a pointer that points to the locations with integers reading from the file data.txt. arr is a pointer for storing the integers. The function returns the number of integers. The function readData reads the list of integers from a file call data.txt into the array...
DIRECTIONS: IMPLEMENT QuickSort and MergeSort. You have been provided: 1. Functions to perform Merge (for MergeSort)...
DIRECTIONS: IMPLEMENT QuickSort and MergeSort. You have been provided: 1. Functions to perform Merge (for MergeSort) and Partition (for QuickSort). 2. In class we discussed the body of the recursive functions, the "brakes" needed to stop the recursion. You are expected to develop 2 RECURSIVE programs: 1. Complete the bodies of the sort functions, MergeSort and QuickSort. 2. Complate the main that tests each function. - program should not read inputs - stock the program with multiple arrays (test cases)...
in C++ Need a heap-sort function #include <iostream> #include <stdlib.h> #include <string> using namespace std; void...
in C++ Need a heap-sort function #include <iostream> #include <stdlib.h> #include <string> using namespace std; void MyFunc ( int *array ) { // Your code here ----------------- } int main(int argc,char **argv) { int *Sequence; int arraySize; // Get the size of the sequence cin >> arraySize; // Allocate enough memory to store "arraySize" integers Sequence = new int[arraySize];    // Read in the sequence for ( int i=0; i<arraySize; i++ ) cin >> Sequence[i]; // Run your algorithms to...
Quick sort func in C++ #include <iostream> #include <stdlib.h> #include <string> using namespace std; void MyFunc...
Quick sort func in C++ #include <iostream> #include <stdlib.h> #include <string> using namespace std; void MyFunc ( int *array ) { // Code here } int main(int argc,char **argv) { int *Sequence; int arraySize; // Get the size of the sequence cin >> arraySize; // Allocate enough memory to store "arraySize" integers Sequence = new int[arraySize];    // Read in the sequence for ( int i=0; i<arraySize; i++ ) cin >> Sequence[i]; // Run your algorithms to manipulate the elements...
Write a program to implement bubble sort, insertion sort, selection sort, merge sort and quick sort...
Write a program to implement bubble sort, insertion sort, selection sort, merge sort and quick sort (pivot = first index) algorithms. Compute the CPU processing time for all the algorithms for varying input sizes as follows: N = 102, 103, 104, 105, and 106 Use a random number generator to generate the inputs. Obtain the inputs from the following input ranges: 1- 103, 1 - 106, 1 – 109, 1 - 1012 Write down your results as a table (with...
1.) Generate an array of 10 random numbers between 1 - 100 2.) Copy the array...
1.) Generate an array of 10 random numbers between 1 - 100 2.) Copy the array to a temp array 3.) Call each of the methods to sort (bubble, selection, insertion, quick, merge), passing it the array 4.) In-between the calls, you are going to refresh the array to the original numbers. 5.) Inside of each sorting method, you are going to obtain the nanoseconds time, before and after the method Subtract the before time from the after time to...
You are asked to implement a C++ class to model a sorted array of unsigned integers....
You are asked to implement a C++ class to model a sorted array of unsigned integers. The class is to be used in an embedded application that cannot assume the presence of the STL. The array has to be dynamically allocated in such a way that allows programmers using it to specify the required size. Your class should should: (1) provide the appropriate constructors and destructor; (2) provide methods for updating, and showing numbers in/to the array (e.g., to be...
/************************************************************************************* Function Prototypes *************************************************************************************/ int ScanArray(char *fname, int myArray[], int nSize); void Ge
/************************************************************************************* Function Prototypes *************************************************************************************/ int ScanArray(char *fname, int myArray[], int nSize); void GenerateFromArray(void); /************************************************************************************/ /************************************************************************************/ int main(void) { /* This is the main() program. It should call the functions ScanArray() and GenerateFromArray() */ GenerateFromArray(); system("pause"); return 0; } /*************************************************************************************** Define this function to scan the elements of an array from the given data file "ArrayInp.dat". If the input file is not found, or contains invalid data, the function should return a 0 and print an error message. If the input...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT