Construct a permutation of the ten distinct elements (i.e. the digits 0,1,2,3,4,5,6,7,8,9) that is as bad...

Construct a permutation of the ten distinct elements (i.e. the digits 0,1,2,3,4,5,6,7,8,9) that is as bad as possible for quicksort using median-of-three partitioning. Please write out what the permutation is and describe how you found what it is.

Expert Solution

In case of quicksort using median-of-three partitioning, the median of first , last and middle index element is selected as pivot with intention to avoid the worst case time complexity of O(n²) happens in traditional quick-sort when the array is already sorted and pivot element is either the first index or the last index.

Consider the permutation 1,9,3,4,0,5,6,7,8,2. Here the first indexed element is 1, last indexed element is 2, middle indexed element( index 5) is 0. Hence the median of 0,1,2 will be 1 and it will partition the array as

0 and 9,3,4,5,6,7,8,2 so that one sub array is of size 1 and another in size 8 which is worst possible partitioning in quicksort using median-of-three partitioning. Note that because we are selecting pivot as median of three elements, hence there will be atleast one element less than pivot and one element greater than pivot and hence both left and right subarray will have at least 1 element in all cases.

Hence the permutation 1,9,3,4,0,5,6,7,8,2 is worst possible permutation.

Please comment for any clarification.

venereology answered 2 weeks ago

Show that there are only two distinct groups with four elements, as follows. Call the elements...

Show that there are only two distinct groups with four elements, as follows. Call the elements of the group e, a. b,c. Let a denote a nonidentity element whose square is the identity. The row and column labeled by e are known. Show that the row labeled by a is determined by the requirement that each group element must appear exactly once in each row and column; similarly, the column labeled by a is determined. There are now four table...

The Bad (i.e., Opportunistic) Side of Earnings Management

A license plate in a certain state consists of 4 digits, not necessarily distinct, and 3...

A license plate in a certain state consists of 4 digits, not necessarily distinct, and 3 letters, also not necessarily distinct. (a) How many distinct license plates are possible if no restriction? (b) How many distinct license plates are possible if it must begin and terminate by a digit? (c) How many distinct license plates are possible if it must begin and terminate by a letter? (d) How many distinct license plates are possible if the three letters must appear...

in java Write a program that reads in ten numbers and displays the number of distinct...

in java Write a program that reads in ten numbers and displays the number of distinct numbers and the distinct numbers separated by exactly one space (i.e., if a number appears multiple times, it is displayed only once). (Hint: Read a number and store it to an array if it is new. If the number is already in the array, ignore it.) After the input, the array contains the distinct numbers. Here is the sample run of the program: Enter...

What is the probability that a randomly chosen four-digit integer has distinct digits and is odd?

The following algorithm returns true if the n items in an array are all distinct, i.e.,...

The following algorithm returns true if the n items in an array are all distinct, i.e., if no two items are equal to each other, otherwise it returns false. 1 ALGORITHM UniqueElements(A[1..n]) 2 // Determine whether all the elements in an array are distinct 3 // Input: Array A[1..n] 4 // Output: “true” if all elements of A are distinct, “false” otherwise 5 for i ← 1 to n – 1 do 6 for j ← i + 1 to...

Imagine a new book that is to be released. Construct the attributes (i.e., the value of...

Imagine a new book that is to be released. Construct the attributes (i.e., the value of independent variables) of this, and estimate the sales rank of it when it is sold on Amazon.com

Think about the different elements of benchmarking and auditing that make these two disciplines distinct from...

Think about the different elements of benchmarking and auditing that make these two disciplines distinct from each other. Discuss why an employee invited to participate in each of these kinds of activities might have a more favorable perspective of one over the other. What differences might drive such perception differences and what might a quality engineer do to alleviate some of the concerns raised by the more negative perceptions?

How many different positive integers less than 1000 have distinct digits and are even? My attempt:...

How many different positive integers less than 1000 have distinct digits and are even? My attempt: since 1 digit numbers have the repeating 0 digit i started with 2 digit numbers. xxx= First digit: can only be 0 Second digit: can be any of 9 digits Third digit: can't be 0 or the digit used in the tens column so one of 4 numbers. 1*9*4= 36 ways so 1 * 9 * 4= 36 ways Now for the 3 digit...

Marketers know that both the social elements of the service encounter (i.e., the employee and the...

Marketers know that both the social elements of the service encounter (i.e., the employee and the customer) and the physical elements, including the servicescape, are important to a positive service experience. To measure service quality, marketers use the SERVQUAL scale, which measures five (5) dimensions of service quality. List the five dimensions of service quality. Briefly explain each of the five dimensions of service quality. Gap analysis is a related metric. What is gap analysis – what does it measure,...

Question