Since some sorting algorithms are more efficient when the input list is close to

Question

Since some sorting algorithms are more efficient when the input list is close to sorted, we might be able to quickly sort a list by first checking how close the input list is to already being sorted, and then using that information to help us choose which sorting algorithm to use. One measurement of how dost; a list is to being sorted is the "move distance." Given an input list L of length n such that each number 1,2,..., n appears exactly once, define the "move distance" of L as the sum of the number of positions that each list element must be moved to get to its correct sorted position. Example: The move distance of 3,4,1,5,2 is 2 + 2 + 2 + 1 + 3 = 10 because 3 is 2 positions away from position 3, 4 is 2 positions away from position 4 and so on. The move distance of a list L gives us a sense of how far away list L is from being sorted. Write pseudo code that returns the move distance of any input list consisting of each number 1,2,... ,n appearing exactly once. Analyze the runtime of your algorithm using notation.

Explanation / Answer

#include<iostream.h>
#include<conio.h>

void main()
{
   int a[5]={3,4,1,5,2},i,b,s=0;

   for(i=0;i<5;i++)
   {
       b=a[i]-(i+1);
       if(b<0)
           b=b*(-1);
       s=s+b;
   }
   cout<<s;
   getch();
}

  

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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