Etiqueta: quicksort

Algoritmo de ordenamiento Quicksort en Javascript animado con jquery

En esta entrada utilizare el algoritmo de quicksort en javascript que publique anteriormente y lo acomode de una manera especial para poder mostrar poco a poco como se va ordenando un conjunto de números por medio de este método de ordenamiento.

Para el que no conozca la función que estoy utilizando setTimeout, esta simplemente se encarga de ejecutar una función o un código después de pasar cierto tiempo, en este caso puse 500 que es medio segundo. Hago uso de esta función par que se pueda notar el ordenamiento y no sea instantáneo.

A continuación anexo el ejemplo animado, solo denle clic en el botón comenzar:

Y ahora el código que hace posible esta demostración:

CSS

.bloque{
float:left;
margin-left:5px;
margin-bottom:2px;
width:20px;
height:20px;
text-align::center;
padding:5px;
background:#fff;
}

HTML


<div id="contenido" style=" background:#efefef; height:90px; padding:10px;"></div>
<input id="botonsito" type="button" value="Comenzar" onclick="comenzar()" />

Javascript


//arreglo a ordenar
arreglo=[10,9,19,8,1,12,14,0,5,6,9,17,10,4,5,3,2,3,4,5,6,7,88,77,66,55,44,33,21,2,33,44,73,78,9,2,3,0,1,8,1,13];

imprimirArreglo();

function comenzar(){

//llamamos la función mandando 0 en el primer parametro
//y mandando la longitud del arreglo -1
quicksort(0,(arreglo.length-1));

//desabilitamos boton
$("#botonsito").prop("disabled",true)

}

//funcion que plasma el arreglo para poder ser visualizado
function imprimirArreglo(){

//borramos el contenido del div del contenido
$("#contenido").html("");

//imprimimos los elementos en forma de div
for(i_=0;i_<arreglo.length;i_++){

//anexamos un div con clase bloque
$("#contenido").append("<div class='bloque'>"+arreglo[i_]+"</div>");
}

}

//función quicksort
function quicksort(primero,ultimo){
//definimos variables indices
i = primero
j = ultimo

//sacamos el pivote de la mitad del arreglo
pivote = arreglo[parseInt((i+j)/2)];

iteracionQS(i,j,pivote,primero,ultimo)

}

//funcion que suplanta el while y se llama recursivamente
function iteracionQS(i,j,pivote,primero,ultimo){

//mientras arreglo[i] sea menor a pivote
while(arreglo[i]<pivote)
i++;
//mientras j sea mayor a pivote
while(arreglo[j]>pivote)
j--;

//si el indice i es menor o igual a j entonces intercambiamos
if(i<=j){

//variable temporal auxiliar para guardar valor de arreglo[j]
aux=arreglo[j];

//intercambiamos los valores de arreglo[j] y arreglo[i]
arreglo[j] = arreglo[i]
arreglo[i] = aux

// incrementamos y decrementamos i y j
i++;
j--;

imprimirArreglo(arreglo);
}

//repetimos
if(i<j){
//hacemos una pausa de medio segundo
setTimeout(function(){
iteracionQS(i,j,pivote,primero,ultimo)
},500);
}else{
//si primero es menor a j llamamos la funcion nuevamente
if(primero<j){

//pausa de medio segundo
setTimeout(function(){
quicksort(primero,j);
},500);
}
//si ultimo es mayor que i llamamos la funcion nuevamente
if(ultimo>i){

//pausa de medio segundo
setTimeout(function(){
quicksort(i,ultimo)
}
,500);
}
}
}

De cualquier forma les dejo la liga directa al ejemplo mostrado, por si surge alguna duda.

Algoritmo de ordenamiento Quicksort en javascript

El algoritmo quicksort es un algoritmo de ordenamiento, como su nombre lo dice, es de los más rápidos y es recomendable su uso (no como el de burbuja).

Ver quicksort animado con jquery.

Aquí anexo el algoritmo de quicksort en javascript:

Función Quicksort

function quicksort(primero,ultimo){
	//definimos variables indices
	i = primero
	j = ultimo

	//sacamos el pivote de la mitad del arreglo
    pivote = arreglo[parseInt((i+j)/2)];

	//repetir hasta que i siga siendo menor que j
	do{

		//mientras arreglo[i] sea menor a pivote
		while(arreglo[i]<pivote) 			i++; 		//mientras j sea mayor a pivote 		while(arreglo[j]>pivote)
			j--;

		//si i es menor o igual a j, los valores ya se cruzaron
		if(i<=j){

			//variable temporal auxiliar para guardar valor de arreglo[j]
			aux=arreglo[j];

			//intercambiamos los valores de arreglo[j] y arreglo[i]
            arreglo[j] = arreglo[i]
            arreglo[i] = aux

			// incrementamos y decrementamos i y j
            i++;
            j--;
		}

	}while(i<j);

	    //si primero es menor a j llamamos la funcion nuevamente
		if(primero<j){ 			quicksort(primero,j); 		} 		//si ultimo es mayor que i llamamos la funcion nuevamente 		if(ultimo>i){
		    quicksort(i,ultimo);
		}
}

Como utilizarlo


//arreglo a ordenar
arreglo=[10,9,19,8,1,12,14,24,34,54,5,4,2,99,2,3,1,0];

//llamamos la función mandando 0 en el primer parametro
//y mandando la longitud del arreglo -1
quicksort(0,(arreglo.length-1));

//imprimimos para ver el resultado
alert(arreglo)