Suppose a large array is maintained with the following policy. The array is init

Question

Suppose a large array is maintained with the following policy. The array is initially sorted. When new elements are added, they are inserted at the end of the array and counted. Whenever the number of new elements reaches 10, the array is resorted and the counter is clear. What strategy would be good to use for resorting the array? More specifically, assume that A[1..n] contains n elements sorted in increasing order. Then 10 new elements are added at the end of the array. Design a sorting algorithm (using pseudocode) that resorts the array A[1…n+10] in running time O(n).

Explanation / Answer

for resorting an Array of large number of elements .it is better to choose
the Insertion sort algorithm.
assume that size of array is n asA[1..n]
after adding 10 elements the array could be n+10 as A[1.....n+10]
the pseudo code for insertion sort is

insertion(int a[],int n)
{
   int k,i,y;
   for(k=n-10;k<n;k++)
   {
       y=a[k];
       for(i=k-1;i>=0 && y<a[i];i--)
       {
           a[i+1]=a[i];
           a[i]=y;
       }
   }
}

when considering large volume of array first loop is exceptable means it runs 10 X n times

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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