Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
Sorting Algorithms 1. Add a counter to the functions insertionSort and mergeSort that counts the number of comparisons that are made. Run two functions with arrays of various sizes. At what size does the difference in the number of comparisons between significant? How does this size that the orders of these algorithms predict? Compare your analysis with the actual running times and counter as a function of the input size n = 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 8192, 16384 and clock() function.) Use the below code to generate an array value for testing.            for (int i = 0; i < n; i++)             {                   //Create an unsorted array                   arr[i] = (double)(n - i);                               }

Sorting Algorithms 1. Add a counter to the functions insertionSort and mergeSort that counts the number of comparisons that are made. Run two functions with arrays of various sizes. At what size does the difference in the number of comparisons between significant? How does this size that the orders of these algorithms predict? Compare your analysis with the actual running times and counter as a function of the input size n = 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 8192, 16384 and clock() function.) Use the below code to generate an array value for testing.            for (int i = 0; i < n; i++)             {                   //Create an unsorted array                   arr[i] = (double)(n - i);                               }

Database System Concepts
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
See similar textbooks
icon
Related questions
Question
100%

Sorting Algorithms

1. Add a counter to the functions insertionSort and mergeSort that counts the number of comparisons that are made. Run two functions with arrays of various sizes. At what size does the difference in the number of comparisons between significant? How does this size that the orders of these algorithms predict? Compare your analysis with the actual running times and counter as a function of the input size n = 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 8192, 16384 <time.h> and clock() function.) Use the below code to generate an array value for testing.

 

         for (int i = 0; i < n; i++)

            {

                  //Create an unsorted array

                  arr[i] = (double)(n - i);

                 

            }

The table provided is designed to compare the performance of two sorting algorithms: Insertion Sort and Merge Sort. The table is divided into two main categories: Comparisons and Running Time for different input sizes (n). ### Table Structure: 1. **Input n:** Represents the size of the array to be sorted. Various sizes are given, ranging from 2 to 16,384. 2. **Comparisons:** - **Insertion Sort:** The number of comparisons made by the Insertion Sort algorithm. - **Merge Sort:** The number of comparisons made by the Merge Sort algorithm. 3. **Running Time:** - **Insertion Sort:** The time taken by the Insertion Sort algorithm to sort the array. - **Merge Sort:** The time taken by the Merge Sort algorithm to sort the array. ### Input Sizes: - 2 - 4 - 8 - 16 - 32 - 64 - 128 - 256 - 512 - 1024 - 2048 - 8192 - 16384 ### Note: The table is empty and requires empirical data from sorting operations to be filled in. This data would typically be collected by running the sorting algorithms on arrays of specified sizes and recording the number of comparisons and the time taken for each sort. The line of code provided suggests that the unsorted arrays for the experiments are initialized in descending order, which is often used to test the worst-case performance for some sorting algorithms.
Transcribed Image Text:The table provided is designed to compare the performance of two sorting algorithms: Insertion Sort and Merge Sort. The table is divided into two main categories: Comparisons and Running Time for different input sizes (n). ### Table Structure: 1. **Input n:** Represents the size of the array to be sorted. Various sizes are given, ranging from 2 to 16,384. 2. **Comparisons:** - **Insertion Sort:** The number of comparisons made by the Insertion Sort algorithm. - **Merge Sort:** The number of comparisons made by the Merge Sort algorithm. 3. **Running Time:** - **Insertion Sort:** The time taken by the Insertion Sort algorithm to sort the array. - **Merge Sort:** The time taken by the Merge Sort algorithm to sort the array. ### Input Sizes: - 2 - 4 - 8 - 16 - 32 - 64 - 128 - 256 - 512 - 1024 - 2048 - 8192 - 16384 ### Note: The table is empty and requires empirical data from sorting operations to be filled in. This data would typically be collected by running the sorting algorithms on arrays of specified sizes and recording the number of comparisons and the time taken for each sort. The line of code provided suggests that the unsorted arrays for the experiments are initialized in descending order, which is often used to test the worst-case performance for some sorting algorithms.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 4 steps with 6 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS