## 10327 - Flip Sort

Moderator: Board moderators

### 10327

Plz help me to find the mistake
Here is my code
#include<stdio.h>
int main()
{
long int n,i,j,temp,a[100000],k,count=0,p;
while(scanf("%ld",&n)==1)
{
for(i=0;i<n;i++)
scanf("%ld",&a[i]);
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
count++;
}
}
printf("Minimum exchange operations : %ld\n",count);
count=0;
}
return 0;
}
Gungchil
New poster

Posts: 2
Joined: Mon Aug 21, 2006 3:10 pm

### 10327

This is my source code. Anyone can tell what's the problem in it?

/* p10327 */
/* Flip Sort */

#include<stdio.h>
void main()
{
long s[1002],n,i,j,x,m;
while(scanf("%ld",&n)!=EOF)
{
m=0;
for(i=0;i<n;i++)
scanf("%d",&s[i]);
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(s[i]>s[j])
{
x=s[i];
s[i]=s[j];
s[j]=x;
m++;
}
}

}

printf("Minimum exchange operations : %ld\n",m);
}
}
Rushow
New poster

Posts: 14
Joined: Sat Oct 14, 2006 4:09 pm

Rushow, you forgot the terms & conditions of the problem
only one operation ( Flip ) is available and that is you can exchange two adjacent terms

but your algorithm didn't perform like this.
2 3 1
in your algo, first interchange occurs between 2 and 1, but 2 and 1 is not adjacent. always swap between two adjacent (consecutive positioned) number (when needed).
so your algo is not flip (bubble) sort, actually replacement sort.

recently, our teacher taught us bubble sort, but you mistook. so bad.
let observe step by step, how flip sort will work
(currently comparing numbers will be shown in red)-
3 2 1 //the initial position of the array n=3 elements
3 2 1 //swap. after swapping: 2 3 1
2 3 1 //swap
2 1 3 //after n-1 comparison the largest element will in last position. so no eed to compare with it latter. again start from the beginning)
2 1 3 //swap
1 2 3 //after n-2 comparison the 2nd largest element will in 2nd last position. so no need to compare with it latter. there has only one element. so sorting was completed)

we swapped for 3 times. so ans=3.

to clear more, u can also get help from: http://www.comp.nus.edu.sg/~stevenha/programming/prog_sorting.html

// N.B. while writing code, use BBcode tags. visit BBcode Guide
[ Common thing of every man is that, everyone thinks that he is uncommon ]

Tariq Shahriar
New poster

Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor

thank you jainal.
you are really a genish!!!
Last edited by newton on Mon Jul 23, 2007 11:01 am, edited 1 time in total.

newton
Experienced poster

Posts: 162
Joined: Thu Jul 13, 2006 7:07 am

Hi Newton,you have to count only minimum exchange operations.
So,replace it .

Code: Select all
`for(i = 0;i < num-1; i++) {          for(j = i+1;j < num;j++)          {                if(array[i] > array[j])               {                     cnt++;                     tmp = array[i];                     array[i] = array[j];                     array[j] = tmp;               }          } } `

By following

Code: Select all
`cnt = 0;for(i = 0;i < num; i++) {          for(j = i+1;j < num;j++)          {               if(array[i] > array[j])                      cnt++;           } } `

jainal cse du
New poster

Posts: 23
Joined: Thu Jul 27, 2006 2:43 pm

HOW can this code give WA?
I got already 7 (or like that) WAs on this easy prob.

Code: Select all
`program Project1;{\$APPTYPE CONSOLE}uses  SysUtils;var  a: array [1..1000] of integer;  i,j,k,l,n: integer;  fl: boolean;begin  while not eof do  begin    readln (n);    if eof then break;    for i:=1 to n do      read (a[i]);    k := 0;    fl := true;    while fl do    begin      fl := false;      for j:=1 to n-1 do        if a[j]>a[j+1] then        begin          inc(k);          fl := true;          l := a[j];          a[j] := a[j+1];          a[j+1] := l;          fl := true        end    end;    writeln ('Minimum exchange operations : ',k)  end;end.`
Now I lay me down to sleep...
my profile
andysoft
Experienced poster

Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS

Maybe your program actually gets a runtime error.
Judge doesn't detect runtime errors for Pascal programs, and incorrectly gives WA verdict instead.
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

### 10327....

I don't know why judge give me worng answer.... plezz help me.... This is too..... much crazy.
Code: Select all
`removed`
Last edited by Obaida on Tue Feb 24, 2009 2:49 pm, edited 1 time in total.
try_try_try_try_&&&_try@try.com
This may be the address of success.
Obaida
A great helper

Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

Cheque it

Code: Select all
`Input:55 1 3 5 1output:Minimum exchange operations : 5`

Thanks
Keep posting
sapnil
"Dream Is The Key To Success"

@@@ Jony @@@
sapnil
Experienced poster

Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST

### Thanks....

Thank You..... Got Ac....
try_try_try_try_&&&_try@try.com
This may be the address of success.
Obaida
A great helper

Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### 10327 - Flip Sort --> more inputs

Input
5
6 2 1 5 4
8
3 5 8 2 1 9 7 0
2
0 0
12
0 1 2 5 4 1 2 0 5 0 7 9
30
21 5 6 5 8 452 12 5 96 21 21 5 6 5 8 452 12 5 96 21 21 5 6 5 8 452 12 5 96 21 21 5 6 5 8 452 12 5 96 21 21 5 6 5 8 452 12 5 96 21

output
Minimum exchange operations : 6
Minimum exchange operations : 16
Minimum exchange operations : 0
Minimum exchange operations : 19
Minimum exchange operations : 168
Minimum exchange operations : 67
carliros
New poster

Posts: 6
Joined: Wed Aug 13, 2008 1:30 am

### Re: 10327 - Flip Sort --> more inputs

carliros wrote:Input
Minimum exchange operations : 6
Minimum exchange operations : 16
Minimum exchange operations : 0
Minimum exchange operations : 19
Minimum exchange operations : 168
Minimum exchange operations : 67

Do your code is accepted?? I am quite confused! Though i do not get ac, but your output have increased my confusion.
debugger
New poster

Posts: 8
Joined: Tue Jul 29, 2008 6:24 pm

### Re: 10327 - Flip Sort

yes, my code was AC.
carliros
New poster

Posts: 6
Joined: Wed Aug 13, 2008 1:30 am

### Re: 10327 - Flip Sort

this is my code. i got WA..
but what is wrong in this code?

#include<stdio.h>

int main()
{
long int n,a[1001];

while(scanf("%ld",&n)==1)
{
long int i,j,x=0,temp;

for(i=0;i<n;i++)
scanf("%ld",&a[i]);

for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
if(a[i]>a[j])
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
x++;
}

printf("Minimum exchange operations : %ld\n",x);
}

return 0;

}

pls help me..
pok
New poster

Posts: 25
Joined: Sun Nov 09, 2008 11:04 pm

### Re: 10327 - Flip Sort

You didn't need to do exchange but count how many exchange are available.

Ok, check this input,
Code: Select all
`Input:55 1 3 5 1output:Minimum exchange operations : 5`

try_try_try_try_&&&_try@try.com
This may be the address of success.
Obaida
A great helper

Posts: 380
Joined: Wed Jan 16, 2008 6:51 am