sort complexity bubble algorithms algorithm sorting

algorithm - complexity - ¿Qué deberían enseñar los estudiantes primero cuando aprenden algoritmos de clasificación?



sorting algorithms complexity (30)

Acabo de hacer eso la semana pasada con mi hijo. Le pido que presente su propio algoritmo de clasificación, y me preguntó cuánto tardaría en clasificar un mazo de cartas con su método. Luego le enseñé Bubble Sort (el más fácil de explicarle a un niño) "¡Es una burbuja!" y lo hizo contar los pasos de nuevo. Se dio cuenta de que era más fácil y rápido.

Entonces, si lo desea, puede enseñar a los más avanzados (Quicksort es el más sorprendente). Idealmente, debería enseñar tres al menos que sean diferentes (no variación de la misma).

Si fuera profesor de programación y tuviera que elegir un algoritmo de clasificación para enseñar a sus alumnos cuál sería? Estoy pidiendo solo uno porque solo quiero introducir el concepto de clasificación. ¿Debería ser el tipo de burbuja o el tipo de selección? Me di cuenta de que estos dos se enseñan con más frecuencia. ¿Hay algún otro tipo de género que explique la clasificación de una manera más fácil de entender?

Pídales a todos que traigan una baraja de cartas y escoja un palo. Divida en equipos de dos. Uno baraja las 13 cartas y las pone boca abajo en una fila. El compañero llega a señalar dos de las cartas. El otro los levanta, los mira y dice "En orden" o "No está en orden". Entonces, el compañero puede decirle que los intercambie y que los vuelva a poner (boca abajo)

El trabajo del socio es ordenar las tarjetas en orden (algo que deberá definir al inicio).

Cuando el parner cree que están clasificados, dice "Parar". El otro gira las cartas boca arriba y lo comprueban.

Cuando haya terminado, discuta qué funcionó para todos. Luego habla sobre BUBBLE SORT vs SELECTION sort

Luego, habla sobre la CLASIFICACIÓN RÁPIDA.

Pídales que prueben a cada uno de ellos, con su juego de cartas.

Aconsejaría tanto Selection como Merge Sort en los algoritmos generales de clasificación. Ambos son relativamente sencillos en comparación con sus amigos. Pero si solo puedes enseñar uno y la gente puede manejarlo, yo elegiría Merge Sort. Porque el tipo de combinación es eficiente, estable y enseña varios conceptos importantes (fusión, división y conquista).

Tipo de selección:
Encuentre el valor mínimo / máximo y colóquelo en su lugar, luego vuelva a hacerlo en el resto de la lista ... esto es muy intuitivo. Para mí, la selección es mucho más intuitiva que el tipo de burbuja. Probablemente puedas enseñar esto en muy poco tiempo. Y habrá una sensación de logro por parte de las personas que implementan esto ... Aunque Bubble and Insertion puede salir temprano y no perderá tiempo en una lista ordenada. La selección es probablemente la más fácil de hacer. La inserción es probablemente la más difícil de implementar.

MergeSort:
Esto le enseñará a fusionar (lo cual es importante porque hay un montón de aceleraciones que se pueden obtener combinando dos listas ordenadas) y también cómo dividir el problema en subproblemas más pequeños (importante para tratar con estructuras jerárquicas y también utilizado en ordenación rápida). QuickSort aunque más rápido es mucho más difícil de entender. Necesita dos variables de escaneo, un elemento de pivote, etc. Combinar es más directo y la fusión será útil para otras cosas que no sean la clasificación (como unir dos registros que están ordenados en un campo) ....

El concepto básico de una fusión es intuitivo. Tome el artículo menor de una lista ordenada y colóquelo en la lista final. Y dividir el problema de clasificación de fusión también es algo intuitivo.
mergesort (primera mitad) mergesort (segunda mitad)
fusionar (primera mitad, segunda mitad)

Si solo puedes enseñar un tipo y tienes que hacerlo rápidamente (o el público no está realmente interesado en absoluto), me inclinaría por la Selección porque es más difícil y la selección podría enseñarse rápidamente. Pero si la audiencia está más motivada, entonces yo haría Merge porque enseña muchos conceptos fundamentales adicionales.

De los géneros más eficientes, este es mucho más fácil que el tipo rápido y de montón. Aunque el ordenamiento rápido es probablemente el más rápido en la práctica (siempre que tenga suficiente RAM) y Heap probablemente pueda ordenar las listas más grandes (si se implementan de forma no recursiva).

Clasificación del cubo:
Me referiré a esto porque también es intuitivo y representa otro tipo de algoritmo de clasificación. En muchas situaciones, esto es apropiado y el tiempo O (n) es muy atractivo.

Clasificación de conteo:
Tiene sus usos. Hay algunos casos en que esto es muy eficiente ... También es relativamente fácil.

Comenzaré mostrando el tipo de inserción. Todo el mundo que ha ordenado una mano de cartas (que básicamente es todo el mundo) sabe de este tipo. Además, no tiene el rendimiento abismal de sortear burbujas.

Creo que los métodos de clasificación son un muy buen ejemplo de lo que es un algoritmo. Pero solo se convierte en un buen ejemplo cuando se comparan varios métodos. Si solo puedes enseñar uno, no estoy seguro de que valga la pena.

Realísticamente, llamamos al método de clasificación en algún marco. Entonces, si no puede enseñar de manera efectiva sobre los aloritmos de clasificación, puede que no valga la pena el tiempo.

Ya nadie tiene que escribir un método de clasificación, pero sigue siendo un muy buen ejemplo del impacto de los algoritmos.

Creo que solo enseñar un tipo es paralizante. Recuerde que Everything Is Fast For Small n , por lo tanto, en términos de enseñar un género, no se trata de rendimiento, sino de comprender el algoritmo.

Creo que la introducción debería ser del tipo de burbuja para introducir el concepto, pero como mínimo introduzca otro tipo para que los alumnos piensen en otras formas de realizar la tarea. Asegúrese de que entiendan la compensación en el rendimiento y la complejidad del código y que hay diferentes herramientas para diferentes situaciones.

El género de burbujas es el clásico, y es muy fácil entender por qué funciona.

Pero a menos que este sea un curso introductorio, debe incluir una visión general de otros algoritmos de clasificación, ya que es la mejor manera de mostrar las compensaciones involucradas en el diseño de algoritmos y explicar el mejor caso vs. peor comportamiento promedio (tanto tiempo de ejecución y memoria )

El ordenamiento de selección es probablemente el algoritmo de clasificación más sencillo de enseñar y el más simple de entender. También es un gran ejemplo de por qué las soluciones simples no siempre son las mejores, lo que podría conducir a una discusión sobre géneros más interesantes y rápidos como mergesort y quicksort.

El tipo de burbuja es el más fácil de asimilar para principiantes, y también sirve como un excelente ejemplo de por qué las soluciones fáciles pueden ser costosas. ¿Podría ser una buena forma de pasar a una complejidad asintótica y una notación de gran O?

Enseñaría el género Bubble si tuviera que elegir solo uno, ya que es más fácil de entender (creo). Sin embargo, lo más valioso que obtuve al estudiar los diversos algoritmos de clasificación fue que hay más de una forma de hacerlo (lo que finalmente me llevó a Perl, pero esa es otra historia), cada uno con sus ventajas y desventajas. Por lo tanto, aprender un solo algoritmo de clasificación podría ser una manera de pasar por alto el aspecto crítico de todo el asunto.

Enseñaría el tipo de "llamar al marco".

Sería eficiente enseñar y aprender de este tipo. Los estudiantes tendrían un alto grado de éxito y baja tasa de errores al implementar este tipo.

Editar: Hay muchos comentarios críticos sobre esta respuesta sobre la calidad de mi clase de clasificación única. Estas críticas son aplicables a cualquier respuesta a esta pregunta, que es: "Si fueras profesor de programación y tuvieras que elegir un algoritmo de clasificación para enseñar a tus alumnos cuál sería?"

Er, deberías darles un tipo O (n ^ 2) y O (n log n). Bubble y Heap serían mis elecciones.

Independientemente del algoritmo real que elija, le aconsejo que presente dos algoritmos (en lugar de uno) y explique las compensaciones (en memoria, velocidad de ejecución, etc.) que generan.

Entonces deberías decir que no existe un algoritmo de clasificación ideal que pueda aplicarse ciegamente a cualquier tarea. Sin embargo, hay buenos candidatos. En este punto, muéstreles quicksort e introspection sort (como deberes) y considere que su tarea compitió :)

IntroSort es un gran algoritmo para enseñar también, una vez que los estudiantes han aprendido a entender el tipo Quick y Heap. IntroSort (abreviatura de ordenación introspectiva) se inicia como QuickSort y cambia a HeapSort si la profundidad de recursión excede un nivel basado en el logaritmo de la cantidad de elementos que se ordenan.

En general, obtienes lo mejor de los mundos de clasificación Rápida y Hep y un peor tiempo de ejecución de O ( n log n ).

IntroSort en Wikipedia

La mejor conferencia a la que asistí en algoritmos los demostró a todos como gráficos de barras dibujados a través de applets de Java. A continuación, podría ver el patrón de clasificación, así como las características de O (N) ...

¿Enseñas burbuja porque es increíblemente simple y muestra el resto como animaciones quizás?

No estoy seguro de poder ser un profesor de ciencias de la computación y solo enseñar un algoritmo de clasificación.

Como mínimo, a los estudiantes se les debe enseñar al menos uno de cada uno de los principales tipos de clasificación , a saber, un tipo de intercambio, un género de selección, un género de inserción y un tipo de fusión. Además de uno de cada uno de estos tipos, también cubriría Quicksort, que se encuadra en el encabezado de ordenamiento de particiones.

En cuanto a los géneros específicos de cada uno de los tipos que cubriría:

  • Burbuja Clasifique como un ejemplo de la categoría de ordenación de intercambio, ya que es uno de los tipos de ordenación más simples y que probablemente ya hayan visto o descubierto por sí mismos. Este es también el tipo de uso que probablemente usarán más a menudo si tienen que rodar el suyo por algo simple, por lo que tiene sentido que lo entiendan.
  • Heapsort de la categoría de ordenación de selección. Probablemente este sea el tipo más confuso al lado de Quicksort, pero una vez que comprendan cómo se configura para comprender el algoritmo de Quicksort.
  • Se cubrirá la ordenación de inserción como un ejemplo de la categoría de ordenación por inserción, ya que también es un tipo simple del que pueden sacarle provecho. Como pueden encontrar escenarios en los que necesitan unir dos listas, saber que tiene sentido.
  • Merge Sort es algo así como un tipo especializado, por lo que no lo ve con demasiada frecuencia, pero es muy bueno en lo que hace y sigue siendo útil en situaciones en las que necesita ordenar los datos que está obteniendo por partes.

Si tuviera que limitar las cosas a una sola clase que pudiera enseñar, pero tenía tiempo para asegurarme de que el estudiante entendiera exactamente lo que estaba sucediendo, enseñaria Quicksort. Si bien no es fácil de comprender, la gran mayoría de los marcos que existen allí lo utilizan para su algoritmo de ordenamiento, por lo que una comprensión de cómo funciona es útil en su desarrollo con ese marco. Además, es bastante probable que si alguien es capaz de entender Quicksort, entonces pueda aprender el Sort de burbuja y el Tipo de inserción por su cuenta.

No importa qué tipo de algoritmo de clasificación se enseñe, si los estudiantes no aprenden acerca de bogosort , se están perdiendo, y el profesor está perdiendo una forma obvia de atraer a su audiencia :)

Pensé que la ordenación por selección era la más simple de comprender, y la OMI sería la mejor para introducir la clasificación.

Creo que sería una tontería no enseñarles al menos un algoritmo de clasificación O (nlog (n)), junto con una explicación de la notación O grande.

Quicksort es definitivamente otro algoritmo de clasificación muy simple de entender, y es muy fácil implementarlo. Tiene versiones in-situ y "fuera de lugar" que son divertidas para pensar. Y es rápido.

Lo suficientemente rápido para ti, al menos, viejo.

Sería un tipo radical . Porque es sorprendentemente fácil y, sin embargo, no obvio. Cosas como esa solo tienen que ser enseñadas.

Si quieres enseñar a ordenar, entonces una clasificación de burbujas es probablemente la más fácil de comprender. Si quieres enseñar algoritmos de ordenamiento, entonces realmente deberías enseñar quicksort, mergesort, insertsort y posiblemente incluso heapsort para que los estudiantes puedan tener una idea de las ventajas y desventajas entre los diversos métodos de clasificación.

Teniendo en cuenta que su estudiante probablemente nunca tenga que codificar uno solo, la pregunta realmente debería decidirse sobre "¿Cuál es el valor de aprender este algoritmo?" en lugar de "¿qué hace este algoritmo?"

En otras palabras, a sus estudiantes se les debe enseñar una variedad de algoritmos diferentes, ya sea para clasificar, buscar, comprimir, etc., es en gran medida irrelevante.

Uhm ... los algoritmos de clasificación son realmente una forma intuitiva y concreta de enseñar algunas buenas lecciones sobre notaciones de Big O, optimización, sentido común y ciencias de la computación en general, y tal vez una "clasificación de burbuja" + "clasificación de selección" + "clasificación de fusión" enfoque puede ser útil, para la comparación. Creo que el más selecto (y eficiente en muchos casos) es el seleccionado.

Yo compararía y contrastaría una o (n-cuadrado), como una ordenación de selección con una clasificación ao (n log n), como una ordenación rápida.

Pero si no son personas de ciencias de la computación y no necesariamente tienen la intención de serlo, simplemente muestren una clase fácil de entender como selección o burbuja.

Si finalmente solo puedes enseñar UN algoritmo, creo que SelectionSort es aún más fácil de enseñar (e implementar en mi humilde opinión) como BubbleSort. Puede ser muy ineficaz, pero todos obtendrán su concepto, todos con un poco de conocimiento de programación pueden leer su código y hay una cosa que hace que SelectionSort sea único entre todos los algoritmos de clasificación: solo necesita n - 1 swaps para una lista de n entradas :-) No solo nunca necesita hacer más de n - 1 swaps, realmente necesita exactamente n - 1 swaps. El número de intercambios realizados es 100% determinista y conocido incluso antes de que comience. Creo que esto no es cierto para cualquier otro algoritmo de clasificación in situ (aunque las personas son libres de corregirme en los comentarios).

De lo contrario, yo voto por BubbleSort y SelectionSort, que son más fáciles de entender y muestran cómo clasificar de la manera más fácil (estos son lo suficientemente simples, los estudiantes pueden llegar a estas soluciones sin haber oído hablar de ningún algoritmo de clasificación) a veces no es muy efectivo. En contraste, mostraría QuickSort y MergeSort, siendo muy buenos algoritmos de división y conquista, y ambos también muy rápidos.

Algoritmos que no usaría, ya que su concepto es más difícil de obtener, son ShellSort, RadixSort, HeapSort y BucketSort. También son bastante especiales (por lo general, solo los usa al ordenar cierto tipo de datos o si tiene ciertas restricciones para la clasificación).

Puede mencionar a la hermanita de ShellSort, InsertionSort (que básicamente es un tipo de shell donde el ancho del paso finalmente ha llegado a uno), pero solo porque muchas implementaciones de QuickSort usan InesrtionSort como ordenación inversa, una vez que la recursión es demasiado profunda (o el conjunto de datos restante para ordenar recursivamente es demasiado pequeño) ... pero aquí comienza a ser realmente complicado y no debes hacerlo demasiado complicado.

Si quiere enseñar el concepto de clasificación, entonces creo que debe enseñar al menos dos formas diferentes de clasificación; de lo contrario, los estudiantes pensarán que la ordenación es solo la forma en que les enseñó.

Creo que los estudiantes obtendrían el mayor valor al aprender un algoritmo O (n ^ 2) clásico (preferiblemente ordenar por inserción o selección, pero no por tipo de burbuja, que no tiene justificación para ser utilizado en aplicaciones reales), así como Dividir y conquistar, algoritmo O (nlogn) como quicksort o merge sort.

Si le preocupa que estos tipos sean demasiado difíciles de enseñar a sus alumnos, eche un vistazo a estas actividades de Computer Science Unplugged , que están diseñadas para estudiantes de escuelas primarias.

Primero se les debe pedir que implementen su propio algoritmo de clasificación, desde cero, sin referencia previa a ningún algoritmo existente. Hacer esto les enseñará a ordenar mucho más que a decirles de un algoritmo que no tendrían ni idea de cómo se derivó.

Deja que tus estudiantes decidan.

Antes de introducir cualquier algoritmo de clasificación, dé a cada alumno algunas cartas, tal vez 10 o más. Luego, pídales que clasifiquen las tarjetas. Pídales que escriban los pasos que siguen, que serán esencialmente su algoritmo. Es probable que descubran la ordenación por inserción o selección. También puede pedirles que calculen cuántos pasos tomaría su clasificación si tuvieran 100 o 1000 cartas, lo cual es una buena pista para la notación O grande.

PD: ¿Alguien cree que descubriría sortear las burbujas?