## Friday, August 31, 2012

### Codeforces 136 Div-2

Today, I once again participated Ru based Algorithms Online Contest, Codeforces 136 Div-2.
The problem C is pretty tricky.
But something more important caught my attention;
First I tried the first piece of code as follow,
Then, the second one.
However, the first one got passed.
Things I noticed is Arrays.sort(?) were written in different algorithms:

1st, The static void `sort(int[] a), `is a tuned quicksort, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

2nd, The static void sort(object[] a) , uses modified mergesort, which is stable and guaranteed nlg(n) algorithm.

From my knowledge, this two should be in kind of same performance, and quicksort could be faster for some cases. But today, for this problem, which is a simple sorting problem, doesn't apply for my common sense.

IF YOU HAVE ANY IDEA ABOUT THIS, PLZ, PLZ LEAVE ME COMMENT ON THIS.
HUGE THANKS.

Comment:
```import java.util.Arrays;
import java.util.Scanner;

/**
* User: antonio081014
* Date: 8/31/12
* Time: 9:10 PM
*/
public class C {

public static void main(String[] argv){
C main = new C();
main.run();
System.exit(0);
}

public void run(){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] array = new int[n];
int[] array2 = new int[n];
for (int i = 0; i < array.length; i++) {
array[i] = scanner.nextInt();
array2[i] = array[i];
}

Arrays.sort(array2);
int cont = 0;
for (int i=0 ; i<array2.length ; i++)
cont += array[i] == array2[i] ? 0 : 1;
System.out.println(cont<=2?"YES":"NO");
}
}
```

Comment:
```import java.util.Arrays;
import java.util.Scanner;

/**
* User: antonio081014
* Date: 8/31/12
* Time: 9:10 PM
*/
public class C {

public static void main(String[] argv){
C main = new C();
main.run();
System.exit(0);
}

public void run(){
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
Integer[] array = new Integer[n];
Integer[] array2 = new Integer[n];
for (int i = 0; i < array.length; i++) {
array[i] = new Integer(scanner.nextInt());
array2[i] = new Integer(array[i]);
}

Arrays.sort(array2);
int cont = 0;
for (int i=0 ; i<array2.length ; i++)
cont += array[i].equals(array2[i]) ? 0 : 1;
System.out.println(cont<=2?"YES":"NO");
}
}
```