Tipo de burbuja si. Ordenamiento de burbuja. Y aquí está el video tutorial.

Cuando se trabaja con matrices de datos, no es infrecuente que ordenar en orden ascendente o descendente, es decir racionalización... Esto significa que los elementos de la misma matriz deben organizarse estrictamente en orden. Por ejemplo, en el caso de un orden ascendente, el elemento anterior debe ser menor (o igual) que el siguiente.

Solución

Hay muchos métodos de clasificación. Algunos de ellos son más efectivos, otros son más fáciles de entender. La clasificación es bastante fácil de entender. método de burbuja también llamado por simple intercambio... ¿Qué es y por qué tiene un nombre tan extraño: "método burbuja"?

Como sabes, el aire es más liviano que el agua, por lo que las burbujas de aire flotan. Esto es solo una analogía. En la clasificación de burbujas en orden ascendente, los elementos más ligeros (con un valor más bajo) "flotan" gradualmente hasta el principio de la matriz, mientras que los más pesados descienden uno tras otro hasta la parte inferior (hasta el final de la matriz).

El algoritmo y las características de esta clasificación son los siguientes:

Durante el primer paso a través de la matriz, los elementos se comparan en pares: el primero con el segundo, luego el segundo con el tercero, luego el tercero con el cuarto, etc. Si el elemento anterior es más grande que el siguiente, se intercambian.
No es difícil adivinar que gradualmente el mayor número resulta ser el último. El resto de la matriz permanece sin clasificar, aunque se observa algún movimiento de elementos con un valor menor al comienzo de la matriz.
En la segunda pasada, no es necesario comparar el último elemento con el penúltimo. El último elemento ya está en su lugar. Esto significa que el número de comparaciones será una menos.
En la tercera pasada, ya no es necesario comparar el penúltimo y tercer elemento desde el final. Por tanto, el número de comparaciones será dos menos que en la primera pasada.
Después de todo, cuando se recorre una matriz, cuando solo quedan dos elementos para comparar, solo se realiza una comparación.
Después de eso, el primer elemento no tiene nada con qué comparar y, por lo tanto, el último paso a través de la matriz es innecesario. En otras palabras, el número de pasadas a través del arreglo es igual a m-1, donde m es el número de elementos del arreglo.
El número de comparaciones en cada paso es m-i, donde i es el número del paso a través de la matriz (primera, segunda, tercera, etc.).
Cuando se intercambian elementos de matriz, se suele utilizar una variable "búfer" (tercera), donde se coloca temporalmente el valor de uno de los elementos.

Programa Pascal:

constante m = 10; var arr: matriz [1 .. m] de entero; i, j, k: número entero; comenzar a aleatorizar; escribir ( "Matriz de origen:"); para i: = 1 am comience arr [i]: = aleatorio (256); escribir (arr [i]: 4); fin; Writeln; Writeln; para i: = 1 a m- 1 hacer para j: = 1 a m- yo hago si arr [j]> arr [j + 1] entonces comienza k: = arr [j]; arr [j]: = arr [j + 1]; arr [j + 1]: = k final; escribir ( "Matriz ordenada:"); para i: = 1 para m escribir (arr [i]: 4); Writeln; readln end.

Detalles Categoría: Ordenar y buscar

Bubble Sort (Exchange Sort) es un algoritmo de clasificación ineficaz y fácil de implementar. El método fue estudiado como uno de los primeros en el curso de la teoría de algoritmos, mientras que en la práctica se usa muy raramente.

El algoritmo consta de pasadas repetidas a través de la matriz que se va a clasificar. Para cada pasada, los elementos se comparan secuencialmente en pares, y si el orden en el par es incorrecto, los elementos se intercambian. Los pases a través de la matriz se repiten una vez o hasta que en la siguiente pasada resulta que los intercambios ya no son necesarios, lo que significa que la matriz está ordenada. Con cada pasada del algoritmo a través del ciclo interno, el siguiente elemento más grande de la matriz se coloca en su lugar al final de la matriz junto al "elemento más grande" anterior, y el elemento más pequeño se mueve una posición al comienzo de la array ("flota" a la posición deseada como una burbuja en el agua, de ahí el nombre del algoritmo).

Peor momento
El mejor momento
Tiempo promedio
Costo de memoria

Un ejemplo de cómo funciona el algoritmo

Tome una matriz de números "5 1 4 2 8" y ordene los valores en orden ascendente usando la clasificación de burbujas. Se destacan los elementos que se comparan en esta etapa.

Primer pase:

(5 1 4 2 8) (1 5 4 2 8), aquí el algoritmo compara los dos primeros elementos y los intercambia. (1 5 4 2 8) (1 4 5 2 8), cambia porque (1 4 5 2 8) (1 4 2 5 8), intercambia lugares desde (1 4 2 5 8 ) (1 4 2 5 8 ), Ahora, dado que los elementos están en sus lugares (), el algoritmo no los intercambia.

Segunda pasada:

(1 4 2 5 8) (1 4 2 5 8) (1 4 2 5 8) (1 2 4 5 8), cambia porque (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8 ) (1 2 4 5 8 )

La matriz ahora está completamente ordenada, pero el algoritmo no sabe si este es el caso. Por lo tanto, necesita hacer un pase completo y determinar que no hubo permutaciones de elementos.

Tercer pase:

(1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8) (1 2 4 5 8 ) (1 2 4 5 8 )

La matriz ahora está ordenada y el algoritmo se puede completar.

Implementación del algoritmo en varios lenguajes de programación:

Sintaxis de Intel

Mov bx, matriz de desplazamiento mov cx, n for_i: dec cx xor dx, dx for_j: cmp dx, cx jae exit_for_j jbe no_swap mov ah, byte ptr bx mov byte ptr bx, al mov byte ptr bx, ah no_swap: inc dx jmp for_j exit_for_j: bucle for_i

Sintaxis de AT&T (GNU)

Text # void bubble_sort (matriz * sin firmar, longitud sin firmar); .globl bubble_sort .type bubble_sort, @ función bubble_sort: mov 8 (% esp),% ecx # unsigned length cmp $ 1,% ecx jbe exit mov 4 (% esp),% eax # unsigned * array dec% ecx for_ecx: xor % edi,% edi for_edi: mov (% eax,% edi, 4),% ebx cmp% ebx, 4 (% eax,% edi, 4) jae no_xchng mov 4 (% eax,% edi, 4),% edx mov% edx, (% eax,% edi, 4) mov% ebx, 4 (% eax,% edi, 4) no_xchng: inc% edi cmp% edi,% ecx jne for_edi loop for_ecx exit: ret

C

#define SWAP (A, B) (int t = A; A = B; B = t;) void bubbleort (int * a, int n) (int i, j; for (i = n - 1; i> 0 ; i--) (para (j = 0; j< i; j++) { if (a[j] >a) SWAP (a [j], a); )))

C ++

Usando plantilla

#incluir plantilla< typename Iterator >void bubble_sort (Iterador primero, Iterador último) (while (Primero< --Last) for(Iterator i = First; i < Last; ++i) if (*(i + 1) < *i) std::iter_swap(i, i + 1); }

Sin usar plantilla

Burbuja vacía (int * a, int n) (for (int i = n - 1; i> = 0; i--) (for (int j = 0; j< i; j++) { if (a[j] >a) (int tmp = a [j]; a [j] = a; a = tmp;))))

C #

Void BubbleSort (int A) (para (int i = 0; i< A.Length; i++) { for (int j = i+1; j < A.Length; j++) { if (A[j] < A[i]) { var temp = A[i]; A[i] = A[j]; A[j] = temp; } } } }

Delphi

Ordenar una matriz de enteros dinámicos unidimensionales:

Escriba TIntVec = matriz de Integer; ... procedimiento BubbleSort (var a: TIntVec); var i, p, n: entero; b: booleano; comenzar n: = Longitud (a); si n< 2 then exit; repeat b:= false; Dec(n); if n >0 entonces para i: = 0 a n-1 hacer si a [i]> a entonces comienza p: = a [i]; a [i]: = a; a: = p; b: = verdadero; fin; hasta que no b; fin;

D

Void bubbleSort (alias op, T) (T inArray) (foreach (i, ref a; inArray) (foreach (ref b; inArray) (if (mixin (op)) (auto tmp = a; a = b; b = tmp;))))

Fortran

¿Do i = n-1,1, -1 do j = 1, i if (a (j) .gt.a (j + 1)) entonces t = a (j) a (j) = a (j + 1 ) a (j + 1) = t endif enddo enddo

Java

Ordenación de burbujas vacía (int arr) (para (int i = 0; i< arr.length-1; i++){ for (int j = i+1; j < arr.length; j++){ if (arr[i] < arr[j]) { int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } } } }

Pascal

Para i: = n-1 downto 1 do (n es el tamaño de la matriz M) para j: = 1 to i do if M [j]> M then begin tmp: = M [j]; M [j]: = M; M: = tmp; fin; escribir ("valores de salida M:"); para i: = 1 an escribir (M [i]: 4); Writeln;

Algoritmo de clasificación de burbujas mejorado:

P: = Verdadero; (¿hay una permutación?) K: = 1; (Número de vista) Mientras P Comienza P: = falso; Para i: = 1 Para n-k Hacer si X [i]> X Entonces comience A: = X [i]; X [i]: = X; X: = A; P: = verdadero; Fin; k: = k + 1; Fin;

Perl

Para (@out) (para (0 .. $ N-1) (if ($ out [$ _] gt $ out [$ _ + 1]) (($ out [$ _], $ out [$ _ + 1]) = ($ fuera [$ _ + 1], $ fuera [$ _]);)))

Rubí

Arr = swap = true size = arr.length - 1 while swap swap = false for i in 0 ... size swap | = arr [i]> arr arr [i], arr = arr, arr [i] if arr [ i]> tamaño del extremo del arr - = 1 extremo pone arr.join ("") # salida => 1 3 3 5 8 10 11 12 17 20

Pitón

Def swap (arr, i, j): arr [i], arr [j] = arr [j], arr [i] def bubble_sort (arr): i = len (arr) while i> 1: para j en xrange (i - 1): si arr [j]> arr: swap (arr, j, j + 1) i - = 1

VBA

Subordenar (Mus () As Long) Dim i As Long, tmp As Long, t As Boolean t = True Do while tt = False For i = 0 To UBound (Mus ()) - 1 If Mus (i)> Mus ( i + 1) Entonces tmp = Mus (i) Mus (i) = Mus (i + 1) Mus (i + 1) = tmp t = True End If Next Loop End Sub

PHP

$ tamaño = tamaño de ($ arr) -1; para ($ i = $ tamaño; $ i> = 0; $ i--) (para ($ j = 0; $ j<=($i-1); $j++) if ($arr[$j]>$ arr [$ j + 1]) ($ k = $ arr [$ j]; $ arr [$ j] = $ arr [$ j + 1]; $ arr [$ j + 1] = $ k;))

JavaScript

Función sortBubble (datos) (var tmp; for (var i = data.length - 1; i> 0; i--) (for (var j = 0; j< i; j++) { if (data[j] >datos) (tmp = datos [j]; datos [j] = datos; datos = tmp;))) devolver datos; )

JavaFX

Función bubbleSort (seq: Number): Number (var sort = seq; var elem: Number; for (n in reverse) (for (i in) (if (sort< sort[i]){ elem = sort[i]; sort[i] = sort; sort = elem; } } } return sort; }

Nemerle

Usando System.Console; usando Nemerle.Collections; def arr = matriz; foreach (i in) foreach (j in) cuando (arr [j]> arr) (arr [j], arr) = (arr, arr [j]); WriteLine ($ "La lista ordenada es un $ (arr.ToList ())");

TurboBasic 1.1

CLS RANDOMIZE TIMER DEFINT X, Y, N, I, J, DN = 10 "32 766 - 62,7 SEG DIM Y [N], Y1 [N], Y2 [N], Y3 [N], Y4 [N]" FRE (-1) = 21440-21456 IMPRIMIR "ZAPOLNENIE MASSIVA ELEMENTAMI" PARA X = 1 TO NY [X] = X IMPRIMIR Y [X]; SIGUIENTE X: IMPRIMIR IMPRIMIR "PEREMESHIVANIJE ELEMENTOV MASSIVA" IMPRIMIR "SLUCHAINYE CHISLA" PARA X = 1 A N YD = Y [X] XS = INT (RND * N) +1 IMPRIMIR XS; Y [X] = Y Y = YD SIGUIENTE X: IMPRIMIR IMPRIMIR "PEREMESHANNYJ MASSIV" PARA X = 1 PARA N IMPRIMIR Y [X]; SIGUIENTE X: IMPRIMA "ALGORITM" SORTIROVKA PROSTYM OBMENOM "O (N ^ 2) MTIMER FOR J = 1 TO N-1 STEP 1 F = 0 FOR I = 1 TO NJ STEP 1" IF Y [I]> Y THEN D = Y [I]: Y [I] = Y: Y = D: F = 1 SI Y [I]> Y LUEGO INTERCAMBIAR Y [I], Y: F = 1 LOCALIZAR 8,1 REM IMPRIMIR "ANYMACIJA SORTIROVKI" REM PARA X1 = IMPRESIÓN DE BLOQUE DE ANIMACIÓN REM DE 1 TO N Y; REM SIGUIENTE X1: IMPRIMIR REM DEMORA .5 REM SIGUIENTE I SI F = 0 ENTONCES SALIR PARA EL SIGUIENTE J T1 = MTIMER IMPRIMA "OTSORTIROVANNYJ MASSIV" PARA X = 1 TO N IMPRIME Y [X]; SIGUIENTE X: IMPRIMIR IMPRIMIR "TIEMPO TRANSCURRIDO ="; T1

Como se señaló, el algoritmo rara vez se usa en la práctica debido a su bajo rendimiento. La clasificación de burbujas tomará O (n) tiempo en el mejor de los casos y O (n2) en promedio y peor.

Al escribir el artículo, se utilizaron fuentes abiertas de Internet:

Organicemos la matriz de arriba a abajo, desde el elemento cero hasta el último.

La idea detrás del método: el paso de clasificación consiste en ir de abajo hacia arriba a través de la matriz. A lo largo del camino se ven pares de elementos vecinos. Si los elementos de un par están en el orden incorrecto, los intercambiamos.

Después del paso cero a través de la matriz, la "parte superior" es el elemento "más ligero", de ahí la analogía con una burbuja. El siguiente paso se hace al segundo elemento desde la parte superior, por lo que el segundo elemento más grande se eleva a la posición correcta ...

Hacemos pasadas a lo largo de la parte inferior cada vez menor de la matriz hasta que solo queda un elemento en ella. Esto completa la clasificación, ya que la secuencia está en orden ascendente.

Plantilla void bubbleSort (T a, tamaño largo) (i largo, j; T x; para (i = 0; i< size; i++) { // i - número de pase para (j = tamaño-1; j> i; j--) ( // bucle interior del pase si (a> a [j]) (x = a; a = a [j]; a [j] = x;))))

El número medio de comparaciones e intercambios tiene un orden de crecimiento cuadrático: Theta (n 2), de lo que podemos concluir que el algoritmo de burbuja es muy lento e ineficaz.
Sin embargo, tiene una gran ventaja: es simple y se puede mejorar de cualquier manera. Qué vamos a hacer ahora.

Primero, considere la situación en la que no se ha realizado ningún intercambio en ninguno de los pasillos. Qué significa eso?

Esto significa que todos los pares están en el orden correcto, por lo que la matriz ya está ordenada. Y no tiene sentido continuar el proceso (¡especialmente si la matriz se ordenó desde el principio!).

Entonces, la primera mejora del algoritmo es recordar si se realizó algún intercambio en una pasada determinada. Si no, el algoritmo termina.

El proceso de mejora puede continuar si recuerda no solo el hecho del intercambio en sí, sino también el índice del último intercambio k. De hecho: todos los pares de elementos vecinos con índices menores que k ya están en el orden requerido. Otras pasadas pueden terminar en el índice k, en lugar de moverse a un límite superior predeterminado i.

Se puede obtener una mejora cualitativamente diferente del algoritmo a partir de la siguiente observación. Aunque la burbuja de luz desde la parte inferior se eleva hacia la parte superior en una pasada, las burbujas pesadas descienden a la velocidad mínima: un paso por iteración. Entonces, la matriz 2 3 4 5 6 1 se ordenará en 1 pasada, y la secuencia 6 1 2 3 4 5 se ordenará en 5 pasadas.

Para evitar este efecto, puede cambiar la dirección de los pases sucesivos. El algoritmo resultante a veces se denomina " clasificación por agitador".

Plantilla void shakerSort (T a, tamaño largo) (largo j, k = tamaño-1; largo lb = 1, ub = tamaño-1; // límites de la parte sin clasificar de la matriz T x; hacer ( // pasar de abajo hacia arriba para (j = ub; j> 0; j--) (si (a> a [j]) (x = a; a = a [j]; a [j] = x; k = j;)) lb = k + 1; // pasar de arriba a abajo para (j = 1; j<=ub; j++) { if (a >a [j]) (x = a; a = a [j]; a [j] = x; k = j;)) ub = k-1; ) mientras (lb< ub); }

¿Cuánto afectaron los cambios descritos a la eficacia del método? El número medio de comparaciones, aunque disminuyó, sigue siendo O (n 2), mientras que el número de intercambios no ha cambiado en absoluto. El número medio (es el peor) de operaciones sigue siendo cuadrático.

Obviamente, no se requiere memoria adicional. El comportamiento del método mejorado (pero no el inicial) es bastante natural, una matriz casi ordenada se ordenará mucho más rápido que una aleatoria. La clasificación de burbujas es estable, pero el agitador de clasificación pierde esta cualidad.

En la práctica, el método de la burbuja, incluso con mejoras, es, lamentablemente, demasiado lento. Por lo tanto, casi nunca se usa.

Etiquetas: Clasificación de burbujas B, clasificación de burbujas B, clasificación de burbujas de matriz 2D

Ordenamiento de burbuja

Y el algoritmo es muy simple. Pasamos por la matriz de números y verificamos el orden (el siguiente número debe ser mayor e igual al anterior), tan pronto como nos topamos con una violación de la orden, inmediatamente intercambiamos los elementos, llegamos al final de la matriz y luego empezar de nuevo.

Ordenemos la matriz (1, 5, 2, 7, 6, 3)
Pasamos por la matriz, verificamos el primer número y el segundo, van en orden ascendente. Entonces hay una violación de la orden, intercambiamos estos elementos
1, 2, 5, 7, 6, 3
Continuamos caminando a través de la matriz, 7 es más que 5, pero 6 es menos, por lo que intercambiamos lugares.
1, 2, 5, 6, 7, 3
3 fuera de servicio, intercambiar con 7
1, 2, 5, 6, 3, 7
Regrese al principio de la matriz y haga lo mismo.

1, 2, 5, 3, 6, 7
1, 2, 3, 5, 6, 7

Dicen que esto es similar a la "aparición" de elementos "más ligeros", como burbujas, razón por la cual el algoritmo recibió su nombre. void bubbleSort (int * a, tamaño_t tamaño) (tamaño_t i, j; int tmp; for (i = 1; i< size; i++) { for (j = 1; j < size; j++) { if (a[j] >a) (tmp = a [j]; a [j] = a; a = tmp;))))

Este algoritmo siempre tomará (n-1) 2 pasos, independientemente de la entrada. Incluso si la matriz está ordenada, se recorrerá (n-1) 2 veces. Además, se volverán a comprobar los datos ya ordenados.

Suponga que necesita ordenar la matriz 1, 2, 4, 3

1 2 4 3
1 2 4 3
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4

Una vez intercambiados los elementos ay a, ya no es necesario pasar por esta sección de la matriz. Tengamos esto en cuenta y rehagamos el algoritmo.

Void bubbleSort2 (int * a, size_t size) (tamaño_t i, j; int tmp; for (i = 1; i< size; i++) { for (j = i; j >0; j--) (si (a [j]< a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

Otra implementación

Void bubbleSort2b (int * a, size_t size) (tamaño_t i, j; int tmp; for (i = 1; i< size; i++) { for (j = 1; j <= size-i; j++) { if (a[j] < a) { tmp = a[j]; a[j] = a; a = tmp; } } } }

En este caso, habrá la mitad del número de pasos, pero aún queda el problema de ordenar una matriz ya ordenada: debe hacer que la función mire la matriz ordenada una vez. Para hacer esto, introducimos una variable de bandera: se omitirá (bandera = 0) si la matriz está ordenada. Tan pronto como nos encontremos con un fuera de servicio, la bandera se levantará (bandera = 1) y comenzaremos a ordenar la matriz como de costumbre.

Void bubbleSort3 (int * a, size_t size) (size_t i; int tmp; char flag; do (flag = 0; for (i = 1; i< size; i++) { if (a[i] < a) { tmp = a[i]; a[i] = a; a = tmp; flag = 1; } } } while (flag); }

En este caso, la complejidad también es del orden de n 2, pero en el caso de una matriz ordenada, solo habrá una pasada.

Ahora mejoremos el algoritmo. Escribamos una función general para ordenar una matriz de tipo vacío. Dado que se desconoce el tipo de variable, será necesario transferir adicionalmente el tamaño de un elemento de la matriz y la función de comparación.

Int intSort (const void * a, const void * b) (return * ((int *) a)> * ((int *) b);) void bubbleSort3g (void * a, size_t item, size_t size, int (* cmp) (const void *, const void *)) (size_t i; void * tmp = NULL; char flag; tmp = malloc (item); do (flag = 0; for (i = 1; i< size; i++) { if (cmp(((char*)a + i*item), ((char*)a + (i-1)*item))) { memcpy(tmp, ((char*)a + i*item), item); memcpy(((char*)a + i*item), ((char*)a + (i-1)*item), item); memcpy(((char*)a + (i-1)*item), tmp, item); flag = 1; } } } while (flag); free(tmp); }

La función se ve fea: la dirección del elemento actual y anterior a menudo se calcula. Seleccionemos variables separadas para esto.

Void bubbleSort3gi (void * a, size_t item, size_t size, int (* cmp) (const void *, const void *)) (size_t i; void * tmp = NULL; void * prev, * cur; char flag; tmp = malloc (elemento); do (bandera = 0; i = 1; prev = (char *) a; cur = (char *) prev + elemento; while (i< size) { if (cmp(cur, prev)) { memcpy(tmp, prev, item); memcpy(prev, cur, item); memcpy(cur, tmp, item); flag = 1; } i++; prev = (char*)prev + item; cur = (char*)cur + item; } } while (flag); free(tmp); }

Ahora, con estas funciones, puede ordenar matrices de cualquier tipo, por ejemplo

Void main () (int a = (1, 0, 9, 8, 7, 6, 2, 3, 4, 5); int i; bubbleSort3gi (a, sizeof (int), 10, intSort); para (i = 0; yo< 10; i++) { printf("%d ", a[i]); } _getch(); }

Ordenando una matriz multidimensional

Ordenar una matriz multidimensional estática es esencialmente lo mismo que ordenar una matriz unidimensional. Puede aprovechar la propiedad de que las matrices unidimensionales y multidimensionales estáticas tienen la misma representación de memoria.

Void main () (int a = (1, 9, 2, 8, 3, 7, 4, 6, 5); int i, j; bubbleSort3gi (a, sizeof (int), 9, intSort); para (i = 0; yo< 3; i++) { for (j = 0; j < 3; j++) { printf("%d ", a[i][j]); } } } Сортировка динамически созданного двумерного массива может быть произведена двумя способами. Во-первых, можно по определённому алгоритму находить индекс i-го и j-го элемента по порядковому номеру k от 0 до n * m. #include #incluir #incluir #incluir void bubbleSort2d (int ** a, size_t m, size_t n) (int tmp; size_t i, j, k, jp, ip; size_t tamaño = m * n; char flag; do (flag = 0; for (k = 1 ; k< size; k++) { //Вычисляем индексы текущего элемента j = k / m; i = k - j*m; //Вычисляем индексы предыдущего элемента jp = (k-1) / m; ip = (k-1) - jp*m; if (a[i][j] >a) (tmp = a [i] [j]; a [i] [j] = a; a = tmp; flag = 1;))) while (bandera); ) #define SIZE_X 3 #define SIZE_Y 4 void main () (int ** a = NULL; int i, j; a = (int **) malloc (sizeof (int *) * SIZE_X); for (i = 0; I< SIZE_X; i++) { a[i] = (int*) malloc(sizeof(int) * SIZE_Y); for (j = 0; j < SIZE_Y; j++) { a[i][j] = rand(); printf("%8d ", a[i][j]); } printf("\n"); } printf("\nafter sort\n"); bubbleSort2d(a, SIZE_X, SIZE_Y); for (i = 0; i < SIZE_X; i++) { for (j = 0; j < SIZE_Y; j++) { printf("%8d ", a[i][j]); } printf("\n"); } for (i = 0; i < SIZE_X; i++) { free(a[i]); } free(a); _getch(); }

En segundo lugar, primero puede mover la matriz a unidimensional, ordenar la matriz unidimensional y luego volver a moverla a dos dimensiones.

Void bubbleSort3gi2d (void ** a, size_t item, size_t m, size_t n, int (* cmp) (const void *, const void *)) (size_t size = m * n, sub_size = n * item; size_t i, j , k; void * arr = malloc (tamaño * elemento); char * p1d = (char *) arr; char * p2d = (char *) a; // Copia una matriz bidimensional de tipo void en unidimensional para ( yo = 0; yo< m; i++) { memcpy(p1d + i*sub_size, *((void**)(p2d + i*item)), sub_size); } bubbleSort3gi(arr, item, size, cmp); //Копируем одномерный массив обратно в двумерный for (i = 0; i < m; i++) { memcpy(*((void**)(p2d + i*item)), p1d + i*sub_size, sub_size); } }

Si está confundido acerca de esta función, utilice una escrita. Llamar, del ejemplo anterior

No solo no se considera el más método rápido además, cierra la lista de los métodos de ordenación más lentos. Sin embargo, también tiene sus ventajas. Por lo tanto, ordenar por el método de la burbuja es la solución más lógica y natural al problema, si necesita organizar los elementos en un orden determinado. Una persona común, por ejemplo, lo usará manualmente, solo por intuición.

¿De dónde vino este nombre inusual?

El nombre del método se acuñó usando una analogía con las burbujas de aire en el agua. Esta es una metáfora. Así como las pequeñas burbujas de aire se elevan hacia arriba, después de todo, su densidad es mayor que la de cualquier líquido (en este caso, el agua), por lo que cada elemento de la matriz, cuanto menor es su valor, más gradualmente se abre camino hacia el principio. de la lista de números.

Descripción del algoritmo

La clasificación de burbujas se realiza de la siguiente manera:

primer paso: los elementos de la matriz de números se toman de dos en dos y también se comparan en pares. Si en algunos dos elementos el primer valor es mayor que el segundo, el programa intercambia sus lugares;
por lo tanto, termina al final de la matriz. Mientras que todos los demás elementos permanecen, como estaban, en un orden caótico y aún requieren clasificación;
por lo tanto, el segundo paso es necesario: se realiza por analogía con el anterior (ya descrito) y tiene el número de comparaciones - menos uno;
el pase número tres tiene una comparación menos que el segundo y dos menos que el primero. Etc;
para resumir, cada pasada tiene (valores totales en la matriz, un número específico) menos (número de pasada) comparaciones.

Aún más breve, el algoritmo del programa futuro se puede escribir de la siguiente manera:

se comprueba una matriz de números hasta que se encuentran dos números cualesquiera, y el segundo de ellos debe ser mayor que el primero;
el programa intercambia los elementos de la matriz ubicados incorrectamente entre sí.

Pseudocódigo basado en el algoritmo descrito

La implementación más simple es la siguiente:

Procedimiento Sortirovka_Puzirkom;

Comienzo

ciclo para j desde nachalnii_index antes de konechii_index;

ciclo para I desde nachalnii_index antes de konechii_index-1;

Si massiv [i]> massiv

(cambiar los valores en lugares);

Fin

Por supuesto, aquí la simplicidad solo agrava la situación: cómo algoritmo más simple, especialmente porque todas las deficiencias se manifiestan en él. El consumo de tiempo es demasiado alto incluso para una matriz pequeña (aquí entra en juego la relatividad: para un profano, la cantidad de tiempo puede parecer pequeña, pero en el negocio de un programador, cada segundo o incluso un milisegundo cuenta).

Se requería una mejor implementación. Por ejemplo, teniendo en cuenta el intercambio de valores en la matriz por lugares:

Procedimiento Sortirovka_Puzirkom;

Comienzo

sortirovka = verdadero;

ciclo adiós sortirovka = verdadero;

sortirovka = falso;

ciclo para I desde nachalnii_index antes de konechii_index-1;

Si massiv [i]> massiv(el primer elemento es mayor que el segundo), entonces:

(intercambiamos los elementos en lugares);

sortirovka = verdadero; (indicó que se realizó el intercambio).

Fin.

Desventajas del método

La principal desventaja es la duración del proceso. ¿Cuánto tiempo tarda la 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 haya elementos menos un valor. Esto se debe a que al final solo queda un elemento sin nada con qué comparar, y la última pasada a través de la matriz se convierte en una acción inútil.

Además, el método de clasificación es eficiente intercambios simples, como también se le llama, solo para arreglos pequeños. No será posible procesar grandes cantidades de datos con su ayuda: el resultado serán errores o una falla del programa.

Dignidad

La clasificación de burbujas es muy fácil de entender. En los planes de estudio de las universidades técnicas, al estudiar el orden de los elementos de la matriz, es el primero en aprobar. El método se implementa fácilmente como en el idioma. Programación Delphi(D (Delphi) y C / C ++ (C / C plus plus), un algoritmo increíblemente simple para organizar los valores en el orden correcto y Bubble Sort es ideal para principiantes.

Debido a deficiencias, el algoritmo no se utiliza para fines extracurriculares.

Principio de clasificación claro

Vista inicial de la matriz 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 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 7 22 37 74 44

1 4 7 8 22 37 74 44

Etapa 4 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

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 de clasificación de burbujas en Pascal

Ejemplo:

const kol_mas = 10;

var massiv: 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 do readln (massiv [a]);

para un: = 1 a kol_mas-1 comience

para b: = a + 1 to kol_mas do begin

si massiv [a]> massiv [b] entonces comience

k: = massiv [a]; massiv [a]: = massiv [b]; massiv [b]: = k;

fin;

Writeln ("después de ordenar");

para a: = 1 a kol_mas do writeln (massiv [a]);

Un ejemplo de clasificación de burbujas en C (C)

#incluir

int main (int argc, char * argv)

int massiv = (36, 697, 73, 82, 68, 12, 183, 88), i, ff;

por (;;) (

ff = 0;

para (i = 7; i> 0; i -) (

si (masivo [i]< massiv) {

swap (massiv [i], massiv);

si (ff == 0) romper;

getch (); // retraso de la pantalla