## 10327 - Flip Sort

Moderator: Board moderators

### 10327 - Flip Sort

i send my programe tothe judge !!but it got WA and I don't know why!!
is there anyone can help me to find the bug ???
[cpp]
#include<stdio.h>
int in[5000],input,time=0,ins;
main()
{
while(scanf(" %d",&input)==1)
{
time=0;
for(int i=0;i<input;i++)
scanf(" %d",&in[i]);
for(int i=0;i<input;i++)
{
for(int j=i+1;j<input;j++)
{
if(in[i]>in[j])
{
ins=in[i];
in[i]=in[j];
in[j]=ins;
time++;
}
}
}
printf("Minimum exchange operations : %d\n",time);
}
}[/cpp]
mystical_liu
New poster

Posts: 9
Joined: Sun Jul 21, 2002 1:18 pm

And there is no need to use big numbers.
Shih-Chia Cheng
New poster

Posts: 17
Joined: Fri May 24, 2002 4:24 am
Location: Taiwan

### i fix my code... but ....

i fix my code but it still WA!!
can you say more clear???

i find the smallest number and change
Is there any thing i didn't consider???

[cpp]
#include<stdio.h>
int in[5000],input,time=0,ins,min=0;
main()
{
int i,j;
while(scanf(" %d",&input)==1)
{
time=0;
for(i=0;i<input;i++)
scanf(" %d",&in[i]);
for(i=0;i<input;i++)
{
min=i;
for(j=i+1;j<input;j++)
if(in[i]>in[j])
min=j;
if(in[i]>in[min])
{
ins=in[i];
in[i]=in[min];
in[min]=ins;
time++;
}
}
printf("Minimum exchange operations : %d\n",time);
}
}[/cpp]
mystical_liu
New poster

Posts: 9
Joined: Sun Jul 21, 2002 1:18 pm

### Re: i fix my code... but ....

mystical_liu wrote:i fix my code but it still WA!!
can you say more clear???

i find the smallest number and change
Is there any thing i didn't consider???

[cpp]
#include<stdio.h>
int in[5000],input,time=0,ins,min=0;
main()
{
int i,j;
while(scanf(" %d",&input)==1)
{
time=0;
for(i=0;i<input;i++)
scanf(" %d",&in[i]);
for(i=0;i<input;i++)
{
min=i;
for(j=i+1;j<input;j++)
if(in[i]>in[j]) <-------- in[min]>in[j] i think is what you want
min=j;
if(in[i]>in[min])
{
ins=in[i];
in[i]=in[min];
in[min]=ins;
time++;
}
}
printf("Minimum exchange operations : %d\n",time);
}
}[/cpp]
Joe Smith
New poster

Posts: 26
Joined: Wed Apr 17, 2002 5:56 am

In this approach only one operation ( Flip ) is available and that is you can exchange two adjacent terms.

Tip: try your first version, minus the swaping of the list elements.

--
SWeko has spoken
sweko
New poster

Posts: 7
Joined: Fri Apr 19, 2002 4:05 pm

### OH!!!!I got it!!

OH!!!
I got it !!!!!
thinks a lot!!~!~
I know where am I wrong!!
mystical_liu
New poster

Posts: 9
Joined: Sun Jul 21, 2002 1:18 pm

### 10327

hI why i am getting tle for this problem? is there any efficient algorithm for this problem. Will anybody kindly see my code and tell me where i am doing too much.Here is my code:
#include <stdio.h>

main()
{
int a[1001],r,n,i,j,temp,cnt,count;
while(1)
{
r=scanf("%d",&n);
if(r==EOF) break;
for(i=0;i<n;i++)
scanf("%d",&a[i]);
a[i]=0;
cnt=0;
for(i=0;i<n;i++)
{
count=0;
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
cnt++;
temp=a[j];
a[j]=a[i];
a[i]=temp;
i++;
if(i>=n-1) {i=-1;break;}
}
else if(a[i]<a[j])
{
count++;
if (count==n-1) {i=n;break;}
i++;
if(i>=n-1) {i=-1;break;}

}
}
}
printf("Minimum exchange operations : %d\n",cnt);
}
return 0;
}

yahoo
Learning poster

Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

You only have to count all inversions (such i<j that t[i]>t[j])
gawry
New poster

Posts: 19
Joined: Fri Aug 02, 2002 5:54 pm

Would you please kindly explain what do you mean by i<j such that t[i]>t[j]. I can't understand. Thanks in advance.

yahoo
Learning poster

Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

It's easy - let's take a sequence
seq = [1, 3, 2]
for i=2 and j=3 (like in Pascal) seq[i] > seq[j] , but i < j. it's inversion ...

You should only find and count all this situations - after it print counted number and it's all

nice work
Dominik Michniewski
Guru

Posts: 828
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland

Thanks. I got accepted. Thank you very much.

yahoo
Learning poster

Posts: 93
Joined: Tue Apr 23, 2002 9:55 am

### 10327 help

can i use number of swapping in bubble sort to calculate the min. operation ?
If yes, why there is still WA?
route
New poster

Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

Counting bubblesort swaps should be correct, are you sure there is no bug in your program?
Actually to make it faster, you don't have to swap at all. Simply count the number of inversions...
junjieliang
Experienced poster

Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

### 10327 help

[pascal]
Program flip;
var i, j, cnt, n, temp:longint;
m:array[1..1000] of longint;

begin
while not eof do
begin
for i:=1 to n do
cnt:=0;
for i:=1 to n-1 do
for j:=n downto i+1 do
If m[j] < m[j-1] then
begin
temp:=m[j-1]; (*this sentence is omitted*)
m[j-1]:=m[j]; (*this sentence is omitted*)
m[j]:=temp; (*this sentence is omitted*)
inc(cnt);
end;
writeln('Minimum exchange operations : ', cnt);
end;
end.
[/pascal]

This is my program ...
and I try to omit some sentences after you've told swapping is not necessary...
I think there is no bug....
but i still got WA
can you tell me what the problem is ?
Thanks
[/pascal]
route
New poster

Posts: 39
Joined: Sat Dec 21, 2002 1:25 am

Reason: The input is something like 3<eoln>1<space>2<space>3<space><eoln><eof>
Without the readln your program will process the last case twice, hence WA.
junjieliang
Experienced poster

Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Next