10327 - Flip Sort

[Gungchil]

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;
}

[Rushow]

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

[Tariq Shahriar]

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.
think about second sample input-

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

[newton]

thank you jainal.
you are really a genish!!!

[jainal cse du]

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]

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.



[mf]

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

[Obaida]

I don't know why judge give me worng answer.... plezz help me.... This is too..... much crazy.

Code: Select all

removed

[sapnil]

Cheque it

Code: Select all

Input:
5
5 1 3 5 1
output:
Minimum exchange operations : 5


Thanks
Keep posting
sapnil

[Obaida]

Thank You..... Got Ac....

[carliros]

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]

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]

yes, my code was AC.

[pok]

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

[Obaida]

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

Hope you find your mistake.