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

8th Edition

ISBN: 9781260521337

Author: ROSEN

Publisher: MCG

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

Please help on both Part b) and c) below Thanks

find the zeros of the function algebraically: f(x) = 9x2 - 3x - 2

a small pond contains eight catfish and six bluegill. If seven fish are caught at random, what is the probability that exactly five catfish have been caught?

Chapter 11 Solutions

DISCRETE MATHEMATICS+ITS APPL. (LL)-W/A

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