Ordenar es un concepto sencillo pero poderoso. A partir de una lista desordenada de elementos, se puede utilizar un algoritmo para ordenarlos de una manera determinada. Aunque esta idea pueda parecer básica, ordenar es algo que aparece a lo largo de toda la informática en muchos aspectos y formas diferentes. Una de las aplicaciones más importantes es la aceleración de las búsquedas. Por ejemplo, tu ordenador ordena los archivos por nombre y tamaño para que puedas encontrar rápidamente el que necesitas. UEFN te permite ordenar objetos en el esquematizadorpor tipo para agrupar cosas y organizar tu proyecto. En Fortnite, los jugadores en el marcador del juego se ordenan por muchas estadísticas diferentes, como eliminaciones y tiempo de vuelta, para que todo el mundo sepa quién es el mejor.
Ordenar en el código de Verse puede ayudarte a subir de nivel y mejorar aspectos de tu desarrollo. Por ejemplo, ¿qué te parece ordenar un conjunto de jugadores por su puntuación en un torneo, en el que los jugadores que hayan obtenido la menor puntuación en cada ronda queden eliminados? Si ordenas esta matriz al final de cada ronda, podrás encontrar rápidamente a los que hayan obtenido menos puntos y asignarlos como espectadores. Por otro lado, puedes coger solo a los jugadores con la mejor puntuación y concederles una bonificación para la siguiente ronda. Incluso puedes utilizar esta lista ordenada para crear marcadores locales persistentes, para que los jugadores sepan a quién tienen que vigilar durante la partida. Y si tienes una lista de personas a las que te gustaría nombrar en la isla, puedes ordenar sus nombres alfabéticamente para facilitar la visualización.
Cada uno de estos ejemplos utiliza la ordenación de formas diferentes, pero en el fondo, todos utilizan un algoritmo de ordenación para lograr su objetivo. Los algoritmos de ordenación implementan la lógica que ordena tus listas, y hay muchos tipos diferentes entre los que elegir en función de lo que necesites. Aunque ordenar es una herramienta potente, es importante entender cómo funciona si quieres integrarla en tus proyectos. Esta página cubre las ideas principales detrás de la ordenación y cómo elegir el algoritmo que mejor funcione para tu proyecto. Para ver implementaciones de algoritmos de ordenación específicos, consulta el enlace al final de esta página.
Ordenación por combinación
La ordenación por combinación es un algoritmo de ordenación del tipo «divide y vencerás». Esto significa que divide el grupo de elementos que deben ordenarse en grupos más pequeños y los ordena. A continuación, combina los grupos más pequeños sabiendo que ya están ordenados.
Cómo implementar la ordenación por combinación
La siguiente implementación se llama a sí misma para ordenar por combinación las matrices divididas, lo que significa que es una función recursiva. Cuando se tiene una función recursiva, es necesario especificar un caso base para evitar la recursividad infinita. Dado que este algoritmo divide las matrices por la mitad cada vez, el caso base es la matriz de un solo elemento, por lo que la matriz se considera ordenada para empezar con un elemento y se puede combinar con otra matriz de un solo elemento, y así sucesivamente hasta llegar a la matriz completa de elementos.
La siguiente es una implementación genérica que utiliza tipos paramétricos para sus parámetros. Esto significa que puedes utilizar el tipo que desees para los elementos y tu propia función de comparación como argumentos. Así que puedes tener una matriz de enteros que ordenas o una matriz de un tipo más complejo como una clase que puedes ordenar. La función Compare es otro parámetro al que puedes pasar tus propias funciones personalizadas. Si quieres ordenar de menor a mayor, o por determinados campos de una clase, puedes especificarlo en tu función personalizada, sin modificar la implementación de esta función genérica.
Sigue estos pasos para implementar la ordenación por combinación en Verse:
-
Empecemos por escribir el caso base: solo un elemento en la matriz. Si hay un elemento o menos, devuelve el argumento de la matriz que se pasó a la función.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Verifica que hay más de un elemento en la matriz; de lo contrario, hemos llegado al caso base. else: # Devuelve la matriz pasada porque hemos llegado al caso base. Matriz -
A continuación, divide la matriz por la mitad.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Verifica que hay más de un elemento en la matriz; de lo contrario, hemos llegado al caso base. Mid:int = Floor(Length / 2) # Obtén el índice medio de la matriz. Left:[]t = Array.Slice[0, Mid] # Divide la matriz por la mitad. Esto mantiene los elementos desde el principio hasta la mitad del índice - 1. Right:[]t = Array.Slice[Mid] # Divide la matriz por la mitad. Mantiene los elementos desde la mitad del índice hasta el final de la matriz. else: # Devuelve la matriz pasada porque hemos llegado al caso base. Matriz -
Llama a
MergeSorten cada mitad del array inicial y, a continuación, ejecutaMergepara las dos mitades juntas.MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Length > 1 # Verifica que hay más de un elemento en la matriz; de lo contrario, hemos llegado al caso base. Mid:int = Floor(Length / 2) # Obtén el índice medio de la matriz. Left:[]t = Array.Slice[0, Mid] # Divide la matriz por la mitad. Esto mantiene los elementos desde el principio hasta la mitad del índice - 1. Right:[]t = Array.Slice[Mid] # Divide la matriz por la mitad. Mantiene los elementos desde la mitad del índice hasta el final de la matriz. then: # Llama a MergeSort en la mitad izquierda de la matriz. LeftSorted:[]t = MergeSort(Left, Compare) # Llama a MergeSort en la mitad derecha de la matriz. RightSorted:[]t = MergeSort(Right, Compare) # Combina las dos matrices y devuelve el resultado. Merge(LeftSorted, RightSorted, Compare) else: # Devuelve la matriz pasada porque hemos llegado al caso base. Matriz -
Cuando vuelvas a combinar las dos mitades, compara los elementos de cada matriz y añádelos a la matriz resultante hasta que se hayan añadido todos los elementos de ambas matrices. Para ello, dispón de una variable de índice para realizar un seguimiento de las posiciones en cada matriz. Cada vez que la función
Comparese completa correctamente, el elemento izquierdo de la matriz debe añadirse y su variable índice debe avanzar a la siguiente posición en la matriz. En caso contrario, haz lo mismo con el elemento derecho de la matriz. Una vez añadidos todos los elementos de una de las matrices, añade los elementos restantes de la otra matriz, puesto que ya está ordenada.# Una función de ayuda para MergeSort que combina las matrices divididas en un orden basado en la función Compare. Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= var LeftIndex:int = 0 var RightIndex:int = 0 var MergedArray:[]t = array{} # Recorre en bucle todos los elementos de las matrices para añadirlos a la variable MergedArray. loop: if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]): # Comprueba el elemento de la mitad izquierda de la matriz con el elemento de la mitad derecha de la matriz. # Utiliza la función Compare pasada como argumento if (Compare[LeftElement, RightElement]): set MergedArray += array{LeftElement} set LeftIndex += 1 else: set MergedArray += array{RightElement} set RightIndex += 1 else: # En este punto hemos añadido todos los elementos de una de las matrices. # Ahora comprueba qué matriz tiene todavía elementos para combinar y añade todos los elementos restantes. if (LeftIndex >= Left.Length): option{set MergedArray += Right.Slice[RightIndex]} else: option{set MergedArray += Left.Slice[LeftIndex]} # Sal del bucle porque hemos terminado de añadir todos los elementos. break # Devuelve la matriz combinada. MergedArray
Script completo
# Un algoritmo de ordenación de tipo «divide y vencerás» que separa los vectores en dos, organiza cada vector dividido y luego los mezcla.
# Se trata de una implementación recursiva, en la que la función se llama a sí misma para combinar la ordenación de las matrices divididas.
# El caso base (la condición para detener la recursión) es que la matriz tenga solo un elemento.
# Se trata de una implementación genérica que utiliza tipos paramétricos, por lo que puede proporcionar su propio tipo y su propia función de comparación como argumentos.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
Length:int = Array.Length
if:
Length > 1 # Verifica que hay más de un elemento en la matriz; de lo contrario, hemos llegado al caso base.
Mid:int = Floor(Length / 2) # Obtén el índice medio de la matriz.
Left:[]t = Array.Slice[0, Mid] # Divide la matriz por la mitad. Esto mantiene los elementos desde el principio hasta la mitad del índice - 1.
Right:[]t = Array.Slice[Mid] # Divide la matriz por la mitad. Mantiene los elementos desde la mitad del índice hasta el final de la matriz.
then:
# Llama a MergeSort en la mitad izquierda de la matriz.
LeftSorted:[]t = MergeSort(Left, Compare)
# Llama a MergeSort en la mitad derecha de la matriz.
RightSorted:[]t = MergeSort(Right, Compare)
# Combina las dos matrices y devuelve el resultado.
Merge(LeftSorted, RightSorted, Compare)
else:
# Devuelve la matriz pasada porque hemos llegado al caso base.
Matriz
# Una función de ayuda para MergeSort que combina las matrices divididas en un orden basado en la función Compare.
Merge(Left:[]t, Right:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
var LeftIndex:int = 0
var RightIndex:int = 0
var MergedArray:[]t = array{}
# Recorre en bucle todos los elementos de las matrices para añadirlos a la variable MergedArray.
loop:
if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
# Comprueba el elemento de la mitad izquierda de la matriz con el elemento de la mitad derecha de la matriz.
# Utiliza la función Compare pasada como argumento
if (Compare[LeftElement, RightElement]):
set MergedArray += array{LeftElement}
set LeftIndex += 1
else:
set MergedArray += array{RightElement}
set RightIndex += 1
else:
# En este punto hemos añadido todos los elementos de una de las matrices.
# Ahora comprueba qué matriz tiene todavía elementos para combinar y añade todos los elementos restantes.
if (LeftIndex >= Left.Length):
option{set MergedArray += Right.Slice[RightIndex]}
else:
option{set MergedArray += Left.Slice[LeftIndex]}
# Sal del bucle porque hemos terminado de añadir todos los elementos.
break
# Devuelve la matriz combinada.
MergedArray
Cómo escoger un algoritmo
Aunque muchos algoritmos de ordenación siguen ideas similares, hay algunas cosas que diferencian a cada uno de ellos y que pueden tener un gran impacto en el rendimiento del algoritmo.
Complejidad temporal
Los algoritmos llevan tiempo y, cuantas más cosas tengan que hacer, más tardarán. Hay una serie de factores que influyen en la complejidad del problema que intenta resolver el algoritmo, y la cantidad de tiempo que se tarda en resolverlo se denomina complejidad temporal.
Dado que calcular el tiempo exacto que tardará un algoritmo en terminar es casi imposible debido a diversos factores, como el hardware del ordenador, otro código en ejecución o el tipo de datos con los que se trabaja, la complejidad temporal se mide en operaciones, es decir, el número de acciones que debe realizar un algoritmo para terminar. Como cada algoritmo es diferente, la cantidad de tiempo que se tarda en procesar un conjunto de datos se representa con la notación big O. La notación Big O no describe el número exacto de operaciones necesarias, sino cómo cambia ese número a medida que aumenta el tamaño de la lista que se introduce en el algoritmo.
Por ejemplo, digamos que escribes un algoritmo para encontrar el número más pequeño de una lista. No sabes si la lista está ordenada, por lo que el algoritmo tiene que comprobar cada número para saber si es el más pequeño. Si hay tres elementos en la lista, el algoritmo hace tres comprobaciones, y, si hay diez elementos, el algoritmo hace diez. Como el número de operaciones aumenta linealmente con el tamaño de entrada de la lista, la complejidad temporal es lineal, u O(n), donde n es el número de elementos de la lista. Si tu algoritmo tuviera que hacer dos operaciones por elemento, como copiar cada elemento en una lista diferente después de cada comprobación, la complejidad temporal sería O(2n) ya que el número de operaciones es dos veces el número de elementos.
¿Y si tu algoritmo solo quisiera comprobar si hay algún elemento en la lista? Dado que tu algoritmo solo realiza una operación independientemente del tamaño de la entrada, la complejidad temporal sería constante, u O(1). Hay muchos otros ejemplos, como el tiempo cuadrático (O(n^2)) o el tiempo factorial (O(n!)), pero lo que importa es que cada uno de ellos describe cómo el número de operaciones realizadas crece con el tamaño de la entrada.
La complejidad en la ordenación
Medir la complejidad temporal de los algoritmos de ordenación es mucho más complicado debido a los diferentes estados en los que puede encontrarse una lista antes de ordenarse. ¿Y si ya se ha ordenado? ¿Y si se ha ordenado al revés? El rendimiento de un algoritmo de ordenación puede variar drásticamente en función de estos factores, por lo que los algoritmos de ordenación suelen medirse por su complejidad temporal en el mejor, el peor y el caso promedio.
Por ejemplo, veamos el algoritmo de ordenación por burbujas. En el mejor de los casos, dada una lista ya ordenada, la ordenación por burbujas solo necesita comprobar cada par de elementos, pero no tendrá que hacer ningún intercambio. Esto significa que la complejidad temporal en el mejor de los casos será O(n), ¡lo cual es genial! Sin embargo, ¿qué ocurre en el caso contrario, en el que la lista se ordena al revés? En esta situación, la ordenación por burbujas tendrá que hacer un número n de comprobaciones e intercambiar cada elemento de la lista n veces, lo que significa que la complejidad temporal en el peor de los casos será n * n o O(n^2). Esto se considera lento en comparación con otros algoritmos de ordenación y puede irse de las manos muy rápido, ya que el algoritmo tardaría al menos cien operaciones en procesar una lista de diez elementos. ¿Te imaginas cuántas operaciones requerirían cien elementos? ¿Y mil?
En lugar del mejor y el peor caso, los algoritmos de ordenación suelen rendir más cerca de su caso medio. Por ejemplo, la complejidad media de la ordenación por combinación es O(nlogn). Se considera un buen punto de referencia, ya que muchos otros algoritmos de ordenación comunes tienen complejidades en el mejor, peor y medio de los casos iguales o muy cercanas a este nivel. La ordenación por burbujas de antes tiene una complejidad media de O(n^2), por lo que incluso en el caso medio, sigue siendo relativamente lenta.
Conocer la complejidad temporal es importante a la hora de elegir un algoritmo, ya que lo que se busca es que el código se ejecute rápido y funcione de forma similar independientemente del tipo de entrada. Para ver algunos ejemplos de algoritmos de ordenación eficaces, consulta Ordenación por combinación y Ordenamiento rápido. Ambos algoritmos tienen las mismas complejidades en el mejor, el peor y el caso medio de O(nlogn), y son un buen punto de partida para cualquier situación de ordenación.
Complejidad espacial
Además de la complejidad temporal, también es importante tener en cuenta cuántas cosas tiene que crear tu algoritmo para terminar de ordenar. Se trata de la complejidad espacial o la cantidad de datos adicionales que se crean al ejecutar el algoritmo. Al igual que la complejidad temporal, la complejidad espacial se mide con la notación Big O , que varía según los algoritmos. Por ejemplo, como la ordenación por combinación divide una lista en n sublistas, tiene una complejidad espacial de O(n). Los algoritmos que ordenan objetos en su lugar (es decir, que solo modifican datos existentes sin crear otros nuevos) tienen una complejidad espacial de O(1). Si trabajas con listas muy grandes, puede que debas tener en cuenta la complejidad espacial al seleccionar el algoritmo.
Dado que Verse es un lenguaje de programación funcional, las operaciones de la API de estructura de datos devuelven versiones modificadas del elemento original pasadas como entrada. Por ejemplo, las funciones de matriz Insert() y RemoveElement() no modifican la matriz original, sino que crean y devuelven una nueva matriz tras ejecutar la función. Esto puede dar lugar a mayores requisitos de complejidad temporal y espacial a la hora de crear estos nuevos elementos.
Estabilidad
Durante la ordenación, el algoritmo suele toparse con vínculos. Por ejemplo, si hay dos jugadores y cada uno tiene una puntuación de cinco, ¿cómo debe ordenarlos el algoritmo? En este escenario, un algoritmo estable mantendrá el orden en que aparecen los elementos iguales en la lista después de la ordenación. Si el jugador uno estaba antes que el jugador dos en la lista previa a la ordenación, la lista ordenada mantendrá al jugador uno antes que el jugador dos.
Sin embargo, un algoritmo inestable no mantendrá este orden, por lo que el jugador dos podría aparecer antes que el jugador uno. Esto es importante si en tu código importan los primeros elementos de una lista (por ejemplo, si quisieras que los tres mejores jugadores por puntuación se muestren en un marcador). En esa situación, sería conveniente contar con un algoritmo estable para garantizar que quien consiga primero esa puntuación permanezca en el marcador.
Cómo probar y perfilar tus algoritmos
Aunque está bien saber cómo se espera que funcione el algoritmo dada la complejidad temporal y espacial, es aún más importante medir cómo funciona de verdad con entradas reales. Desarrollar algoritmos de ordenación puede ser difícil, ya que es complejo identificar si el código funciona de manera coherente en todas las entradas. Aquí es donde entran en juego las pruebas. Al configurar una función de prueba, puedes medir la precisión del código e identificar cómo se comporta a medida que lo desarrollas. También puedes ver si hay alguna regresión en el rendimiento al cambiar la implementación de lo que estás probando. Sigue estos pasos para configurar un archivo de prueba para los algoritmos de ordenación y generar datos sobre su rendimiento:
-
Crea una función que pueda fallar nombrada
RunArrayTest.# Función de prueba para ordenar matrices y perfilar el código. RunArrayTest()<decides><transacts>:void= -
Añade el argumento para la matriz donde quieras ejecutar la ordenación y la función de comparación que se va a utilizar.
# Función de prueba para ordenar matrices y perfilar el código. RunArrayTest(ActualArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void= # Ejecuta la ordenación por combinación. ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) -
Ahora debes comparar la matriz ordenada con lo que se espera. Añade el argumento para comparar la matriz esperada con la matriz real ordenada y comprueba que el resultado sea correcto.
Compara los elementos de
ResultArraycon los deExpectedArray. La funciónRunArrayTestpuede fallar si un elemento no coincide.# Función de prueba para ordenar matrices y perfilar el código. RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void= # Ejecuta la ordenación por combinación. ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # Asegúrate de que se haya pasado la prueba y la matriz se haya ordenado como se esperaba. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected -
Añade una función de argumento para imprimir las matrices a cada paso, compararlas si la prueba falla y saber cómo arreglar el código que estás probando.
# Función de prueba para ordenar matrices y perfilar el código. RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void= # Ejecuta la ordenación por combinación. ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # Imprime las matrices real, prevista y final para la resolución de problemas. ProjectLog("Real: {ArrayToString(ActualArray)}") ProjectLog("Prevista: {ArrayToString(ExpectedArray)}") ProjectLog("Final: {ArrayToString(ResultArray)}") # Asegúrate de que se haya pasado la prueba y la matriz se haya ordenado como se esperaba. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected -
La función de prueba verifica la precisión del resultado, pero también te permite obtener más información de la prueba. Al utilizar la expresión de perfil, puedes medir el rendimiento de tus algoritmos si registras el tiempo que tarda el algoritmo en completarse.
Esto es útil si quieres comparar el rendimiento de diferentes algoritmos de ordenación o probar cómo se ejecutan los algoritmos con diferentes entradas. Los algoritmos individuales pueden funcionar de manera muy diferente según los mejores y peores casos de entrada, y la creación de perfiles te permite encontrar y probar dichos casos para saber qué buscar. Tras hacer varias pruebas, podrás medir el rendimiento promedio de tu algoritmo y estimar cómo funcionará en entradas de cualquier tamaño.
-
Añade un argumento de cadena denominado
Descriptionque explique en qué se centra la prueba. Puedes añadirlo a la expresiónprofilepara registrar la descripción con el valor cronometrado.# Función de prueba para ordenar matrices y perfilar el código. RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void= # Ejecuta la ordenación por combinación y el perfilado del código. ResultArray := profile(Description): SortingAlgorithms.MergeSort(ActualArray, Compare) # Imprime las matrices real, prevista y final para la resolución de problemas. ProjectLog("Real: {ArrayToString(ActualArray)}") ProjectLog("Prevista: {ArrayToString(ExpectedArray)}") ProjectLog("Final: {ArrayToString(ResultArray)}") # Asegúrate de que se haya pasado la prueba y la matriz se haya ordenado como se esperaba. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected
Casos de prueba de escritura
Empieza por lo fácil. Aísla lo que estás probando. Prueba una matriz de enteros para ordenar del valor más pequeño al más grande.
-
Crea una función de comparación para enteros.
# Función de comparación que se utilizará como argumento para ordenar enteros de menor a mayor. IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int= Left < Right -
Crea una función auxiliar para convertir una matriz de enteros en una cadena.
# Función auxiliar para convertir una matriz de enteros en una cadena. IntArrayToString(Array:[]int)<transacts>:string= var ConvertedToString:string = "[" for (Index -> Element : Array): set ConvertedToString += "{Element}" if (Index < Array.Length - 1): set ConvertedToString += ", " set ConvertedToString += "]" -
Crea un dispositivo Verse para ejecutar la prueba.
# Este archivo contiene pruebas para verificar que el algoritmo de ordenación se comporta de la manera prevista. # Las pruebas también incluyen el perfilado del código para ver el rendimiento del algoritmo. using { /Fortnite.com/Devices } using { /UnrealEngine.com/Temporary/Diagnostics } using { /Verse.org/Simulation } using { /Verse.org/Random } my_log_channel<public> := class(log_channel): # Un «registrador» de todo el proyecto para imprimir mensajes de funciones que no están en una clase con un registro. # La impresión que no es de registrador es <no_rollback>, por lo que no se puede usar en una función de <transacts>. ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void= Logger := log{Channel := my_log_channel} Logger.Print(Message, ?Level := Level) # Un dispositivo del modo creativo creado en Verse que se puede colocar en un nivel. # Colócalo en el nivel para ejecutar pruebas y perfilar el código. test_sorting := class(creative_device): # Se ejecuta cuando se inicia el dispositivo en un juego en ejecución OnBegin<override>()<suspends>:void= # Matrices de ejemplo que se usarán para la prueba. Test1ExpectedIntArray:[]int = array{} Test1ActualIntArray:[]int = array{} # Ejecuta las pruebas y notifica si se han completado correctamente o no. if: RunArrayTest["Matriz de enteros ordenada de menor a mayor", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString] then: ProjectLog("Todas las pruebas superadas.") else: ProjectLog("Una o más pruebas fallidas.") -
Ahora rellena las matrices de prueba con valores.
var ArrayLength:int = GetRandomInt(10, 100) Test1ExpectedIntArray:[]int = for (Count := 0..ArrayLength): Recuento Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray) -
Arrastra el dispositivo Verse a tu nivel para ejecutar la prueba.
A continuación, se muestran más opciones de pruebas que puedes ejecutar:
* Ordena una matriz de enteros de mayor a menor.
# Función de comparación que se utilizará como argumento para ordenar enteros de mayor a menor.
IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
Left > Right
* Ordena una matriz de enteros con valores repetidos.
Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}
Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)
* Ordena una clase por uno de sus campos.
# Una clase de ejemplo para probar la ordenación.
player_stats := class<unique>:
Wins:int = 0
RoundsPlayed:int = 0
# Función de comparación que se utilizará como argumento para ordenar victorias de menor a mayor.
IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins < Right.Wins
Izquierda
# Función auxiliar para convertir los valores de comparación estadística del jugador en una cadena.
PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string=
var ConvertedToString:string = "["
for (Index -> Element : Array):
set ConvertedToString += "{Element.Wins}"
if (Index < Array.Length - 1):
set ConvertedToString += ", "
set ConvertedToString += "]"
Script completo
# Este archivo contiene pruebas para verificar que el algoritmo de ordenación se comporta de la manera prevista.
# Las pruebas también incluyen el perfilado del código para ver el rendimiento del algoritmo.
using { /Fortnite.com/Devices }
using { /UnrealEngine.com/Temporary/Diagnostics }
using { /Verse.org/Simulation }
using { /Verse.org/Random }
my_log_channel<public> := class(log_channel):
# Un «registrador» de todo el proyecto para imprimir mensajes de funciones que no están en una clase con un registro.
# La impresión que no es de registrador es <no_rollback>, por lo que no se puede usar en una función de <transacts>.
ProjectLog<public>(Message:[]char, ?Level:log_level = log_level.Normal)<transacts>:void=
Logger := log{Channel := my_log_channel}
Logger.Print(Message, ?Level := Level)
# Un dispositivo del modo creativo creado en Verse que se puede colocar en un nivel.
# Colócalo en el nivel para ejecutar pruebas y perfilar el código.
test_sorting := class(creative_device):
# Se ejecuta cuando se inicia el dispositivo en un juego en ejecución
OnBegin<override>()<suspends>:void=
# Matrices de ejemplo que se usarán para la prueba.
var ArrayLength:int = GetRandomInt(10, 100)
Test1ExpectedIntArray:[]int =
for (Count := 0..ArrayLength):
Recuento
Test1ActualIntArray:[]int = Shuffle(Test1ExpectedIntArray)
set ArrayLength = GetRandomInt(10, 100)
Test2ExpectedIntArray:[]int = for (Count := 0..ArrayLength):
ArrayLength - Count
Test2ActualIntArray:[]int = Shuffle(Test2ExpectedIntArray)
Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}
Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)
set ArrayLength = GetRandomInt(10, 100)
Test4ExpectedPlayerStats:[]player_stats = for (Count := 0..ArrayLength):
player_stats:
Wins := ArrayLength - Count
RoundsPlayed := GetRandomInt(Count, Count * 30)
Test4ActualPlayerStats:[]player_stats = Shuffle(Test4ExpectedPlayerStats)
# Ejecuta las pruebas y notifica si se han completado correctamente o no.
if:
RunArrayTest["Matriz de enteros ordenada de menor a mayor", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
RunArrayTest["Matriz de enteros ordenada de mayor a menor", Test2ActualIntArray, Test2ExpectedIntArray, IsIntGreaterThan, IntArrayToString]
RunArrayTest["Matriz de enteros ordenada de menor a mayor con repeticiones", Test3ActualIntArray, Test3ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
RunArrayTest["Matriz de estadísticas del jugador de mayor a menor número de victorias", Test4ActualPlayerStats, Test4ExpectedPlayerStats, IsWinsGreaterThan, PlayerStatsWinsArrayToString]
then:
ProjectLog("Todas las pruebas superadas.")
else:
ProjectLog("Una o más pruebas fallidas.")
# Función de prueba para ordenar matrices y perfilar el código.
RunArrayTest(Description:string, ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t, ArrayToString(:[]t)<transacts>:string where t:subtype(comparable))<decides><transacts>:void=
# Ejecuta la ordenación por combinación y el perfilado del código.
ResultArray := profile(Description):
SortingAlgorithms.MergeSort(ActualArray, Compare)
# Imprime las matrices real, prevista y final para la resolución de problemas.
ProjectLog("Real: {ArrayToString(ActualArray)}")
ProjectLog("Prevista: {ArrayToString(ExpectedArray)}")
ProjectLog("Final: {ArrayToString(ResultArray)}")
# Asegúrate de que se haya pasado la prueba y la matriz se haya ordenado como se esperaba.
for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
Result = Expected
# Función auxiliar para convertir una matriz de enteros en una cadena.
IntArrayToString(Array:[]int)<transacts>:string=
var ConvertedToString:string = "["
for (Index -> Element : Array):
set ConvertedToString += "{Element}"
if (Index < Array.Length - 1):
set ConvertedToString += ", "
set ConvertedToString += "]"
# Función auxiliar para convertir los valores de comparación estadística del jugador en una cadena.
PlayerStatsWinsArrayToString(Array:[]player_stats)<transacts>:string=
var ConvertedToString:string = "["
for (Index -> Element : Array):
set ConvertedToString += "{Element.Wins}"
if (Index < Array.Length - 1):
set ConvertedToString += ", "
set ConvertedToString += "]"
# Función de comparación que se utilizará como argumento para ordenar enteros de menor a mayor.
IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
Left < Right
# Función de comparación que se utilizará como argumento para ordenar enteros de mayor a menor.
IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
Left > Right
# Una clase de ejemplo para probar la ordenación.
player_stats := class<unique>:
Wins:int = 0
RoundsPlayed:int = 0
# Función de comparación que se utilizará como argumento para ordenar victorias de menor a mayor.
IsWinsSmallerThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins < Right.Wins
Izquierda
# Función de comparación que se utilizará como argumento para ordenar victorias de mayor a menor.
IsWinsGreaterThan(Left:player_stats, Right:player_stats)<decides><transacts>:player_stats=
Left.Wins > Right.Wins
Izquierda
Por tu cuenta
-
Implementa un algoritmo de ordenación diferente. Puedes encontrar las siguientes otras implementaciones de algoritmos:
-
Añade más casos de prueba para aumentar la cobertura de las pruebas. ¿Se te ocurren casos extremos que las pruebas no cubren actualmente? ¿O tipos de datos más complejos?