Blog de programación e ideas locas

Buenas a todos.
Hoy en día un amigo y compañero de la Universidad abre un nuevo blog. El proposito del blog es una medida de ir archivando codigo y prepararse para la proxima competencia de ACM-ICPC.

Visita este nuevo blog y si te gusta el tema también puedes participar:
Los NCR’s Codeboard

Tambien quiero felicitar a los ganadores de la competencia.
Ricardo, Cathy y Javier alumnos de la Universidad de Concepción

Algunas fotos de la competencia.(En la primera salgo yo con mi equipo y Diego)

Hoy en día, mas que escribir algo un aporte a internet(si es que lo es) sera un aporte para mi, por que realizare un resumen para un certamén para mañana sobre los algortimos de ordenamiento HeapSort, QuickSort.

HeapSort

Este algoritmo se basa en usar la estructrura llamada “heap” que maneja la información durante la ejecución del algoritmo, lo que permite crear una cola de prioridades util para este ordenamiento. El heap es un arbol binario completo  almacenado en un arreglo dado de la siguiente manera.

dado un nodo i (posición dentro del arreglo)

Padre(i)
   return|_ i/2 _|
Hijo-Izquierdo(i)
   return 2i
Hijo-Derecho(i)
   return 2i+1

Notar que la division es entera y se redondea hacia arriba.

Además se debe satisfacer la propiedad A[Padre(i)] >= A[i], donde A es arreglo.

Consideremos desde literatura los algoritmos HEAPIPY(A,i) que mantiene la propiedad de un Heap y tiene un costo de O(log(n)) o  O(h) y el BUILD-HEAP(A) que construye un arbol Heap y tiene un costo de O(n)

HEAPSORT(A)

BUILD-HEAP(A)
for i ← largo[A] downto 2
     do exchange A[1] ↔ A[i]
     heap-size[A]  ← heap-size[A]-1
     HEAPIPY(A,1)

Este algoritmo de ordenamiento tiene un costo de O(nlog(n))

Quicksort

Este algoritmo, como el merge sort, se basa en el paradigma dividir y conquistar

QUICKSORT(A,p,r)
if p < r
  then q ← PARTICION(A,p,r)
         QuickSort(A,p,q)
         QuickSort(A,q+1,r)

PARTITION(A,p,r)
x←A[p]
i←p-1
j←r+1
while TRUE
        do repeat j ← j-1
            until A[j] ≤ x
            repeat i ← i+1
            until A[i] ≥ x
        if i < j
           then exchange A[i] ↔ A[j]
        else
           return j

Este algoritmo en el peor de los casos O(n²) y en mejor de los casos O(nlogn)

Un breve resumen.