Give a worst-case input sequence of 6 numbers for Insertion Sort, containing the numbers 68, 12,...

Give a worst-case input sequence of 6 numbers for Insertion Sort, containing the numbers

68, 12, 43, 13, 58, and 21.

No explanation/proof required.

Solutions

Expert Solution

The answer for the above mentioned question is explained below ::

Worst case input sequence depends on the , style of implementation of the insertion sort algorithm .

While inserting new element into the array if we check the array position for the new element from the left side of the already sorted part of the array then the worst input sequence is

12,13,21,43,58,68

In the implementation of insertion sort algorithm , while inserting the new element if we check the array position for the new element from the already sorted part of the array from right side , then the worst case input sequence is 68,58,43,21,13,12

venereology answered 2 hours ago

Next > < Previous

Related Solutions

Sort the following set of numbers using bubble sort, insertion sort, and selection sort. Show the...

Sort the following set of numbers using bubble sort, insertion sort, and selection sort. Show the process step-by-step, and find the time complexity in Big-O notation for each method. For sorting, use ascending order. 49, 7, 60, 44, 18, 105

give a good explanation of Bubble sort, Insertion sort, Selection sort, and Quicksort.

(code in C++ language) [Code Bubble sort, Insertion sort Create a Big array with random numbers....

(code in C++ language) [Code Bubble sort, Insertion sort Create a Big array with random numbers. Record the time. Run Bubble Check time (compute the processing time) do it 100 times (random numbers) Take the average Insertion: Compare] (some explanations please)

python: ask the user to input a sequence of positive numbers. the end of the sequence...

python: ask the user to input a sequence of positive numbers. the end of the sequence is determined when the user enters a negative number. print out the maximum number from the sequence. output: keep entering positive numbers. to quit, input a negative number. enter a number: 67 enter a number: 5 enter a number: 8 enter a number: -3 largest number entered: 67 (note: i do not want to ask the user how many numbers they will input)

Please use C++ 1. A Sequence of numbers and a sum is given as input. List...

Please use C++ 1. A Sequence of numbers and a sum is given as input. List all combinations of numbers that can add upto the given Sum. User input:- Enter numbers: - 1, 3,7,9,11 Enter a sum :- 20 Output: 11+9 = 20 1+3+7+9 = 20 2. Print absolute prime numbers between a given range:- Enter Range - 2,99 For eg Prime numbers are:- Prime numbers ==> 2,3,5,7,11,13,17,19,23 Absolute Prime numbers ==> 2,3,5,7,11,23 3. Write an encoder and decoder program,...

Develop an algorithm for INSERTION SORT. Give the pseudo-code version. Convert your pseudo-code into a Java...

Develop an algorithm for INSERTION SORT. Give the pseudo-code version. Convert your pseudo-code into a Java program.

Using the sequence below give an example of an insertion, deletion, SNP, inversion, and translocation. 3’-ATTCGGCCAGTTAGCCGATG-5’

Exercise 6. Test the claim that the following sequence of numbers is not random at α...

Exercise 6. Test the claim that the following sequence of numbers is not random at α = 0.025 using the rank test for randomness. 250 221 205 225 215 216 216 236 246 200 207 245 201 229 248

What is the 11th term of the geometric sequence − 1.5, − 3, − 6, − 12, … ?

12. The reciprocal search problem is: input: a list L of n floating point numbers output:...

12. The reciprocal search problem is: input: a list L of n floating point numbers output: two elements a, b L such that a*b=1, or None if no such a, b exist Design an algorithm for this problem using the greedy pattern. Write pseudocode for your algorithm below. If you write multiple drafts, circle your final draft. Hint: I expect your algorithm to be relatively simple and to have time complexity O(n2). 13. Perform a chronological step count to derive...

Subjects