El problema algorítmico de ordenar un conjunto de elementos con respecto a alguna relación de ordenamiento.
En un curso de algoritmos estándar se nos enseña que quicksort es en promedio y en el peor de los casos. Al mismo tiempo, se estudian otros algoritmos de clasificación que son en el peor de los casos (como mergesort y heapsort ), e incluso tiempo lineal en el mejor de los casos (como bubbleort )...
Hay dos métodos de partición de clasificación rápida mencionados en Cormen: Hoare-Partition(A, p, r) x = A[p] i = p - 1 j = r + 1 while true repeat j = j - 1 until A[j] <= x repeat i = i + 1 until A[i] >= x if i < j swap( A[i], A[j] ) else return j y: Lomuto-Partition(A, p,...
Me he encontrado con muchos algoritmos de clasificación durante mis estudios de secundaria. Sin embargo, nunca sé cuál es el más rápido (para una matriz aleatoria de enteros). Entonces mis preguntas son: ¿Cuál es el algoritmo de clasificación más rápido conocido actualmente? Teóricamente, ¿es...
Tengo problemas para encontrar buenos recursos que den el peor de los casos en su lugar estableO ( n lnn )O(norteEnnorte)O(n \ln n) algoritmo de clasificación . ¿Alguien sabe de algún buen recurso? Solo un recordatorio, en su lugar significa que usa la matriz que se pasa y el algoritmo de...
Me pregunto si hay una forma estándar de medir la "clasificación" de una matriz. ¿Se consideraría una matriz que tiene el número medio de posibles inversiones máximamente sin clasificar? Con eso quiero decir que está básicamente lo más lejos posible de ser ordenado o
¿Cuál sería la forma más rápida de hacer esto (desde una perspectiva algorítmica, así como una cuestión práctica)? Estaba pensando algo en las siguientes líneas. Podría agregar al final de una matriz y luego usar bubbleort, ya que tiene un mejor caso (matriz totalmente ordenada al inicio) que...
Tengo un conjunto de pares. Cada par tiene la forma (x, y) de modo que x, y pertenecen a enteros del rango [0,n). Entonces, si n es 4, entonces tengo los siguientes pares: (0,1) (0,2) (0,3) (1,2) (1,3) (2,3) Ya tengo las parejas. Ahora, tengo que construir una combinación usando n/2pares de...
Está escrito en Wikipedia que "... el tipo de selección casi siempre supera al de burbuja y al de gnomos". ¿Alguien puede explicarme por qué el ordenamiento por selección se considera más rápido que el ordenamiento por burbujas aunque ambos tengan: La peor complejidad del tiempo del caso...
Estoy buscando un algoritmo para distribuir valores de una lista para que la lista resultante esté lo más "equilibrada" o "distribuida de manera uniforme" posible (entre comillas porque no estoy seguro de que estas sean las mejores formas de describirla ... más adelante proporcionaré una forma de...
Un sorprendente número de problemas tiene reducciones bastante naturales a la programación lineal (LP). Consulte el Capítulo 7 de [1] para ver ejemplos como flujos de red, emparejamiento bipartito, juegos de suma cero, rutas más cortas, una forma de regresión lineal e incluso evaluación de...
En la clasificación por radix primero ordenamos por el dígito menos significativo, luego ordenamos por el segundo dígito menos significativo y así sucesivamente, y terminamos con una lista ordenada. Ahora, si tenemos una lista de nnn números, necesitamos lognlogn\log n bits para distinguir entre...
Los algoritmos de clasificación genéricos generalmente toman un conjunto de datos para clasificar y una función de comparación que puede comparar dos elementos individuales. Si el comparador es una relación de orden¹, la salida del algoritmo es una lista / matriz ordenada. Sin embargo, me pregunto...
Encuentre la menor cantidad de comparaciones necesarias para ordenar (ordenar) cinco elementos e idee un algoritmo que clasifique estos elementos usando esta cantidad de comparaciones. Solución : ¡ Hay 5! = 120 resultados posibles. Por lo tanto, un árbol binario para el procedimiento de...
En el sitio web de Algoritmos de clasificación , se realiza el siguiente reclamo: El algoritmo de ordenación ideal tendría las siguientes propiedades: Estable: las claves iguales no se reordenan. Opera en su lugar, requiriendo espacio extra.O(1)O(1)O(1) El peor de los casos comparaciones...
La clasificación por radix es teóricamente muy rápida cuando se sabe que las claves están en un cierto rango limitado, digamos valores en el rango por ejemplo. Si simplemente convierte los valores a base que lleva tiempo , realice una clasificación de base radix y luego vuelva a convertir a su base...
Considere el siguiente problema: Entrada: dos matrices y de longitud , donde está en orden.B n BAAABBBnnnBBB Consulta: ¿ y contienen los mismos elementos (con su multiplicidad)?BAAABBB ¿Cuál es el algoritmo determinista más rápido para este problema? ¿Se puede resolver más rápido que...
Estoy buscando un algoritmo de ordenación para matrices int que no asigne ningún byte que no sea el tamaño de la matriz, y se limita a dos instrucciones: SWAP: intercambia el siguiente índice con el actual; MOVER: mueve el cursor al índice +1 o -1; Es decir, no puede intercambiar índices no...
¿Cómo puedo ordenar una lista de 5 enteros de modo que en el peor de los casos se necesitan 7 comparaciones? No me importa cuántas otras operaciones se realizan. No sé nada en particular sobre los enteros. He intentado algunos enfoques diferentes de dividir y conquistar que me llevan a 8...
En su libro Algoritmos aleatorios , Motwani y Raghavan abren la introducción con una descripción de su función RandQS - Randomized quicksort - donde el pivote, utilizado para dividir el conjunto en dos partes, se elige al azar. He estado estacionando mis cerebros (ciertamente algo poco poderosos)...
La ordenación rápida aleatoria es una extensión de la ordenación rápida en la que el elemento pivote se elige aleatoriamente. ¿Cuál puede ser la peor complejidad de tiempo de este algoritmo? Según yo, debería ser , ya que el peor de los casos ocurre cuando el pivote elegido al azar se selecciona en...