Mr. Dengklek has a farm of ducks. He has many types of ducks that varies in size. The ducks like to form lines, which need to be in the correct order. The ducks within the same type need to be behind or in-front of each other. Furthermore, in each types, the ducks are arranged from the little to the largest in size. The order of types of ducks is not too important.
Since Mr. Dengklek only has one hour left, he need to order his ducks quickly.
Please create a c++ program in Dev c++ that display the number of minimal steps required to arrange the ducks.
The first line will consist of a number inputted, C (the tens) and N (the unit). If the input is 21, so C is 2 and N is 1. C is the number of ducks' types and N is the number of how many ducks in each types.
Every C*N line after, a 2-digit number will be inputted, X (the tens) and Y (the unit). X is the type number and Y is the duck's size. FYI, there is no duck that has the same type and size.
That's the right idea, but you have a couple of problems.
You need a second loop in your sort.
You're not swapping the ducks in the array when you find them out of order.
The problem statement says to order from littlest to largest. Your comparison is counting the number of smaller ones in front of bigger ones.
#include <iostream>
usingnamespace std;
int main()
{ int a,ducks[100];
int num_types, ducks_per_type, num_ducks;
int i, j, num_swaps = 0, temp;
cout << "CN?";
cin>>a;
num_types=(a/10);
ducks_per_type=(a%10);
num_ducks = num_types * ducks_per_type;
// Populate the ducks
for (i=0;i<num_ducks;i++)
{ cout << "XY?";
cin >> ducks[i];
}
// sort the ducks
for(i=0;i<num_ducks-1;i++)
{ for (j=i+1; j<num_ducks; j++)
{ if (ducks[i] > ducks[j])
{ // swap the two ducks
temp = ducks[i];
ducks[i] = ducks[j];
ducks[j] = temp;
num_swaps++;
}
}
}
cout << "Ducks After sort" << endl;
for (i=0;i<num_ducks; i++)
cout << ducks[i] << endl;
cout << "Number of swaps: " << num_swaps << endl;
system("pause");
return 0;
}
I renamed most of your variables names as I found them too confusing.
Could the number of swaps be reduced if order of the types is ignored in the sort criteria (sort same type together, but order of types doesn't matter per problem statement)? I'll leave that to you to discover.
Btw, from your code I notice that you simply swamp the values when ordering the duck. However, can you help me in doing something like this:
Order duck(1):
32
22
11
31
21
12
Order duck(2):
*First move
31
32
22
11
21
12
Basically, when 31 move, the 21 behind it automatically fill that spot and when it gonna fill the first spot, the 32,22,11,21,12 automatically step back.
Therefore, they are not simply exchanging positions.