Reference no: EM13829410
Problem:
The insertion sort algorithm is stated below. Operation of insertion sort can be described as follows. The list at any moment is divided into two parts: sorted and unsorted. In each pass of the algorithm, the first element of the unsorted sub-list is moved to the sorted sub-list by inserting it at the appropriate place.
(i) Show how algorithm insertionSort operates by tracing it on the list 32, 15, 58, 7, 24, 30.
Fill in the following table.
|
i
|
j
|
tmp
|
j≥0 ? (true or false)
|
tmp<A[j]?
(true or false)
|
A[0]
|
A[1]
|
A[2]
|
A[3]
|
A[4]
|
A[5]
|
|
....
|
|
|
|
|
values of A[j] at the end of each iteration
|
(ii) Give an example of an array that makes the insertion sort exhibit its worst behavior.
(iii) Count how many comparisons tmp < A[j] are done by the algorithm in the worst case (for an arbitrary n) and state its complexity in terms of Big-Oh.
ALGORITHM insertionSort(A[0..n - 1])
//The algorithm sorts a given array by insertion sort
//Input: an array A[0..n - 1] of n numbers
//Output: array A[0..n - 1] sorted in ascending order
for i ← 1 to n - 1 do
tmp ← A[i]
j ← i - 1
while (j≥0 and tmp < A[j]) do
A[j + 1] ← A[j]
j ← j - 1
A[j + 1] ← tmp
output A[0..n - 1]
Additional Information:
This question is from Computer Science as well as it explains about the algorithm insertionSort.
Total Word Limit: 251 Words
|
What is current value of share of simtek stock to investor
: Simtek currently pays a $2.50 dividend (D0) per share. Next year’s dividend is expected to be $3 per share. After next year, dividends are expected to increase at a 9 percent annual rate for 3 years and a 6 percent annual rate thereafter. What is the..
|
|
Algorithm for taking out heavier marbles
: You have eight marbles and a two-pan balance. All the marbles weigh the same, except for one, which is heavier than all the others. The marbles are otherwise indistinguishable.
|
|
Identify a few core values for effective facilitators
: Identify a few "core values" for effective facilitators. which ones are "most" important to you and your organization
|
|
Scenario analysis: fmp
: Scenario Analysis: FMP
|
|
Explains about the algorithm insertionsort
: The insertion sort algorithm is stated below. Operation of insertion sort can be described as follows. The list at any moment is divided into two parts: sorted and unsorted. In each pass of the algorithm, the first element of the unsorted sub-list..
|
|
When should the organisers recognize revenue
: Discuss the importance of Cost of Goods Sold(COGS) in this case - Let us say that the signatories will get a fixed fee for the effort, when would the organisers recognize the expense?
|
|
What is the current value of share of stock to investor
: General Cereal common stock dividends have been growing at an annual rate of 7 percent per year over the past 10 years. Current dividends are $1.70 per share. What is the current value of a share of this stock to an investor who requires a 12 percent..
|
|
What is the effect on pretax earnings
: Danville Bottlers is a wholesale beverage company. Danville uses the FIFO inventory method to determine the cost of its ending inventory. Ending inventory quantities are determined by a physical count. For the fiscal year-end June 30, 2011, ending in..
|
|
Description of an experience in which you were a facilitator
: Write a brief description of an experience in which "you" were a facilitator. Consider whether it was a positive/negative experience and why-give examples
|