Check if an Array Is Sorted

Q: ¿Por qué basta con comprobar los vecinos?

La relación de orden es transitiva: si a ≤ b y b ≤ c , entonces a ≤ c . Así que, cuando cada par de elementos adyacentes está ordenado, todos los pares de posiciones también lo están. A la inversa, cualquier arreglo desordenado tiene al menos un par de elementos adyacentes en el que el valor disminuye.

Q: ¿Está ordenado un array con elementos iguales?

En orden no decreciente, sí: [4, 4, 4] está ordenado porque ningún elemento es mayor que el siguiente. Si un problema pide, en cambio, un orden estrictamente creciente, modifica la comprobación para que también rechace los elementos vecinos iguales.

Q: ¿Puedo ordenar una copia y compararla con el original?

Sí, y da la respuesta correcta, pero requiere un tiempo de O(n log n) y O(n) de memoria adicional para la copia. La comprobación de los vecinos es más rápida, no necesita ninguna copia y puede devolver el resultado en el primer paso hacia abajo sin leer el resto.

PrincipianteArrays y cadenas

+10

Se te proporciona un array de enteros nums. Devuelve true si está ordenado de forma no decreciente, es decir, si cada elemento es menor o igual que el siguiente, y false en caso contrario. Se permiten elementos vecinos iguales: [2, 2, 3] se considera ordenado. Un array con un solo elemento está ordenado.

Función

isSorted(nums: integer-array) → boolean

numsinteger-array: el arreglo de enteros que hay que comprobar
Devuelveboolean: true cuando cada elemento es menor o igual que el siguiente; false en caso contrario

Restricciones

1 ≤ nums.length ≤ 5000
-10⁹ ≤ nums[i] ≤ 10⁹

Ejemplos

Entrada: nums = [1, 3, 3, 7]
Salida: true
Explicación: Cada paso sube o se mantiene en el mismo nivel: de 1 a 3, de 3 a 3, de 3 a 7. Se permite repetir el 3, así que la respuesta es true.

Entrada: nums = [2, 5, 4, 9]
Salida: false
Explicación: El paso de 5 a 4 va hacia abajo. Un solo paso así basta para que el array quede desordenado, aunque 9 al final sea el valor más grande, así que la respuesta es false.

+16 pruebas ocultas al enviar

Para ir más allá

¿Cómo comprobarías en una sola pasada un array que puede estar ordenado en cualquiera de las dos direcciones, en orden creciente o decreciente?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Un arreglo está ordenado exactamente cuando ningún elemento es mayor que el que viene justo después. Nunca necesitas comparar elementos que estén muy separados: si cada par de elementos vecinos está en orden, todo el arreglo lo está. Así, la comprobación se convierte en un recorrido de una sola pasada por n-1 pares que puede detenerse en el primer descenso.

Ordena una copia y compárala

Intuición

Un arreglo ordenado es uno que no cambiaría al ordenarlo. Así que haz una copia de nums, ordena la copia y comprueba si coincide con el original posición por posición. Si todas las posiciones coinciden, nums ya estaba ordenado.

Para [2, 5, 4, 9], la copia ordenada es [2, 4, 5, 9]. La posición 1 contiene 5 en el original y 4 en la copia, así que la respuesta es false. Para [1, 3, 3, 7], la copia es idéntica y la respuesta es true.

Esto es correcto, pero hace más de lo que pide la pregunta. Ordenar cuesta O(n log n), aproximadamente 6 × 10^4 comparaciones para 5000 números, y la copia ocupa O(n) de memoria. Además, siempre lee todo el arreglo, incluso cuando el primer par ya está desordenado.

Algoritmo

Copia nums para que el original permanezca sin cambios.
Ordena la copia en orden numérico creciente.
Compara la copia con nums posición por posición.
Devuelve true si todas las posiciones coinciden; de lo contrario, false.

def isSorted(nums):
    # sorted returns a new list, so nums itself is left as it was.
    return sorted(nums) == nums

Compara cada par de vecinos

Intuición

No necesitas la versión ordenada para saber si el arreglo está ordenado. Un arreglo está en orden no decreciente exactamente cuando cada elemento es menor o igual que el que está justo después. Como las cadenas de ≤ (a ≤ b y b ≤ c dan a ≤ c), comprobar los n-1 pares vecinos cubre todos los pares de posiciones.

Recorre i desde 1 hasta n-1 y compara nums[i-1] con nums[i]. Para [2, 5, 4, 9], el par (2, 5) está bien y el par (5, 4) baja, así que devuelves false ahí mismo, sin mirar el 9. Los vecinos iguales pasan, porque solo falla >.

Se compara cada par una vez, así que el tiempo es O(n), y el índice del bucle es la única memoria adicional, O(1). Compara los dos valores directamente en lugar de restarlos: con valores de hasta 10^9, una diferencia puede desbordar un entero de 32 bits.

Algoritmo

Recorre en bucle i desde 1 hasta n-1.
Si nums[i-1] > nums[i], devuelve false.
Si el bucle termina, devuelve true. Un único elemento omite el bucle y está ordenado.

def isSorted(nums):
    for i in range(1, len(nums)):
        # One step down anywhere breaks the order.
        if nums[i - 1] > nums[i]:
            return False
    return True

Errores comunes y casos límite

El bucle es corto, así que los errores están en sus extremos y en la comparación.

Considerar que los elementos vecinos iguales son un fallo. Comprobar nums[i-1] >= nums[i] rechaza [1, 3, 3, 7]. Solo un descenso estricto (>) rompe el orden.
Leer más allá del final. Un bucle de 0 a n-1 que compara nums[i] con nums[i+1] debe detenerse una iteración antes, o leerá fuera del array. Empezar en i = 1 y comparar con i-1 evita el problema.
Restar en lugar de comparar. nums[i] - nums[i-1] >= 0 parece lo mismo, pero 10^9 - (-10^9) = 2 × 10^9 no cabe en un int de 32 bits y se desborda hasta convertirse en un número negativo, por lo que [-1000000000, 1000000000] se considera desordenado. El mismo desbordamiento rompe un comparador de qsort escrito como x - y.
Ordenar números como texto. En JavaScript, sort() sin una función de comparación coloca 10 antes de 9, así que una comprobación que ordena y compara da respuestas incorrectas.

Preguntas frecuentes4

¿Cómo se comprueba si un arreglo está ordenado?

Compara cada elemento con el siguiente. Si algún elemento es mayor que su vecino de la derecha, el array no está ordenado y puedes detenerte; si llegas al final sin encontrar ninguno, sí lo está. Esto requiere un tiempo de O(n) y un espacio adicional de O(1).

¿Por qué basta con comprobar los vecinos?

La relación de orden es transitiva: si a ≤ b y b ≤ c, entonces a ≤ c. Así que, cuando cada par de elementos adyacentes está ordenado, todos los pares de posiciones también lo están. A la inversa, cualquier arreglo desordenado tiene al menos un par de elementos adyacentes en el que el valor disminuye.

¿Está ordenado un array con elementos iguales?

En orden no decreciente, sí: [4, 4, 4] está ordenado porque ningún elemento es mayor que el siguiente. Si un problema pide, en cambio, un orden estrictamente creciente, modifica la comprobación para que también rechace los elementos vecinos iguales.

¿Puedo ordenar una copia y compararla con el original?

Sí, y da la respuesta correcta, pero requiere un tiempo de O(n log n) y O(n) de memoria adicional para la copia. La comprobación de los vecinos es más rápida, no necesita ninguna copia y puede devolver el resultado en el primer paso hacia abajo sin leer el resto.

Python

def isSorted(nums):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Entrada

nums = [1, 3, 3, 7]

Esperado

true