10327 - Flip Sort

[Salman]

Using bubble sort I am getting WA ?

Code: Select all

/*
Name:  Flip Sort
Number: 10327
Type :  sorting
Process : ON
Author :Salman Zaman
Email : zamansalman@gmail.com
Date : 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;
}


Some one please help.

[Salman]

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

[emotional blind]

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

[wigin]

Please help me
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 position
int 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;
   }
}

[Solaris]

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

[wigin]

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 4
output:
  Minimum exchange operations : 2


Is my algo wrong?

[little joey]

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 1
3 4 2 1
3 4 1 2
3 1 4 2
1 3 4 2
1 3 2 4
1 2 3 4

[those]

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

[mf]

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

[898989]

I got ac by running bubble sort ! and increasing a
counter if i made a swap

[SHAHADAT]

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

[moon]

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


[emotional blind]

Yes your algorithm is Wrong
Read Little Joey's post.

[mf]

Yes your algorithm is Wrong
Read Little Joey's post.

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

[moon]

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