Blog de programación e ideas locas

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.