Estoy buscando un algoritmo sin comparación o basado en la comparación que pueda ordenar una matriz que contenga cualquier permutación de los primeros n enteros positivos, que debería ser O (n) complejidad de tiempo y O (1) complejidad del espacio.Ordenar primero n enteros en tiempo lineal y espacio constante
¿Existe un algoritmo que se ajuste a estas especificaciones?
Si tiene una matriz de tamaño N con todos los enteros de 1 a N presentes, puede usar el siguiente algoritmo O (N) (Nota: las matrices están basadas en 1 para este pseudocódigo para no introducir innecesarios complejidad al explicar el algoritmo):
@Michael Goldshteyn: si tiene una una matriz de longitud N que contiene todos los enteros de 1 a N, ¿por qué la ordenarías cuando pudieras escribir los enteros en orden en la matriz? –
@Mark, Tal vez está considerando el caso en que los enteros son simplemente claves para los registros. Aquí, simplemente escribir los enteros en orden no ayudará a poner los registros asociados en orden ordenado. –
sí, estoy considerando el caso en el que los enteros son claves, disculpe por no mencionar que – fmunshi
Ese algoritmo es hermoso en su simplicidad. Tendré que encontrar una excusa para usarlo algún día. –
Cuando está seguro de que todos los enteros están entre 1 y N, puede usar counting sort
Pensé que necesitaba un espacio constante. wiki de contar clasificación - "Debido a que usa matrices de longitud k + 1 yn, el uso de espacio total del algoritmo también es O (n + k). " – sreeprasad
sí, pero por lo general es k << n – anijhaw
¿Están todos enteros o hay espacios? –
¿Qué hay de simplemente escribir todos los enteros de 1 a n en la matriz? –
O (n) relativo a qué? Un algoritmo puramente in situ (sin almacenamiento lateral) sería O (1) en el tamaño de su entrada ... Ah, y O (n) tiempo o almacenamiento? –