azrael

He modificado la imagen que en wikipedia ilustra Mergesort (de dominio público) para mostrar como funciona mi Optimal Comparison Sort.Recuerdo que para mezclar tres vectores, se usa el Merge3.Aprovecho para comentar que es el equivalente a un árbol balanceado.Las comparaciones en este caso son 10 para mi Optimal Comparison Sort , 14 para Mergesort y 15 para Quicksort eligiendo como pivote el elemento central. Espero un comportamiento proporcional para vectores aleatorios más grandes. EDITO: No son 10 sino 15 comparaciones. De todas formas confío en que en el caso medio sea más rápido. EDITO2: De todas formas no deja de ser un caso particular, ya que para N=7, OSort hará siempre entre 2+2+2+2=8 y 6+4+2+1+2=15 comparaciones, mientras Quicksort hará entre 6+2+2=10 y 6+5+4+3+2+1=21 (de la forma n-1(n)/2, por la fórmula de la suma de los n primeros números). Mergesort hará  3+3+2+6=14.

This entry was posted on Tuesday, November 20th, 2007 at 22:53 and is filed under Algoritmos ordenación., General, II CUSL, algoritmia. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.