Ordering Numbers

[Tommy98]

hi , i need a logical help my program should be about:

int W;

it means there will be 2 lines , in every line there will be W numbers unordered from 1 to W , example , lets say w is 5

First Line : 1 2 3 4 5
Second Line : 2 4 5 3 1

both of these lines are entered by User , then you can "pull" each number just once , but when you do it means , the first Line is : 1 2 3 4 5 , you pull "3" so then the number 3 goes on the end of the sequence and all the numbers which where on the position of pulled number to right are being pushed back to the left so we got :1 2 4 5 3 and then we do the same with "1" and we will have 2 4 5 3 1 , we did just 2 steps to do this : so the minimum of steps like this , to transform the first line sequence to the second line sequence is 2 , then you also have to say , what would be the Maximum of steps like this to transform first line sequence to the second line sequence , dont forget , that you can pull each number just once , i dont want whole code , i just need somekind of logical help , anyone is up to help me please ?


so my goal is to check the minimum steps to transform it , and also the maximum possible amount of steps to do the same

[Tommy98]

anyone?

[Ericool]

there is several existing sorting algorithms and their Big O notation (interesting for worst case )

[ne555]

if in the first line you've got
... a ... b ...
and in the second
... b ... a ...
then `a' must have moved.

Because a movement makes that the last number, then looking at the second line everything on the right of `a' must have moved.

[whitenite1]

@Tommy98

To me, the maximum steps, would be the amount of numbers being used. If you say the value of W is 5, then you can only move 5 times, etc. Minimum, is 1. Depending on the order of each array.

Here's my version, up to a point. I fill the arrays randomly, not user inputted. At least it gives you ideas, (hopefully), and you can expand it to what your needs are.

#include <iostream>
#include <ctime>
#include <string>
#include <windows.h>

using std::cout;
using std::cin;
using std::endl;
using std::string;

void Shift_it(int W[],int move);

int main()
{
	srand (time(NULL));
	int W[20]={0};
	int W2[20]={0};
	int ck[20];
	int use,move,x,y;
	bool ok, game_over, over;
for (x=0;x<20;x++)
ck[x]=x+1;	
do{
	cout << "How many numbers, upto 20?"<< endl;
	cin >> use;
}while(use<1 || use >20);

cout << "We'll randomly fill the array"<<endl;
for (x=0;x<use;x++)
{
do{
	ok=false;
 y=rand()%use;
 if(W[y]==0)
 {
  	W[y]=x+1;
  	ok=true;
 }
}while(!ok);
}

cout << "Line 1 :" << endl;
for(x=0;x<use;x++)
	cout << W[x]<<" ";

cout << endl;
for (x=0;x<use;x++)
{
do{
	ok=false;
 y=rand()%use;
 if(W2[y]==0)
 {
  	W2[y]=W[x];
  	ok=true;
 }
}while(!ok);
}

cout << endl << "Line 2 :" << endl;	
for(x=0;x<use;x++)
	cout << W2[x]<<" ";

ok=false;

do
{
	ok=true;
	over=true;
for(x=0;x<use;x++)
{
	if(W[x]!=W2[x])
	   ok=false;
	if(ck[x]!=0)
	  over = false;
}
if(!ok && !over)
{

do
{
cout << endl << "Make Line 1, look like line 2." << endl << "Move which number to the right?"<< endl;
cin >> move;
if(ck[move-1]==0)
  cout << "That number was already moved. Choose another.."<< endl;
 }while (ck[move-1]==0);
 
 ck[move-1]=0;

Shift_it(W,move);
cout << endl << "Line 1 :" << endl;
for(x=0;x<use;x++)
	cout << W[x]<<" ";
cout << endl<< "Line 2 :" << endl;
for(x=0;x<use;x++)
	cout << W2[x]<<" ";
}
}while(!ok && !over);
if(over)
cout << endl << endl << "No more moves possibles."<<endl;
else
cout << endl << endl << "Congratulations!! You've done it.." << endl;

cin >> use; // Just to prevent screen from closing on completion..
}

void Shift_it(int W[],int move)
{
	int y=0,shift;
	while (W[y]!=move)
	y++;
	shift=W[y];
	while(W[y]!=0)
	{
		W[y]=W[y+1];
		y++;
	}
	W[y-1]=shift;	
}