We would like to take into account memory hierarchies when analyzing Insertion S

Question

We would like to take into account memory hierarchies when analyzing Insertion Sort. Assume that your machine takes time f(i) to access memory location i, for some nondecreasing function f(i). Most of the time, when doing algorithmic analysis, we assume f(i) is a constant. In reality it is a slow growing function. For this problem, to keep things simple, we will assume that f(i) grows linearly, which is pretty drastic. Also, to keep things simple, we will only count the time for comparisons. To compare two elements in locations i and j takes time i + j. We modify Insertion Sort to take the memory access cost into account. The array to be sorted is in A[1, . . . , n]. To insert the ith element of A into its proper location, put it into A[0], where it is cheap to access. Then compare the elements of A to this value starting at location 1 and going up, rather starting at location i 1 and going down. (Note that if we were going to be really efficient, we could move an element into location 1 before comparing it the element being inserted, so the cost would be just 0 + 1 = 1. This is not in the spirit of the problem. If you must do this, then, to be fair, you should also keep track of the cost of moving items.) Problem 1. Write the pseudo-code for this modified version of Insertion Sort. Do not use a sentinel. Problem 2. What input gives the best-case cost? Problem 3. Analyze the exact best-case cost. Show your work. Problem 4. What input gives the worst-case cost? Problem 5. Analyze the exact worst-case cost. Show your work. Problem 6. Analyze the average-case cost for n = 3. Show your work. Problem 7. Challenge problem, will not be graded. Analyze the average-case cost (for general n)?

Explanation / Answer

1)

/// sort elementsfrom 1 to n

for(i=1;i<n+1;i++)
{
// picking ith element and placing it in zero
a[0] = a[i];
// compare zero with 1 to i-1 and find its position
int pos = 1;
while(a[pos]<a[0])
pos++;
// put this element at pos and move a[pos] to a[i-1] one position ahead
for(j=pos;j<i;j++)
{
a[j+1] = a[j];
}
a[pos] = a[0];
  
}
2) Since we are only considering the memory cost best case would be when the elements are given in decreasing ordrer, here in every iteration you compare a[0] with a[1] realize a[0] is smaller and move a[1]....a[i-1] elements one step right and then put a[0] at a[1]
3)T(base case) = n*(0+1) = n i.e O(n) since in every iteration you just compare a[0] and a[1] cost taken is 1 unit
4)If the array is already sorted then in every iteration you comapre a[0] with a[1]....a[i-1] i.e all possible comparitions. This is the worst case.
5) in ith iteration cost taken would be 0+1 + 0+2... + 0+i-1 i,e i(i-1)/2
total cost = 0 + 1 + ....n*(n-1)/2 = 1/2*(n*(n+1)*(2n+1)/6 - n(n+1)/2 ) = (n*n*n - n)/6
T(n) = O(n^3)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.