## 10327 - Flip Sort

Moderator: Board moderators

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

### 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);
for(i=0;i<n-1;i++)
for(j=i+1;j<n;j++)
{
if(a>a[j])
{
temp=a;
a=a[j];
a[j]=temp;
count++;
}
}
printf("Minimum exchange operations : %ld\n",count);
count=0;
}
return 0;
}

Rushow
New poster
Posts: 14
Joined: Sat Oct 14, 2006 4:09 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);
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(s>s[j])
{
x=s;
s=s[j];
s[j]=x;
m++;
}
}

}

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

Tariq Shahriar
New poster
Posts: 17
Joined: Wed Mar 01, 2006 8:34 pm
Location: 2nd floor
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/pr ... rting.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 ]

newton
Experienced poster
Posts: 162
Joined: Thu Jul 13, 2006 7:07 am
Contact:
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.

jainal cse du
New poster
Posts: 23
Joined: Thu Jul 27, 2006 2:43 pm
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++;
}
}

``````

andysoft
Experienced poster
Posts: 109
Joined: Sat Jun 23, 2007 9:53 pm
Location: Brest, BELARUS
Contact:
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
if eof then break;
for i:=1 to n do
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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Maybe your program actually gets a runtime error.
Judge doesn't detect runtime errors for Pascal programs, and incorrectly gives WA verdict instead.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### 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.

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:
Cheque it

Code: Select all

``````Input:
5
5 1 3 5 1
output:
Minimum exchange operations : 5
``````
Thanks
Keep posting
sapnil
"Dream Is The Key To Success"

@@@ Jony @@@

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### Thanks....

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

carliros
New poster
Posts: 6
Joined: Wed Aug 13, 2008 1:30 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

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

### 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.

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

### Re: 10327 - Flip Sort

yes, my code was AC.

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

### 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);

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

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

return 0;

}

pls help me..

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am

### 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:
5
5 1 3 5 1
output:
Minimum exchange operations : 5``````