Módulo de funciones con clasificación de burbujas. Clasificación de burbujas
Todo el mundo sabe muy bien que, dentro de la clase de tipos de cambio, el método más rápido es el llamado clasificación rápida. Se escriben disertaciones al respecto, se le dedican muchos artículos sobre Habré y se inventan complejos algoritmos híbridos basados en él. Pero hoy no hablaremos de clasificación rápida, y sobre otro método de intercambio: el viejo y bueno. clasificación de burbujas y sus mejoras, modificaciones, mutaciones y variaciones.
Los beneficios prácticos de estos métodos no son tan grandes y muchos usuarios de habra pasaron por todo esto en primer grado. Por tanto, el artículo está dirigido a quienes acaban de interesarse por la teoría de los algoritmos y están dando sus primeros pasos en esta dirección.
imagen: burbujas
Hoy hablaremos de lo más sencillo. clasificaciones de intercambio.
Si alguien está interesado, diré que hay otras clases. clasificación de selección, clasificación por inserción, fusionar ordenar, clasificación de distribución, tipos híbridos Y tipos paralelos. Por cierto, también hay clasificaciones esotéricas. Se trata de varios pseudoalgoritmos cómicos y de otro tipo falsos, fundamentalmente irrealizables, sobre los cuales escribiré un par de artículos en el centro "Humor de TI".
Pero esto no tiene nada que ver con la conferencia de hoy; ahora sólo nos interesan las clasificaciones de intercambio simples. También hay muchas clasificaciones de intercambio (conozco más de una docena), por lo que consideraremos las llamadas clasificación de burbujas y algunos otros estrechamente relacionados con él.
Le advertiré de antemano que casi todos los métodos anteriores son muy lentos y no habrá un análisis en profundidad de su complejidad temporal. Algunos son más rápidos, otros más lentos, pero en términos generales podemos decir que en promedio oh(norte 2). Además, no veo ninguna razón para saturar el artículo con implementaciones en ningún lenguaje de programación. Los interesados pueden encontrar fácilmente ejemplos de código en Rosetta, Wikipedia o en otros lugares.
Pero volvamos a clasificar los intercambios. El orden se produce como resultado de la iteración secuencial repetida de la matriz y la comparación de pares de elementos entre sí. Si los elementos que se comparan no están ordenados entre sí, los intercambiamos. La única pregunta es cómo omitir exactamente la matriz y sobre qué base seleccionar pares para comparar.
No comencemos con la clasificación de burbujas estándar, sino con un algoritmo llamado...
tipo estúpido
Ordenar es realmente estúpido. Miramos la matriz de izquierda a derecha y comparamos los vecinos a lo largo del camino. Si encontramos un par de elementos mutuamente desordenados, los intercambiamos y volvemos al punto de partida, es decir, al principio. Revisamos y verificamos la matriz nuevamente, si nuevamente encontramos un par de elementos vecinos "incorrectos", cambiamos de lugar y comenzamos de nuevo. Seguimos hasta ir ordenando el array poco a poco.“Cualquier tonto puede hacer algo así”, dirás, y tendrás toda la razón. Por eso la clasificación se llama "estúpida". En esta conferencia mejoraremos y modificaremos constantemente este método. Ahora tiene dificultades temporales. oh(norte 3), habiendo hecho una corrección, ya la llevaremos a oh(norte 2), luego lo aceleraremos un poco más, luego un poco más, y al final obtendremos oh(norte registro norte) – ¡y no será “Clasificación rápida” en absoluto!
Hagamos una única mejora a la estúpida clasificación. Habiendo descubierto dos elementos adyacentes sin clasificar durante el pasaje y los intercambiamos, no retrocederemos al principio de la matriz, sino que continuaremos recorriéndola tranquilamente hasta el final.
En este caso, no tenemos ante nosotros nada más que el conocido...
clasificación de burbujas
O clasificación por intercambios simples. Un clásico inmortal del género. El principio de funcionamiento es simple: recorremos la matriz de principio a fin, intercambiando simultáneamente elementos vecinos sin clasificar. Como resultado de la primera pasada, el elemento máximo "flotará" hasta el último lugar. Ahora recorremos nuevamente la parte no ordenada de la matriz (desde el primer elemento hasta el penúltimo) y cambiamos los vecinos no clasificados a lo largo del camino. El segundo elemento más grande ocupará el penúltimo lugar. Continuando con el mismo espíritu, atravesaremos la parte cada vez menor y sin clasificar de la matriz, empujando los máximos encontrados hasta el final.Si no sólo llevamos los máximos hasta el final, sino que también empujamos los mínimos hasta el principio, entonces lo lograremos...
Clasificación por agitador
ella es la misma ordenar aleatoriamente, ella es la misma clasificación de cócteles. El proceso comienza como en una “burbuja”: exprimimos el máximo hasta el fondo. Después de esto, giramos 180 0 y vamos en la dirección opuesta, mientras volvemos al principio no al máximo, sino al mínimo. Habiendo ordenado el primer y último elemento de la matriz, volvemos a dar un salto mortal. Después de ir y venir varias veces, finalmente finalizamos el proceso y terminamos en el medio de la lista.La clasificación por agitador funciona un poco más rápido que la clasificación por burbujas, ya que tanto los máximos como los mínimos migran alternativamente a través de la matriz en las direcciones requeridas. Las mejoras, como dicen, son obvias.
Como puede ver, si aborda el proceso de enumeración de manera creativa, el desplazamiento de elementos pesados (ligeros) hacia los extremos de la matriz es más rápido. Por lo tanto, los artesanos propusieron otra “hoja de ruta” no estándar para sortear la lista.
Clasificación par-impar
Esta vez no correremos de un lado a otro a lo largo de la matriz, sino que volveremos nuevamente a la idea de un recorrido sistemático de izquierda a derecha, pero solo daremos un paso más amplio. En la primera pasada, los elementos con clave impar se comparan con sus vecinos en lugares pares (el 1.º se compara con el 2.º, luego el 3.º con el 4.º, el 5.º con el 6.º, y así sucesivamente). Luego, por el contrario, comparamos/cambiamos elementos “pares” por “impares”. Luego nuevamente “par-impar”, luego nuevamente “par-impar”. El proceso se detiene cuando, después de dos pasos consecutivos por el conjunto (“par-impar” y “par-impar”), no se ha producido ni un solo intercambio. Entonces lo solucionaron.En una “burbuja” normal, durante cada pasada exprimimos sistemáticamente el máximo actual hasta el final de la matriz. Si salta a lo largo de índices pares e impares, todos los elementos más o menos grandes de la matriz se empujan simultáneamente hacia la derecha una posición en una sola ejecución. Funciona más rápido de esta manera.
Veamos el último redecorado* Para Sortuvannya bulbashka** - Ordenar por peine***. Este método se organiza muy rápidamente, oh(norte 2) es su peor dificultad. En promedio a lo largo del tiempo tenemos oh(norte registro norte), y lo mejor, ni lo vas a creer, oh(norte). Es decir, un competidor muy digno de todo tipo de "tipos rápidos" y esto, claro está, sin el uso de la recursividad. Sin embargo, prometí que hoy no profundizaremos en las velocidades de crucero, así que dejaré de hablar y pasaré directamente al algoritmo.
Todo es culpa de las tortugas.
Un poco de historia. En 1980, Włodzimierz Dobosiewicz explicó por qué la clasificación de burbujas y sus derivados funcionan tan lentamente. Todo es por las tortugas.. Las “tortugas” son pequeños elementos que se ubican al final de la lista. Como habrás notado, los tipos de burbujas se centran en los "conejos" (que no deben confundirse con los "conejos" de Babushkin): elementos de gran valor al principio de la lista. Se mueven muy rápidamente hacia la meta. Pero los lentos reptiles se arrastran hasta el principio a regañadientes. Puedes personalizar la tortilla usando peines.imagen: tortuga culpable
Clasificación de peine
En "burbuja", "agitador" y "par-impar", cuando se itera a través de una matriz, se comparan los elementos vecinos. La idea principal del "peine" es tomar inicialmente una distancia suficientemente grande entre los elementos que se comparan y, a medida que se ordena la matriz, reducir esta distancia al mínimo. De esta manera, peinamos la matriz, alisándola gradualmente en hebras cada vez más ordenadas.Es mejor tomar la brecha inicial entre los elementos comparados no cualquiera, sino teniendo en cuenta un valor especial llamado factor reductor, cuyo valor óptimo es aproximadamente 1,247. Primero, la distancia entre elementos es igual al tamaño de la matriz dividido por factor de reducción(el resultado, por supuesto, se redondea al número entero más cercano). Luego, después de recorrer la matriz con este paso, volvemos a dividir el paso entre factor de reducción y revise la lista nuevamente. Esto continúa hasta que la diferencia del índice llega a uno. En este caso, la matriz se ordena mediante una burbuja normal.
El valor óptimo ha sido establecido experimental y teóricamente. factor de reducción:
Cuando se inventó este método, pocas personas le prestaron atención a finales de los años 70 y 80. Una década más tarde, cuando la programación ya no era competencia de los científicos e ingenieros de IBM, sino que ya estaba ganando rápidamente popularidad masiva, el método fue redescubierto, investigado y popularizado en 1991 por Stephen Lacy y Richard Box.
En realidad, eso es todo lo que quería contarles sobre la clasificación de burbujas y otros similares.
- Notas
* abreviado ( ucranio) - mejora
** Ordenado por bombilla ( ucranio) – Clasificación de burbujas
*** Clasificación por peine ( ucranio) – Clasificación de peines
Se ha estimado que hasta una cuarta parte del tiempo que los ordenadores centralizados dedican a clasificar datos. Esto se debe a que es mucho más fácil encontrar un valor en una matriz que ha sido ordenada previamente. De lo contrario, la búsqueda es un poco como buscar una aguja en un pajar.
Hay programadores que dedican todo su tiempo de trabajo a estudiar e implementar algoritmos de clasificación. Esto se debe a que la gran mayoría del software empresarial implica la gestión de bases de datos. La gente busca información en bases de datos todo el tiempo. Esto significa que los algoritmos de búsqueda tienen una gran demanda.
Pero hay un "pero". Los algoritmos de búsqueda funcionan mucho más rápido con bases de datos que ya están ordenadas. En este caso, sólo se requiere una búsqueda lineal.
Si bien las computadoras se quedan sin usuarios en algunos momentos, los algoritmos de clasificación continúan operando en las bases de datos. Los buscadores vuelven y la base de datos ya está ordenada según uno u otro propósito de búsqueda.
Este artículo proporciona ejemplos de implementaciones de algoritmos de clasificación estándar.
Orden de selección
Para ordenar una matriz en orden ascendente, debe encontrar el elemento con el valor más grande en cada iteración. Con él necesitas intercambiar el último elemento. El siguiente elemento con el valor más alto se coloca en el penúltimo lugar. Esto debería suceder hasta que los elementos en los primeros lugares de la matriz estén en el orden correcto.
código C ++
void SortAlgo::selectionSort(int data, int lenD) ( int j = 0; int tmp = 0; for (int i=0; i
datos[i] = datos[j];
datos[j] = tmp;
código C ++
) ) void SortAlgo::bubbleSort(int data, int lenD) ( int tmp = 0; for (int i = 0;i =(i+1);j--)( si (datos[j] Orden de inserción código C ++
La ordenación por inserción divide la matriz en dos regiones: ordenada y desordenada. Inicialmente, toda la matriz es una región desordenada. En la primera pasada, el primer elemento de la región desordenada se elimina y se coloca en la posición correcta en la región ordenada. código C ++
void SortAlgo::mergeSort(int data, int lenD) ( if (lenD>1)( int middle = lenD/2; int rem = lenD-middle; int * L = nuevo int; int * R = nuevo int; for ( int i=0;i Quicksort utiliza un algoritmo de divide y vencerás. Comienza dividiendo la matriz original en dos regiones. Estas partes están a la izquierda y a la derecha del elemento marcado, llamado soporte. Al final del proceso, una parte contendrá elementos más pequeños que la referencia y la otra parte contendrá elementos más grandes que la referencia. código C ++
void SortAlgo::quickSort(int * data, int const len) ( int const lenD = len; int pivot = 0; int ind = lenD/2; int i,j = 0,k = 0; if (lenD>1) ( int * L = nuevo int ; int * R = nuevo int ; pivote = datos; para (i=0;i Un algoritmo para ordenar una matriz unidimensional utilizando el método de la "burbuja". Descripción del algoritmo. Diagrama de bloques y programa para ordenar en orden ascendente una matriz de tipo realde 7 elementos. Descripción del algoritmo La clasificación de los métodos de clasificación no siempre está claramente definida. Detengámonos en el método en el que el intercambio de dos elementos es la principal característica del proceso. El algoritmo de clasificación de intercambio simple a continuación se basa en el principio comparacionesYintercambio pares de elementos adyacentes hasta que todos los elementos estén ordenados. Al igual que con los métodos de selección simples anteriores, hacemos pases repetidos a través de la matriz, cada vez examinando el elemento más pequeño del conjunto restante, moviéndonos hacia el extremo izquierdo de la matriz. Si, para variar, consideramos la matriz verticalmente en lugar de horizontalmente y, con un poco de imaginación, imaginamos los elementos como burbujas en un tanque de agua, con "pesos" correspondientes a sus claves, entonces cada paso a través de la matriz da como resultado una burbuja "flotante" hasta un nivel correspondiente a su peso (ver Tabla 2). Este método se conoce comúnmente como clasificación de burbujas. Su versión más simple se muestra en el Programa 1. procedimiento
ordenar burbujas; var i,
j: índice;
incógnita: artículo; comenzar para
i := 2 a
norte hacer comenzar por j
:= norte
hasta i
hacer si a[j-1].llave
> a[j].llave
entonces comenzar incógnita
:= a[j-1];
a[j-1]
:= a[j];
a[j]
:= incógnita fin{ordenar burbujas} Este algoritmo es fácil de optimizar. Ejemplo en tabla. La Figura 2 muestra que las últimas tres pasadas no afectan de ninguna manera el orden de los elementos, ya que ya están ordenados. Una forma obvia de mejorar este algoritmo es recordar si se produjo algún intercambio en un pase determinado. De lo contrario, esto significa que el algoritmo puede continuar si recuerda no solo el hecho del intercambio, sino también el lugar (índice) del último intercambio. Después de todo, está claro que todos los pares de elementos vecinos con índices menores que este índice k, ya están ordenados en el orden correcto. Por lo tanto, los pases posteriores pueden finalizar en este índice, en lugar de pasar a un límite inferior predeterminado. i. Sin embargo, un programador atento notará una extraña asimetría aquí: una única "burbuja" mal colocada en el extremo "pesado" de la matriz ordenada flotará en su lugar en una sola pasada, pero un elemento mal colocado en el extremo "ligero" flotará en el lugar correcto con solo un paso en cada pasada. Por ejemplo, matriz 12 18 42 44 55 67 94 06 se ordenará utilizando el método de la burbuja en una sola pasada y ordenando una matriz 94 06 12 18 42 44 55 67 requerirá siete pases. Esta asimetría antinatural sugiere una tercera mejora: cambiar la dirección de pasajes sucesivos. Análisis de clasificación de burbujas. El número de comparaciones en el algoritmo de intercambio simple es los números mínimo, promedio y máximo de transferencias (asignaciones de elementos) son iguales Programaclasificación A: conjunto de reales; N, j, k: número entero; WriteLn("Matriz de entrada"); para j:= 1 a N hacer Escribir("A", j, "="); WriteLn("Matriz fuente"); para j:= 1 a N hacer Escribir(A[j]:8:1); para j:= 2 a k hacer si A > A[j] entonces A := A[j]; WriteLn("Matriz ordenada"); para j:= 1 a N hacer Escribir(A[j]:8:1); No sólo no se considera el método más rápido, sino que además cierra la lista de los métodos de pedido más lentos. Sin embargo, también tiene sus ventajas. Por lo tanto, la clasificación de burbujas es la solución más lógica y natural al problema si necesita organizar elementos en un orden determinado. Una persona corriente, por ejemplo, lo utilizará manualmente, simplemente por intuición. El nombre del método se inventó por analogía con las burbujas de aire en el agua. Esta es una metáfora. Así como pequeñas burbujas de aire suben a la superficie; después de todo, su densidad es mayor que la de cualquier líquido (en este caso, agua), cada elemento de la matriz, cuanto menor es en valor, más gradualmente hace su camino al comienzo de la lista de números. La clasificación de burbujas funciona así: Aún más brevemente, el algoritmo del futuro programa se puede escribir de la siguiente manera: La implementación más simple es la siguiente: Procedimiento Sortirovka_Puzirkom;
Comenzar
bucle para j de índice_inicial a índice_konechii;
bucle para i de índice_inicial a konechii_index-1;
Si masivo[i]>masivo (intercambiar los valores); Fin
Por supuesto, aquí la simplicidad sólo agrava la situación: cuanto más simple es el algoritmo, más defectos aparecen en él. El consumo de tiempo es demasiado grande incluso para una matriz pequeña (aquí entra en juego la relatividad: para una persona promedio, la cantidad de tiempo puede parecer pequeña, pero en el negocio de un programador, cada segundo o incluso milisegundo cuenta). Se necesitaba una mejor implementación. Por ejemplo, teniendo en cuenta el intercambio de valores en una matriz: Procedimiento Sortirovka_Puzirkom;
Comenzar
sortírovka
= verdadero; ciclo hasta ahora sortírovka
= verdadero;
sortírovka
= falso;
bucle para i de índice_inicial a konechii_index-1;
Si masivo[i]>masivo(el primer elemento es mayor que el segundo), entonces: (intercambiar elementos); sortírovka
= verdadero; (indicó que se realizó el intercambio).
Fin.
La principal desventaja es la duración del proceso. ¿Cuánto tiempo se tarda en hacer una burbuja? El tiempo de ejecución se calcula a partir del cuadrado del número de números en la matriz; el resultado final es proporcional a él. En el peor de los casos, la matriz se recorrerá tantas veces como elementos contenga menos un valor. Esto sucede porque eventualmente solo queda un elemento sin nada con qué comparar, y el último paso por la matriz se convierte en una acción inútil. Además, el método de clasificación por intercambio simple, como también se le llama, sólo es eficaz para matrices pequeñas. No será posible procesar grandes cantidades de datos con su ayuda: el resultado serán errores o fallas del programa. La clasificación de burbujas es bastante sencilla de entender. En los planes de estudio de las universidades técnicas, cuando se estudia el orden de los elementos de una matriz, se trata primero. El método se implementa fácilmente tanto en el lenguaje de programación Delphi (D) como en C/C++ (C/C plus plus), un algoritmo increíblemente simple para organizar valores en el orden correcto, y Bubble Sort es ideal para principiantes. Debido a sus deficiencias, el algoritmo no se utiliza con fines extracurriculares. Vista inicial del array 8 22 4 74 44 37 1 7 Paso 1 8 22 4 74 44 37 1 7 8 22 4 74 44 1 37 7 8 22 4 74 1 44 37 7 8 22 4 1 74 44 37 7 8 22 1 4 74 44 37 7 8 1 22 4 74 44 37 7 1 8 22 4 74 44 37 7 Paso 2 1 8 22 4 74 44 7 37 1 8 22 4 74 7 44 37 1 8 22 4 7 74 44 37 1 8 22 4 7 74 44 37 1 8 4 22 7 74 44 37 1 4 8 22 7 74 44 37 Paso 3 1 4 8 22 7 74 37 44 1 4 8 22 7 37 74 44 1 4 8 22 7 37 74 44 1 4 8 7 22 37 74 44 1 4 7 8 22 37 74 44 Paso 4 1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 Paso 5 1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 Paso 6 1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 Paso 7 1 4 7 8 22 37 44 74 Ejemplo: const kol_mas=10; var matriz:matriz de números enteros; a, b, k: número entero; writeln("entrada", kol_mas, "elementos de la matriz"); para a:=1 a kol_mas haga readln(array[a]); para a:=1 a kol_mas-1 comienza para b:=a+1 hasta kol_mas comienza si massiv[a]>massiv[b] entonces comienza k:=matriz[a]; masivo[a]:=masivo[b]; matriz[b]:=k; fin; writeln("después de ordenar"); para a:=1 a kol_mas hacer writeln(massiv[a]); #incluir #incluir int principal(int argc, char* argv) int masivo = (36, 697, 73, 82, 68, 12, 183, 88),i, ff; para (; ;)( ff = 0; para (i = 7; i>0; i--)( si (matriz[i]< massiv) {
intercambiar(matriz[i],masivo); si (ff == 0) romper; obtener(); // retraso de pantalla Cuando se trabaja con matrices de datos, a menudo surge la tarea ordenar en orden ascendente o descendente, es decir, ordenar. Esto significa que los elementos de la misma matriz deben estar ordenados estrictamente. Por ejemplo, en el caso de ordenación ascendente, el elemento anterior debe ser menor (o igual) que el siguiente. Hay muchos métodos de clasificación. Algunos de ellos son más eficaces, otros son más fáciles de entender. Lo suficientemente simple de entender es ordenar método de burbuja, que también se llama método de intercambio simple. ¿Qué es y por qué tiene un nombre tan extraño: “método de la burbuja”? Como sabes, el aire es más ligero que el agua, por eso las burbujas de aire flotan. Es sólo una analogía. En la clasificación de burbujas ascendentes, los elementos más livianos (de menor valor) "flotan" gradualmente hasta el comienzo de la matriz, y los más pesados, uno tras otro, caen al fondo (hasta el final de la matriz). Programa Pascal: constante metro = 10 ; var arr: matriz [1 .. m] de número entero; i, j, k: número entero; comenzar a aleatorizar; escribir(La clasificación de burbujas compara elementos adyacentes e intercambia lugares si el siguiente elemento es más pequeño que el anterior. Se requieren múltiples pases a través de los datos. Durante la primera pasada, se comparan los dos primeros elementos de la matriz. Si no están en orden, se intercambian y luego se comparan los elementos del siguiente par. Bajo la misma condición, también cambian de lugar. Por tanto, la clasificación se produce en cada ciclo hasta llegar al final de la matriz.
Combinar ordenar
clasificación rápida
Ejemplo de clasificación de burbujas
Clasificación de burbujas
,
,
,
.Diagrama de flujo de clasificación de burbujas.
¿De dónde surgió un nombre tan inusual?
Descripción del algoritmo
Pseudocódigo basado en el algoritmo descrito.
Desventajas del método.
Ventajas
Principio de clasificación visual
Ejemplo de clasificación de burbujas en Pascal
Ejemplo de clasificación de burbujas en lenguaje C
Solución
El algoritmo y las características de esta clasificación son los siguientes:
![para i: = 1 a m- 1 hacer para j: = 1 a m- hago si arr[ j] loading=lazy> arr[ j+ 1 ] entonces comenzar k : = arr[ j] ;](/uploads/5be8b76667696c4cd63a8c38979b50af.jpg)
![arr[ j+ 1 ] : = k fin ;](/uploads/33b72e60e1d3066a9663f391221dc014.jpg)
