Question

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

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

21, 16, 77, 3, 8, and 11.No explanation/proof required.

Homework Answers

Answer #1

The simplest worst case input is an array sorted in reverse order. The set of all worst case inputs consists of all arrays where each element is the smallest or second-smallest of the elements before it. In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element. This gives insertion sort a quadratic running time (i.e., O(n2)).

So the worst case input sequence would be :

(77, 21, 16, 11, 8, 3)

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Selection-Sort( A[1..n] ) 1 2 3 4 5 6 7 8 9 10 // INPUT: A[1..n],...
Selection-Sort( A[1..n] ) 1 2 3 4 5 6 7 8 9 10 // INPUT: A[1..n], an array of any n numbers in unknown order integer i, j, m fori=1ton−1 do swap A[i] ↔ A[m] // OUTPUT: A[1..n], its numbers now sorted in non-decreasing order m=i for j = i to n do if A[j] < A[m] then m = j Give a proof that this algorithm sorts its input as claimed.
I have the following question please: Consider the following sequence of numbers 8, 1, 11, 4,...
I have the following question please: Consider the following sequence of numbers 8, 1, 11, 4, 2, 9, 10, 5, 3, 12, 6, 7 Sort the list using quick sort with the middle element as pivot. Show the state of the list after each call to the partition procedure. You are not required to write code for this question. You need to trace through the different sorting algorithms using the given list Please could you provide me with a complete...
Java please. Given a sequence of unsorted numbers, determine how badly out of order they are....
Java please. Given a sequence of unsorted numbers, determine how badly out of order they are. Write a program that, for any given sequence of unique natural numbers, will compute the 'distance' between that original ordering and the same set of numbers sorted in ascending order. The distance should be computed by calculating how far displaced each number is in the original ordering from its correct location in the sorted list and summing those results. For instance, given the list...
in C++ Please and thanks Here is a list of 6 numbers. Use the selection sort...
in C++ Please and thanks Here is a list of 6 numbers. Use the selection sort algorithm to sort this list. Fill in this table with each iteration of the loop in the selection sort algorithm. Mark the place from which you are looking for the 'next smallest element'. In this display, the upper numbers are the indices, the lower numbers are in the corresponding positions. Use the several rows provided to show the sequence of steps. 0 1 2...
Consider the following sequence of numbers 8, 1, 11, 4, 2, 9, 10, 5, 3, 12,...
Consider the following sequence of numbers 8, 1, 11, 4, 2, 9, 10, 5, 3, 12, 6, 7 c) Sort the list using quick sort with the middle element as pivot. Show the state of the list after each call to the partition procedure. You are not required to write code for this question. You need to trace through the different sorting algorithms using the given list. Please could I get an answer to the above question through using 9...
An online/anytime sorting algorithm is one that reads its input numbers one at a time, and...
An online/anytime sorting algorithm is one that reads its input numbers one at a time, and maintains a sorted array of all the inputs it has seen so far, so that if it is interrupted at any time, it will still output the correct answer for the inputs that it has processed. Not all sorting algorithms are amenable to modification to make them anytime. But one sorting algorithm, Bubble Sort, is easy to so modify. First, understand the ascending order...
CAN YOU PLEASE ANSWER ALL THESE QUSTIONS 1.In Merge sort, how many additional recursive partitioning levels...
CAN YOU PLEASE ANSWER ALL THESE QUSTIONS 1.In Merge sort, how many additional recursive partitioning levels are required for a list of 64 elements compared to a list of 8 elements? a. 3 b. 9 c. 8 d. 6 2. Which function best represents the number of operations in the worst-case for the following code fragment? for (i = 0; i < N; ++i) {    if (numbers[i] % 2 == 1)       factor = 2.5 } a. f(N) = 6N2 b....
Pinky and The Brain are great friends. They like to play games with numbers. This time,...
Pinky and The Brain are great friends. They like to play games with numbers. This time, Pinky has given The Brain a list of numbers and given him the task of determining if it is possible to choose a subset of them such that they sum is equal to another given number. Build an algorithm using dynamic programming to help The Brain with his problem. INPUT The first line corresponds to N, the amount of numbers given by Pinky The...
Month 1 2 3 4 5 6 7 Value 24 15 21 13 19 21 16...
Month 1 2 3 4 5 6 7 Value 24 15 21 13 19 21 16 a) Develop a three-month moving average for this time series. Compute MSE and a forecast for month 8. If required, round your answers to two decimal places. Do not round intermediate calculation. MSE:_______ The forecast for month 8________ b) Use α = 0.2 to compute the exponential smoothing values for the time series. Compute MSE and a forecast for month 8. If required, round...
These numbers have been drawn from a uniform distribution with range 1-40. 4, 6, 16, 12,...
These numbers have been drawn from a uniform distribution with range 1-40. 4, 6, 16, 12, 23, 19, 16 26, 14, 12, 12, 10, 3, 26, 35, 8, 30, 11, 14, 34, 37, 16, 36, 30, 18, 39, 24, 18, 39, 5, 12, 28, 4, 12, 34, 16, 35, 27, 15, 1 Test the sample for randomness using: a Kolmogorov—Smirnov test.
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT