Ejemplos del algoritmo QuickSort

Hace tiempo que termine un libro de criptografía y mostraba diferentes algoritmos de cifrado. QuickSort era uno de ellos y por su enorme "fama" voy a dedicarle el siguiente post. A continuación mostraré un ejemplo del algoritmo en diferentes lenguajes de programación que conozco. La mayoría del parte del código está sacado de la siguiente web rosettacode.org.

Comenzaré haciendo una pequeña versión del algoritmo "raíz" y como se mejora. (En el siguiente ejemplo escrito en Python creo que se entenderá mejor.)

Python con pivote "fijo"

def qsort(lista):
    if lista == []:
        return []
    else:
        pivote = lista[0]
        izq = qsort([x for x in lista[1:] if x < pivote])
        dech = qsort([x for x in lista[1:] if x >= pivote])
        return izq + [pivote] + dech

Python con pivote aleatorio.

from random import randrange
def qsort(lista):
    def qsort(lista):
        if lista == []:
            return []
        else:
            pivote = lista.pop(randrange(len(lista)))
            izq = qsort([l for l in lista if l < pivote])
            dech = qsort([l for l in lista if l >= pivote])
            return izq + [pivote] + dech
     return qsort(lista[:])

Los algoritmos hacen lo mismo ordenar una lista de elementos. La diferencia entre el algoritmo "sin pivote" y el que lo tiene implementado es simple. La pila se desborda en aproximadamente a los 1000 elementos ordenados. Sin embargo, mediante la de un pivote asignado al azar se evita el desbordamiento de pila, y logra un buen rendimiento. Es decir para pocos elementos usamos la primera ya que usar el segundo método ralentiza el proceso al intentar asignar el numero aleatorio. Pero para el resto de casos mejor la segunda opción.

Y partiendo de este breve ejemplo y explicación os dejo un ejemplo en diferentes lenguajes listos para su uso. Espero que al transcribir el código no se me haya colado nada que pueda dar error en el código, si encontráis erratas avisarme para corregirlas.

Quicksort en PHP

<?php
     function qsort($array,$inicio,$fin){
         $mitad=$array[floor(($inicio+$fin)/2)];
         $i=$inicio;
         $j=$fin;
         do{
             while ($array[$i]<$mitad) $i++;
             while ($array[$j]>$mitad) $j--;
             if ($i<=$j){
             $temp=$array[$i]; $array[$i]=$array[$j]; $array[$j]=$temp;
                 $i++; $j--;
             }
         }while ($i<=$j);
        if ($fin<$j) $this->qsort($array, $inicio, $j);
        if ($i<$fin) $this->qsort($array, $i, $fin);
  }

// lo usamos de la siguiente manera
$list=array(5,4,3,2,1,6,8,9);
$this->qsort($list,0,count($list)-1);
//mostramos el listado ordenado
for($i=0;$i<count($list);i++) echo list[$i]." - ";
?>

Quicksort en JavaScript

function particion(array, inicio, fin, pivote){
 var piv=array[pivote];
 array.swap(pivote, fin-1);
 var aux=inicio;
 var ix;
 for(ix=inicio; ix<fin-1; ++ix){
  if(array[ix]<=piv) {
   array.swap(aux, ix);
   ++aux;
  }
 }
 array.swap(fin-1, aux);
return aux;}

function qsort(array, inicio, fin){
 if(fin-1>inicio){
  var pivote=inicio+Math.floor(Math.random()*(fin-inicio));
  pivote=particion(array, inicio, fin, pivote);
  qsort(array, inicio, pivote);
  qsort(array, pivote+1, fin);
 }
}

Ejemplo con Ruby

def qsort(lista, p, r)
    if p < r then
        q = particion(lista, p, r)
        qsort(lista, p, q-1)
        qsort(lista, q+1, r)
    end
end

def particion(lista, p, r)
    pivote = lista[r]
    i = p - 1
    p.upto(r-1) do |j|
        if lista[j] <= pivote
            i = i+1
            lista[i], lista[j] = lista[j],lista[i]
        end        
    end
    lista[i+1],lista[r] = lista[r],lista[i+1]
    return i + 1
end

# forma de usarlo
a = [9,4,10,12,3,5,10,3,2,25,6,21,33,23,19,13,38,26,12,3]
qsort(a, 0, a.length-1)
puts a

Quicksort con Java

import static org.junit.Assert.assertArrayEquals;
import org.junit.Test;

public class Qsort {
    static <T extends Comparable<? super T>> void qsort(T[] array){
        qsort(array, 0, array.length - 1);
    }

    static <T extends Comparable<? super T>> void qsort(T[] array, int izq0, int dech0){
        int izq = izq0;
        int dech = decht0 + 1;
        T pivote, aux;
        pivote = array[izq0];
        do {
            do izq++; while (izq <= dech0 && array[izq].compareTo(pivote) < 0);
            do dech--; while (array[dech].compareTo(pivote) > 0);
            if (izq < dech) {
                aux = array[izq];
                array[izq] = array[dech];
                array[dech] = aux;
            }
    }while (izq <= dech);
    aux = array[izq0];
    array[izq0] = array[dech];
    array[dech] = aux;
    if (izq0 < dech) qsort(array, izq0, dech);
    if (izq < dech0) qsort(array, izq, dech0);
}

    String[] array = {"Batman", "Spiderman", "Anthony", "Zoolander"};
    qsort(array);
    String[] correcto = {"Anthony", "Batman", "Spiderman", "Zoolander"};
    assertArrayEquals(correcto, array);

}

Bueno creo que con estos ejemplos ya hay suficiente en la página de rosettacode.org Hay muchísimos más ejemplos.