¿Hay algún truco para que un programador de computadoras recuerde el código de un tipo de burbuja?

El truco es entender, no recordar.

Como sugiere el nombre “Bubble sort”, hay una razón por la que se llama Bubble. Las burbujas tienden a moverse para lograr un orden correcto

El concepto es simple:

“Los que se supone que están en la parte superior, burbujean hacia arriba, los que se supone que están en la parte inferior, burbujean hacia abajo” repiten hasta que no haya más burbujas

Implementación de fragmentos de código en c ++, suponiendo que se nos dé un vector de enteros

vacío bubble_sort (std :: vector & v)
{
mientras que (1)
{
bool intercambiado = falso;
para (int i = 0; i {
si (v [i]> v [i + 1])
{
std :: swap (v [i], v [i + 1]);
intercambiado = verdadero;
}
}
if (! swapped) {break; }
}
}

La clasificación de burbujas es una técnica de clasificación fácil de recordar.

en primer lugar, todos sabemos que se necesita complejidad [matemática] n ^ 2 [/ matemática]. es decir, requiere al menos dos bucles anidados.

así que el bucle más externo es el número de pases

y el bucle interno es el número de intercambio.

echemos un vistazo al pseudocódigo:

bubbleSort (arr, n)
{
i, j;
para (i = 0; i

para (j = 0; j // hay yo nos. de elementos ya están
: // ordenado
if (arr [j]> arr [j + 1])
swap (arr [j], arr [j + 1]);
}

entonces las claves totales para recordar:

dos bucles: número de pases y número de intercambio. uno toma hasta n y otro toma hasta ni-1;

sencillo. probablemente tenga más sentido si echa un vistazo al algoritmo de selección de selección.

Antes de que nos enseñaran los algoritmos de clasificación, a nuestra clase se le asignó una tarea: escribir un programa para ordenar una matriz. Yo y la mayoría de los estudiantes implementamos el tipo de burbuja y algunos otros escribieron el tipo de inserción. Esto fue antes de Internet.

La clasificación de burbujas es la forma más fácil de implementar y más intuitiva de clasificar algo para la mayoría de las personas. Solo piense cómo ordenaría y probablemente será una burbuja.

No estoy de acuerdo con que no implementen esto a mano en una larga carrera de programación. Si necesita ordenar una lista muy corta y no tiene una rutina de biblioteca disponible, no vale la pena el código para ordenar rápidamente. La ordenación de burbujas también es más rápida si la lista está ordenada o los elementos están cerca del lugar correcto. Esto sucede ocasionalmente cuando la velocidad es importante y la mayoría de las bibliotecas no incluyen un tipo de burbuja, ya que la mayoría de la gente quiere un algoritmo más rápido en un caso general. Pero no es algo que uses todos los días.

Idealmente, habría un truco para que la gente olvidara que alguna vez existió el tipo de burbuja. ¿Pero quién recuerda los algoritmos de clasificación? No he escrito uno en años . Tuve que hacerlo en un punto, por supuesto. He implementado varios algoritmos de clasificación muchas veces en mi vida. Escribí un tipo de fusión en FORTRAN 90 en un mini-mainframe VAX 8550. Escribí un tipo de inserción en el ensamblaje 6502 en un Commodore 64. Escribí un árbol en una biblioteca anticuada basada en DOS en una PC de 640K. Simplemente no he hecho nada así últimamente. Si quiero ordenar algo, escribiré

#include
#include
…
std :: array a {6, 9, 2, 4, 3}; // C ++ 14
std :: sort (a.begin (), a.end ());

O

importar {
“ordenar”
}
…
a: = [] int {6, 9, 2, 4, 3}
sort.Ints (a)

O

const a = [6, 9, 2, 4, 3];
un tipo();

etc.

Puede estar casi 100% seguro de que estas rutinas de biblioteca harán un mejor trabajo de clasificación que su código casero. Han tenido siete tipos de infiernos derrotados por codificadores divinos cuyo dobladillo la mayoría de nosotros no estamos en condiciones de tocar. Si alguna vez necesita escribir un algoritmo de clasificación (para algún procesador integrado esotérico o algo así), entonces utilice el increíble poder de Internet y búsquelo .

¿Pero tipo burbuja? Si estás en una entrevista y el entrevistador te pide que implementes el ordenamiento de burbujas, entonces considera seriamente escapar. Probablemente sea un idiota, y la compañía que le dio la tarea de entrevistar a la gente está llena de idiotas.

Probablemente nunca tendrá que escribir código para ordenar burbujas en una capacidad profesional.

Es posible que se le pida que lo escriba para una entrevista o prueba, pero obtendrá menos puntos por escribir un código perfecto que no entienda que por escribir un código defectuoso para un algoritmo que usted entienda.

El truco, entonces, es estar bien con anotar menos puntos.

Lo recuerdo así: ¿cuál es el código más simple que puedo escribir para ordenar una matriz intercambiando condicionalmente elementos adyacentes?

Escriba eso, y es probable que sea un “tipo de burbuja”.

No hay truco, no recuerdas el código. Simplemente sabe cómo funciona (itera la matriz una y otra vez, dejando que floten las burbujas más pequeñas y ligeras), y la implementa una vez más.

Recordar el código de memoria es una de las cosas más inútiles que uno puede hacer: el código no importa. Lo que importa es el problema en cuestión y el enfoque. Deberá tener cuidado al codificar el enfoque correctamente, pero el código exacto no importa; y cuando lo hace, lo recuerdas como, “oh, y hay ese pequeño truco para evitar atravesar la parte que ya está ordenada”.

Compárelo con poemas. No es necesario recordar las palabras exactas, solo que era brillante, las toves eran resbaladizas y los borogoves eran como momias en algo.

Si bien estoy de acuerdo con todos los que dicen que hay que entenderlo, no solo recordarlo mediante un estudio de memoria, no estoy seguro de por qué alguien necesitaría recordarlo desde el principio.

Algunas entrevistas de codificación lo requieren, pero, en mi opinión, es un requisito deficiente que no muestra exactamente nada a los entrevistadores.

Los algoritmos de ordenación de matrices son algo que escribe solo algunas veces en su vida y todos ellos están en la escuela o durante la entrevista. Además de algunos trabajos de programación relativamente exóticos, donde uno necesita programar en un nivel bajo y requiere un alto rendimiento, no hay necesidad de implementar la ordenación de matrices.

Solo recuerde cómo hace lo que hace, el resto de la implementación viene naturalmente.

Imagine un brazo barrendero que pasa sobre los artículos a clasificar. En cada pasada sobre los elementos, el elemento más ligero se “burbujea” en la parte superior. Una vez que no hay más elementos para “barrer”, el algoritmo se detiene. El orden en el que los elementos se burbujearon hasta la parte superior es el orden de clasificación, de menor a mayor.

El brazo de barrido puede imaginarse como una especie de estructura de bucle y puede interpretar que el “elemento más ligero” es el elemento que menos se compara con todos los demás elementos del barrido actual.

En mi opinión, si lo entiende de esta manera, puede encontrar una buena cantidad de formas de implementar este algoritmo, es decir, el “código” como lo denomina.

No.

El programador de computadoras no necesita recordar el código. Recuerdan el algoritmo y pueden escribirlo cada vez de manera diferente (while / loop / for / variable names …)

Si solicita un truco sobre cómo el no programador puede impresionar al programador al recordar el código de un algoritmo, es una pregunta diferente.

Aprendes a buscarlo en Google 😉

Supongo que está preguntando porque está tratando de prepararse para entrevistas técnicas. No deberías estar memorizando el código, deberías estar tratando de entender cómo todas las piezas van juntas. Si comprende el por qué, puede recodificar el qué. Puede que no sea perfecto, pero la gente está buscando ver si puedes entender el código, no si puedes memorizarlo perfectamente.

Hoy en día, para la mayoría de los programadores (que trabajan), recordar diferentes tipos de algoritmos de clasificación ya no es una necesidad, por dos razones.

Eins) Están codificando a un alto nivel y la plataforma o el marco que están utilizando se encargará de seleccionar un algoritmo de clasificación adecuado para la colección que están clasificando como shit.sort ().

Zwei) Si están codificando en un nivel bajo, si alguna vez entendieron los métodos de clasificación, entonces pueden codificarlos bastante bien en cualquier idioma en el que dominen, o, si no recuerdan detalles específicos, pueden usar una biblioteca o pueden buscar un algoritmo sexy y probado en Internetz en cuestión de segundos.

Lo mejor para notar sobre Bubble Sort es que la implementación convencional se llamaría mejor Stone Sort .

Recorra todos los valores v (i) donde 0 si alguna entrada v (i) se ordena después de su siguiente vecino v (i + 1) intercambie esos dos valores.

El efecto de esto es que el valor “más grande” visto hasta ahora (en el ciclo) se mueve al final de la lista.

El resultado es que la lista se pone en orden desde abajo en el sentido de que después de k iteraciones, los últimos k valores de la estarán en su posición final.

Puede (por supuesto) interpretar las posiciones de alto índice como ‘superiores’ y donde w> v el valor w es visto como una ‘burbuja más clara’, pero eso no tiene sentido con nuestro pensamiento normal sobre ‘inferior’ de la lista y que 35 es más ligero que 30.

Por supuesto, Bubble Sort es terriblemente ineficiente, pero una eficiencia que se pasa por alto es que durante la k -ésima iteración se pueden ignorar los valores inferiores de k-1 . Sin embargo, dado que el propósito de Bubble Sort es ser el algoritmo de clasificación plausible de peor rendimiento pero ingenuamente que apenas parece importar.

Estoy de acuerdo con el usuario anterior en que, obviamente, la mejor opción es comprenderlo, pero si está utilizando un lenguaje OO, simplemente podría crear la clase y usarla cuando lo necesite.

El programador implementará el ordenamiento de burbujas muy fácilmente cada vez que lo necesite. El mono de codificación necesita recordar fragmentos de código. Por lo tanto, la pregunta es incorrecta.

No se avergüence de preguntarle a Google, no existen sin ninguna razón …