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: 9781264309689

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

Compute the number of different ways a national high school sports competition featuring the top 128 teams in the nation could award winners for 1st through 4th places.

Five cards are dealt off of a standard 52-card deck and lined up in a row. How many such line-ups are there that have atleast one red card.

Suppose that 989 tennis players want to play an elimination tournament. That means: they pair up, at random, for each round; if the number of players before the round begins is odd, one of them, chosen at random, sits out that round. The winners of each round, and the odd one who sat it out (if there was an odd one), play in the next round, till, finally, there is only one winner, the champion. What is the total number of matches to be played altogether, in all the rounds of the tournament?

Chapter 11 Solutions

DISCRETE MATHEMATICS LOOSELEAF

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