## 10327 - Flip Sort

Moderator: Board moderators

### 10327 - <Flip sort >WA ? need test case?

Using bubble sort I am getting WA ?

Code: Select all
`/*Name:  Flip Sort Number: 10327Type :  sortingProcess : ONAuthor :Salman ZamanEmail : zamansalman@gmail.comDate : 02/06/05 01:27*/#include<stdio.h>//#include<conio.h>int main(){      int input[2000]={0};      int n,i,temp,j,count;      // freopen("10327.txt","r",stdin);        while(scanf("%d",&n)!=EOF){         for(i=1;i<=n;i++){             scanf("%d",&input[i]);         }             count=0;         for(i=1;i<=n-1;i++){            for(j=i;j<=n;j++){                if(input[i]>input[j]){                    temp=input[i];                    input[i]=input[j];                    input[j]=temp;                    count++;                }                }                }                      printf("Minimum exchange operations : %d\n",count);     }             //getch();   return 0;}`

Salman
New poster

Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

### how to calculate minimum operation ?

I donot understand how to calculate the minimum exchange opereation.
Can someone expline?
Salman
New poster

Posts: 25
Joined: Thu Jun 26, 2003 9:45 am

for the input
Code: Select all
`4 3 2 1`
after the first swap operation:between 4 and 1
it becomes:
Code: Select all
`1 3 2 4`
and after the second swap operation: between 2 and 3 it becomes
Code: Select all
`1 2 3 4`
that means the input is sorted. only two swap operation needed
now try to find the accurate algorithm for it

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

### 10327 flip sort Why WA???

Why WA?

My Code:
Code: Select all
`#include <iostream>#include <stdio.h>#include <string>#include <stdlib.h>#include <fstream>#include <math.h>using namespace std;int poc=0;int vel=0;int *pole;int vys[100000];int d=0;//this function find smallest number and return his positionint nejmensi(int a,int vel){   int pom=a;   for(int i=a;i<vel-1;i++){      if(pole[pom]<=pole[i+1]){          //pom=i;      }else{          pom=i+1;      }            }   return pom;}void main() {   int proh=0;   int pom=0;   int p=0;   while(cin>>vel){   if(vel<=1000){   pole=new int[vel];   for(int a=0;a<vel;a++){      cin>>p;      pole[a]=p;   }   for(int k=0;k<vel-1;k++){      pom=nejmensi(k,vel);      if(pole[k]==pole[pom] ){      }else{      proh=pole[k];      pole[k]=pole[pom];      pole[pom]=proh;      poc++;      }         }   vys[d]=poc;   poc=0;   d++;   delete [] pole;   }else{   break;   }   }   for(int j=0;j<d;j++){      printf("Minimum exchange operations : %ld\n",vys[j]);      //cout<<endl;   }}`
Last edited by wigin on Thu Oct 27, 2005 8:56 pm, edited 1 time in total.
wigin
New poster

Posts: 2
Joined: Mon Oct 17, 2005 12:50 pm

as far as I can remember the problem was only to find the number of flips required in an "insertion sort"

what algo do u use ??
Where's the "Any" key?
Solaris
Learning poster

Posts: 99
Joined: Sun Apr 06, 2003 5:53 am

Solaris wrote:as far as I can remember the problem was only to find the number of flips required in an "insertion sort"

what algo do u use ??

My algo work so:
input:
Code: Select all
`  4  4 3 2 1`

find smallest number and replace with number which is first position
smaller is 1
replace 4 and 1
Code: Select all
`1 3 2 4`

next
find smaller number from second position
next number is 2
replace 3 and 2
Code: Select all
`1 2 3 4output:  Minimum exchange operations : 2`

Is my algo wrong?
wigin
New poster

Posts: 2
Joined: Mon Oct 17, 2005 12:50 pm

wigin wrote:Is my algo wrong?

Yes, you can only flip two numbers if they are ajacent. So you need 6 flips to sort 4 3 2 1:
Code: Select all
`4 3 2 13 4 2 13 4 1 23 1 4 21 3 4 21 3 2 41 2 3 4`

little joey
Guru

Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

### 10327----WA!!!!

Code: Select all
`var i,j,k,m,n,ans:longint;    a:array[1..1000] of integer;begin  while not eof do    begin      readln(n);      ans:=0;      for i:=1 to n do read(a[i]);      for i:=1 to n do        begin          m:=i;          for j:=i+1 to n do              if a[j]<a[m] then m:=j;          if m<>i then            begin              ans:=ans+1;              k:=a[i];              a[i]:=a[m];              a[m]:=a[i];            end;        end;      writeln('Minimum exchange operations : ',ans);    end;end.`

What's wrong with my algo.?
I used a selection algo. but get WA
those
New poster

Posts: 2
Joined: Tue Oct 11, 2005 3:24 pm

From the problem statement:
only one operation ( Flip ) is available and that is you can exchange two adjacent terms.

The word adjacent is important: you can swap a[i] only with a[i+1] or a[i-1].
mf
Guru

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

I got ac by running bubble sort ! and increasing a
counter if i made a swap
Last edited by 898989 on Fri Sep 15, 2006 11:34 pm, edited 1 time in total.
898989
Learning poster

Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt

I got an AC by doing the bubblesort and count the number of change.
New poster

Posts: 23
Joined: Thu Jun 22, 2006 8:55 am

### plz help

I also got WA . Is my algo.. wrong????

Plz somebody help me

here is my code:

Code: Select all
`#include<stdio.h>#include<math.h>long long int arr[1001];int inver_my(int n) {    int i,j,c=0;        if( n==0 || n==1)       return 0;       for(i=0;i<n-1;i++)    {       for(j=i;j<n;j++)       {          if(arr[i]>arr[j])          {             c++;                   }       }    }    return c; } int main(){      int n;      while(scanf("%d",&n) != EOF)   {      int c=0;               for(int i =0; i<n ; i++)      {         scanf("%lld",&arr[i]);      }               c= inver_my(n);            printf("Minimum exchange operation : %d\n",c);   }      return 0;   }`
moon
moon
New poster

Posts: 5
Joined: Mon Jan 02, 2006 12:49 pm

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

emotional blind wrote:Yes your algorithm is Wrong

You're wrong.

moon's algorithm is correct, it counts the number of inversions. The only problem with the code is that it should print "operations" instead of "operation".
mf
Guru

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

### thanx

Thanks a lot to mf . I am so for my silly mistake . i got AC
thanks also to emotional blind
moon
moon
New poster

Posts: 5
Joined: Mon Jan 02, 2006 12:49 pm

PreviousNext

### Who is online

Users browsing this forum: No registered users and 1 guest