Comparación de algoritmos de clasificación de intercambio

Este artículo analiza varias opciones para ordenar intercambios, y también describe una aplicación gráfica simple ( processing.js ) con ejemplos de tipos.

Antes de leer, le recomiendo que lea los artículos del usuario valemak :

→ Clasificación de intercambio
→ Clasificación de burbujas y todo-todo-todo
→ Tipo tonto y algún otro más inteligente

Ordenar burbujas

La opción más simple es iterar sobre la matriz desde el primer elemento hasta el último, intercambiando (si es necesario) elementos vecinos.

→ Consultar aquí


Para mover el control deslizante, debe hacer clic en el botón gris en la esquina inferior izquierda.
Cuando haga clic en el botón, mueva el control deslizante un paso hacia la derecha

slider++; 

A continuación, verificamos: hemos llegado al final de la matriz (luego saltamos al principio), luego comparamos (intercambiamos) elementos vecinos


Processing.js utiliza estructuras de datos Java, luego el código se traduce a javascript ( enlace ), por lo que la declaración de una matriz de instancias de la clase Módulo, que es responsable de representar elementos e inicializar las instancias, ocurre de esta manera

La función principal de dibujar void draw () es un ciclo infinito en el que se clasifican las instancias de clase

 for (Module mod : mods) { mod.display(); } 

Agregue la función randFoo () , que devuelve valores aleatorios. Para garantizar que los valores no se repitan, los agregaremos a ArrayLis t en la lista listRand , y en la función randFoo () , verificaremos si el nuevo número aleatorio está en la lista listRand

 int randFoo(){ newRand = int(random(1,11)); if(!listRand.contains(newRand) ) listRand.add(newRand ); else newRand=randFoo(); return newRand; } 

→ Consultar aquí

Ordenar píxeles

La clasificación de píxeles (aquí) es una implementación de la clasificación de burbujas.
Desplazaremos los píxeles más cálidos / claros a un lado y los más oscuros / fríos al otro.

 void draw(){ while (i <= height) { c=get(i,j); //    cTemp=c; //      i++; //     c=get(i,j); //     if(cTemp>c) { //   fill(c); //    rect(i-1,j,1,1); fill(cTemp); rect(i,j,1,1); } } if(mousePressed) { if(j>=width) j=0; } //      if(i >= height) {j++; i=0;} } 

→ Consultar aquí
Para comenzar a ordenar, haga clic en la imagen y mantenga presionado el botón.
Puedes leer más sobre los tipos de píxeles aquí .
Video sobre la clasificación de píxeles en el canal oficial The Coding Train aquí

Limitador y bandera

Puede reducir el número de iteraciones si no itera sobre elementos ya ordenados. Para hacer esto, agregue un limitador al final de la matriz, que cambiará al comienzo de la matriz después de cada iteración

 if(slider>=limiter) { slider=1; limiter--; if(limiter<1) limiter=1; } 

→ Consultar aquí

Otra forma de reducir el número de bustos se puede encontrar en el artículo Bubble Sort (Wikipedia). Si durante el paso de la matriz nunca cambiamos los elementos vecinos, la matriz se ordena y el ciclo puede completarse (condición de Iverson ).

Agregue una bandera de bandera , que se eleva cuando nos encontramos con un par de elementos que deben intercambiarse. Si se levanta la bandera, repita nuevamente la matriz. Si no, finalice el ciclo. El estado de la bandera se muestra en la consola.



→ Consultar aquí

Si coloca un limitador a la izquierda y usa un elemento con un limitador como referencia / mínimo, obtenemos la clasificación por selección.

Agregue la variable min a la que se cargará el valor mínimo. Supongamos que inicialmente el elemento más a la izquierda es mínimo: durante el primer paso de la matriz, si un elemento es menor que el mínimo, entonces guardamos este elemento en la variable min

 if(mods[slider-1].rectHight < min){ min=mods[slider-1].rectHight; } 

luego intercambie el primer elemento y el mínimo

 if (mods[limiterL-1].rectHight>min) { vTemp= mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=mods[slider-1].rectHight; mods[slider-1].rectHight=vTemp; } 

Si el control deslizante alcanza el borde derecho de la matriz, entonces el limitador se mueve un paso hacia la derecha, y el control deslizante se mueve hacia el limitador

 if(slider==moduleSize){ if(limiterL<moduleSize) limiterL++; min=mods[limiterL-1].rectHight; incPaddle=limiterL-1; } 

→ Consultar aquí
El número de medidas se puede reducir si al principio de la búsqueda comparamos (intercambiamos) el elemento actual y el elemento más a la derecha de la matriz

 if(mods[limiterL-1].rectHight>mods[moduleSize-1].rectHight) { vTemp=mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=mods[moduleSize-1].rectHight; mods[moduleSize-1].rectHight=vTemp; } 

Entonces no puede verificar el elemento más a la derecha de la matriz

 //if(slider==moduleSize){ if(slider==moduleSize-1){ //if(limiterL<moduleSize) limiterL++; limiterL++; min=mods[limiterL-1].rectHight; slider=limiterL-1; } // slider++; if(slider<moduleSize) slider++; 

→ Consultar aquí

Aquí puede agregar la clasificación de la parte derecha de la matriz en orden descendente agregando el elemento máximo máximo : obtenemos la clasificación del agitador por selección. Vea la sección sobre clasificación de agitadores al final del artículo.

Ordenación rápida

El mecanismo de selección del elemento de soporte también se utiliza en la clasificación rápida. Este algoritmo implica la selección del elemento de referencia inicial con el que se comparan todos los demás elementos de la matriz. El tiempo de ejecución del algoritmo depende de la elección del elemento inicial. En el gif de arriba, el elemento inicial es el número 3 . Puede leer más sobre cómo elegir el elemento de soporte inicial en el artículo (Wikipedia).
En el canal oficial de youtube del procesamiento y los idiomas de p5.js hay un video sobre la clasificación rápida . Aquí puede ver la visualización del algoritmo.
Si el primer elemento es básico, puede insertar elementos más pequeños que el básico frente a él, entonces la matriz se dividirá en dos partes, los elementos de la izquierda serán más pequeños que los básicos, a la derecha, más. Para tal método, consulte la sección sobre clasificación por insertos a continuación.

Ordenamiento enano

Esencialmente, el gnomo mira las macetas de jardín siguientes y anteriores: si están en el orden correcto, avanza una maceta, de lo contrario las intercambia y retrocede una maceta.

Después de levantar la bandera, guarde la coordenada del control deslizante en el limitador variableR y regrese el control deslizante al comienzo de la matriz en pasos

 slider--; 

Una vez al comienzo de la matriz, restablezca la bandera y coloque el control deslizante en la celda con la coordenada que guardamos en el limitador variableR

 if(slider==0){ flag=false; slider=limiterR; } 

→ Consultar aquí

Al cambiar este algoritmo, obtenemos " ordenar por inserciones ".
Al ordenar por inserciones, se selecciona el elemento de referencia / mínimo, luego, en la parte no ordenada de la matriz, se selecciona un elemento que es más pequeño que la referencia y se inserta antes de la referencia

Tengamos los lugares de intercambio de elementos mínimos con los anteriores, hasta el de referencia, y así sucesivamente. insertado delante de la referencia.
Agregar una condición

 if(slider==limiterR-1 && mods[slider-1].rectHight<mods[limiterR-1].rectHight){ flag=false; slider=limiterR; } 

→ Consultar aquí


Clasificación de inserción "rápida"

En este algoritmo, la matriz se divide en dos partes por el elemento de soporte.
Deje que el primer elemento sea la referencia: compare, comenzando por el segundo, los elementos de la matriz con la referencia, si un elemento es más pequeño que la referencia

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight) 

inserte el elemento encontrado antes de la referencia

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight){ flag=true; //   vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[slider-2].rectHight; mods[slider-2].rectHight=vTemp; } 

Si se levanta la bandera, mueva el control deslizante hacia la izquierda en pasos hasta que encontremos el elemento de soporte

 if(flag){ slider--; if(slider<pivot){ flag=false; //   pivot++; slider=pivot; } } 

T.O. la matriz se divide en dos partes, a la izquierda - los elementos son más pequeños que la referencia, a la derecha - más

→ Consultar aquí

Si, después de cada enumeración, las coordenadas del elemento de soporte se guardan en ext. matriz pivotsArr , luego, cuando el elemento de referencia alcanza el borde derecho, obtenemos una matriz ordenada por nivel / paso. Los elementos en cada nivel siguiente serán más grandes que los elementos en el nivel anterior. Los límites de los niveles estarán contenidos en add. pivotsArr array
Cada vez que presione el botón, enviaremos la matriz pivotsArr a la consola

 for(int i=0;i<pivotsArr.length;i++){ print(" "); print(pivotsArr[i]); print(" "); } 

Agregue la función aleatoria randFoo () al final del programa.

→ Consultar aquí

Ahora necesita ordenar los elementos de cada nivel por separado (solo queda agregar la condición para finalizar el ciclo)

→ Consultar aquí
Esta clasificación se puede describir como clasificación por nivel.
, porque después de cada enumeración, los datos numéricos se organizan en niveles, los números de cada nivel siguiente exceden los números en el anterior.

Clasificación impar-par

Vamos a mover el control deslizante por dos pasos, comparando elementos vecinos

 slider=slider+2; 

T.O. comparamos los elementos 0 y 1, 2 y 3, 4 y 5, 6 y 7, etc.
Si el control deslizante alcanza el borde de la matriz, deje que el limitador se mueva un paso hacia la izquierda, y el control deslizante se mueva al comienzo de la matriz.
A continuación, comparamos los elementos 1 y 2, 3 y 4, 5 y 6, 7 y 8, etc.
Al llegar al limitador, lo desplazamos un paso hacia la derecha, colocamos el control deslizante al comienzo de la matriz.

→ Consultar aquí

Ordenar el cepillo para el cabello

Deje que el control deslizante esté al principio de la matriz y el delimitador derecho al final. Comparar (intercambiar) elementos. Movimos el limitador un paso hacia la izquierda y guardamos su índice en la variable limiterStore

 if(limiter==moduleSize) { limiter = limiterStore-1; limiterStore = limiter; slider=1; } 

Mueva el control deslizante con la parada hasta el final de la matriz en pasos

 if(limiter!=moduleSize) { //  limiter     limiter++; slider++; } 

Habiendo llegado al final de la matriz como un limitador, coloque el control deslizante al comienzo de la matriz y coloque el limitador en limiterStore-1

 if(limiter==moduleSize) { limiter = limiterStore-1; limiterStore = limiter; slider=1; } 

→ Consultar aquí

Tipo de agitador

Agregue el limitador izquierdo limitadorL al comienzo de la matriz.
Deje que la bandera se levante cuando el control deslizante llegue al limitador derecho limitadorR, luego el limitador se mueve un paso hacia la izquierda. Además, cuando se levanta la bandera, el control deslizante se mueve en pasos hacia el limitador izquierdo limitador L - el limitador se mueve un paso hacia la derecha - el control deslizante se mueve en pasos hacia la derecha


→ Consultar aquí

Agitador ordenar por elección
Agregue al tipo de burbuja con el limitador derecho el limitador izquierdo. En cada desplazamiento del control deslizante hacia la derecha, verificamos (intercambio), que es mayor: el elemento actual o el limitador

 if(mods[slider-1].rectHight<mods[limiterL-1].rectHight){ vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=vTemp; } 

Cuando el control deslizante alcanza el limitador derecho limitadorR, el limitador derecho se mueve un paso hacia la izquierda, el limitador izquierdo se mueve un paso hacia la derecha, el control deslizante vuelve al limitador izquierdo

 if(slider>=limiterR){ limiterL++; slider=limiterL; limiterR--; } 

→ Consultar aquí

PD Aquí es donde se describe una aplicación que hace que el estudio de algoritmos y estructuras de datos sea mucho más interesante .
Otra visualización de una serie de algoritmos y estructuras de datos.
Este artículo menciona otro sitio donde puede ver cómo se ordenan los datos por diferentes algoritmos.
Este artículo ofrece una evaluación de la complejidad de la clasificación de burbujas.
Puede leer más sobre la evaluación de la complejidad aquí , aquí , aquí , aquí .