Dada una matriz de longitud N. Puede contener valores que van de 1 a N^2 (N al cuadrado) ambos inclusive, los valores son integrales. ¿Es posible ordenar esta matriz en O (N) tiempo? Si es posible, ¿cómo?Una matriz de longitud N puede contener valores 1,2,3 ... N^2. ¿Es posible ordenar el tiempo O (n)?
Editar: Esto no es una tarea.
Escribe cada número entero en la base N, es decir, cada x se puede representar como (x1, x2) con x = 1 + x1 + x2 * N. Ahora puede ordenarlo dos veces con clasificación de conteo, una vez en x1 y una vez en x2, lo que da como resultado la matriz ordenada.
¿Qué es un 'tipo de conteo'? – Omnifarious
Una clasificación de cucharón de dos fases. Primero cuenta cuántas entradas tendrá un contenedor, y de ahí el índice de inicio de cada segmento (toma O (n)). Luego puede intercambiar las entradas en cada cubo en O (n) también. – CodesInChaos
Creo que el resto del mundo lo llama un tipo de raíz. – Omnifarious
Sí, puede hacerlo, usando radix sort con N cucharones y dos pases. Básicamente, usted trata los números como teniendo 2 dígitos en la base N.
no puedo entender 'x = 1 + x1 + x2 * N' como se indica en la respuesta aceptada. Si representamos el número en la base 'N',' N^2' se puede expresar en un máximo de 2 bits, x1 yx2, entonces 'x = x1 * n^0 + x2 * n^1' =' x1 + x2 * N' . Por favor aclara –
Es posible ordenar cualquier matriz de enteros con un valor máximo bien definido en el tiempo O(n) usando un radix sort. Este es probablemente el caso para cualquier lista de enteros que encuentre. Por ejemplo, si estuviera ordenando una lista de enteros de precisión arbitrarios, no sería cierto. Pero todos los tipos integrales C tienen rangos fijos bien definidos.
Si esta es una pregunta de tarea, por favor marque como tal. – danben
Sus valores son intergral, supongo? Puedes hacerlo con enteros – CodesInChaos
@CodeInChaos: Sí integral, agregué esa información en la pregunta, gracias. – riderchap