Mrs. Chambers always has her class line up in height order (shortest at the fron

Question

Mrs. Chambers always has her class line up in height order (shortest at the front of the line). Every September a new class of exactly 20 3rd graders arrive, all of different height. For the first few days it takes a long tome to get the kids in height order, since no one knows where they should be in the line. Needless to say, there is quite a bit of jockeying around. This year Mrs. Chambers decried to try a new method to minimize this ordering chaos. One student would be selected to be the first person in line. Then, another student is selected and would find the first person in the line that is taller than him, and stand in front of that person, thereby causing all the students behind him to step back to make room. If there is no student that is taller, then he would stand at the end of the line. This process continues, one student at-a-time, until all the students are in line, at which point the students will be lined up in height order. For this problem, you will write a program that calculates the total number of steps taken back during the ordering process for a given class of students. The first line of input contains a single integer p, (1 lessthanorequalto p lessthanorequalto 1000), which is the number of data sets that follow. Each data set should be processed identically and independently. Each data set consists of a single line of input. It contains the data set number, K, followed by non-negative unique integers separated by a single space. The 20 integers represent the height (in millimeters) of each student in the class. For each data set there is one line of output. The single output line consists of the data set number, K, followed by a single space followed by total number of steps taken back. Use the data below for this assignment. Enter it into a text Tile which you save on the disk. Read the data from the file that you saved.

Explanation / Answer

#include<iostream>
#include<fstream>

using namespace std;
//s-d array to represnt class nd 20 height

int **class_student;
//no of columns
const int col = 20;
int steps_taken(int class_student[],int col);
int main()
{
   ifstream in;
   //open file which contains data,I have named it height.txt, u can choose name of your choice
   in.open("height.txt");
   int count = 0,n;
   if(!in)
   {
       cout<<"Can't open file ";
       return -1;
   }
   int row;
   in>>n;
   count = n;
   class_student = new int*[n];
   for( int i=0;i < n; ++i)
           class_student[i] = new int[col];
   int i= 0 ;
   //read from file
   while(!in.eof())
   {
       in>>row;
       for(int i = row-1 ,j = 0; j < 20; j ++)
       {
           in>>class_student[i][j];
          
       }
   }
   //display steps taken for each row of students height
   for( int i = 0 ; i < count ; i ++ )
   {

       cout<<i+1<<" "<<steps_taken(class_student[i],col)<<endl;
   }
   in.close();
}

//The problem statement gives to insertion sort algorithm
int steps_taken(int class_student[],int col)
{
   int steps = 0,d;
   int temp;
   for (int c = 1 ; c <= col - 1; c++)
   {
       d = c;

       while ( d > 0 && class_student[d] < class_student[d-1])
       {
           temp = class_student[d];
           class_student[d] = class_student[d-1];
           class_student[d-1] = temp;
            d--;
           ++steps;
}
   }
   return steps;
}

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

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