We want to design an algorithm to sort a set of integer numbers and track how ma

Question

We want to design an algorithm to sort a set of integer numbers and track how many places they had to be moved to be in non-decreasing order. The user is first asked how many numbers they want to input and then they will be asked to input this set of integers. If the user indicated that they want to input zero numbers the program ends. When the numbers are sorted, the program prints out the ordered collection with the number of places that each number had to move (negative being moving left, and positive moving right). If the following was a piece of code:

How many number do you want to sort? 4

Input your 4 numbers now: 6 3 8 2

Then the output would be:

New array is 2,3,6,8 and they moved -3,0,2,1 places.

• Using the Engineering Problem-Solving Methodology show in detail, using whatever tools you have, how you would develop the algorithm. Define the problem statement, show the design of the algorithm and include the various refinement techniques as needed.

• Show how you intend to test your algorithm and outline the various limitations of the proposed algorithm.

• Finally convert your algorithm into a C program. Remember to use good programming standards, add comments to the code, and follow good formatting practices to lay out the code. It is likely that each of the parts of the algorithm will be implemented as functions in the program.

Explanation / Answer

#include <stdio.h>

void sort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
}

void printMove(int arr[], int old[] ,int n){
   int i,j;
   for(i=0; i<n; i++){
       int k = arr[i];
       for(j=0; i<n; j++){
           if(k==old[j]){
               printf(" %d ",(i-j));
               break;
           }
       }
   }
}
int main(){
   int num;
   int arr[10];
   int old[10];
   printf("How many number do you want to sort?");
   scanf("%d",&num);
   if(num>10){
       printf("num should be up to 10");
       return 0;
   }
   int i =0;
   while(i<num){ //Getting input numbers
       int n;
       printf("Enter Number:");
       scanf("%d",&n);
       arr[i] = n;
       old[i] = n;
       i++;
   }
   sort(arr,num); // sorting array
   printf("New array is ");
   for(i=0; i<num; i++){ // printing sorted array
       printf(" %d ",arr[i]);
   }
   printf(" and they moved ");
   printMove(arr,old,num); // printing moves
   printf("places ");
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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