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.

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 months ago

Using the worst case scenario for a recursive insertion sort on an array of 5 elements...

Using the worst case scenario for a recursive insertion sort on an array of 5 elements {5, 4, 3, 2, 1} Determine a formula that counts the numbers of nodes in that recursion tree. What is the Big O for execution time. Determine a formula that expresses the height of the recursion tree. What is the Big O for memory?

6. The worst case scenario in the quick sort occurs when the array is partitioned to...

6. The worst case scenario in the quick sort occurs when the array is partitioned to two equal sized subarray every time that a recursive call takes place. True False 7.Suppose that we want to sort an array of n elements, where each element is a string of at most 1000 characters. What is the time requirement for applying radix sort to sort this array? O(n2) O(1000n) O(l000logn) O(nlogn) 8.Suppose we want to sort the following array of integers using...

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.

1. Insertion sort for 12, 2, 3, 21, 11, 10,8 2. Bubble sort for 12, 2,...

1. Insertion sort for 12, 2, 3, 21, 11, 10,8 2. Bubble sort for 12, 2, 3, 21, 11, 10,8 3. selection sort for 12, 2, 3, 21, 11, 10,8 analysis of algorithm

(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)

1a .Write a program that perform insertion sort (ascending order) on an input array and print...

1a .Write a program that perform insertion sort (ascending order) on an input array and print the total number of comparisons that have been made. You can implement by using any programming languages such as C/C++. For example, in the case of array B = [ 30 , 10 , 20 , 40 ], there are 4 needed comparisons to perform insertion sort (30 vs 10, 20 vs 30, 20 vs 10, and 40 vs 30). 1b. Write a program...

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.

Question