Explanation Comparison sort is type of sorting algorithm that is used to sort elements in particular orders, it determines which of the two elements should be place first in the final sorted list, there are many comparison sorts to sort elements of a list, some of those are selection sort,insertion sort, merge sort and quick sort. For selection sort, number of comparisons for n elements are n 2 − 2 n + 1 . Insertion sort and quick sort are same for number of comparisons for n elements, quick sort is different only in worst case scenario. So, the number of comparisons for both of these is n ( n − 1 ) 2 For merge sort the number of comparisons for n elements are n log 2 n . We will start sorting for n = 100 Selection sort; n 2 − 2 n + 1 = 100 2 − 2 × 100 + 1 = 9801 Insertion and quick sort; n ( n − 1 ) 2 = 100 ( 100 − 1 ) 2 = 4950 Merge sort; n log 2 n = 100 log 2 100 = 100 × 6

Discrete Mathematics and Its Applications ( 8th International Edition ) ISBN:9781260091991

8th Edition

ISBN: 9781259676512

Author: Kenneth H Rosen

Publisher: McGraw-Hill Education

See similar textbooks

Concept explainers

Permutations and Combinations

If there are 5 dishes, they can be relished in any order at a time. In permutation, it should be in a particular order. In combination, the order does not matter. Take 3 letters a, b, and c. The possible ways of pairing any two letters are ab, bc, ac, ba…

Counting Theory

The fundamental counting principle is a rule that is used to count the total number of possible outcomes in a given situation.

Videos

Question

Chapter 11, Problem 5CAE

To determine

To compare the number of comparisons that are needed to sort lists of n elements, for n=100,1000 and 10000 from the set of positive integers less than 1,000,000 if the elements are randomly selected positive integers using the selection sort, the insertion sort, merge sort and the quick sort.

Expert Solution & Answer

Want to see the full answer?

Check out a sample textbook solution

See solution

Chapter 11, Problem 4CAE

Chapter 11, Problem 6CAE

Students have asked these similar questions

How many ordered lists are there of seven items chosen from twelve?

A doughnut shop has a special on its mix n match selection, which allows customers to select three doughnuts from among the following varieties: plain, maple, frosted, chocolate, glazed, and jelly. How many different mix n match selections are possible?

In a “Pick-4” game, a player wins a prize for matching a 4-digit number from 0000 to 9999 with the number randomly selected during the drawing. How many 4-digit numbers can a player choose? Assume that a number can start with a zero or zeros such as 0001

Chapter 11 Solutions

Discrete Mathematics and Its Applications ( 8th International Edition ) ISBN:9781260091991

Ch. 11.1 - Prob. 1E Ch. 11.1 - Vhich of these graphs are trees?Ch. 11.1 - Prob. 3E Ch. 11.1 - Prob. 4E Ch. 11.1 - Prob. 5E Ch. 11.1 - Prob. 6E Ch. 11.1 - Prob. 7E Ch. 11.1 - Prob. 8E Ch. 11.1 - Prob. 9E Ch. 11.1 - Prob. 10E

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, subject and related others by exploring similar questions and additional content below.

Solution Summary: The author compares the number of comparisons that are needed to sort lists of n elements from the set of positive integers less than 1,000,000.

Concept explainers

Videos

To compare the number of comparisons that are needed to sort lists of n elements, for n=100,1000 and 10000 from the set of positive integers less than 1,000,000 if the elements are randomly selected positive integers using the selection sort, the insertion sort, merge sort and the quick sort.

Want to see the full answer?

Chapter 11 Solutions