El ordenamiento es un concepto simple pero poderoso. Si tomas una lista desordenada de elementos, puedes usar un algoritmo para ordenarlos de una forma específica. Si bien esta idea puede resultar básica, el ordenamiento está presente en toda la informática en muchos aspectos y formas diferentes. Una de sus aplicaciones más importantes es en la aceleración de la búsqueda. Por ejemplo, la computadora ordena archivos por nombre y tamaño para que puedas encontrar el que necesitas de forma rápida. Con UEFN puedes ordenar objetos por tipo en el esquematizador para agrupar cosas y organizar tu proyecto. En Fortnite, los jugadores del marcador en el juego se ordenan según distintas estadísticas, como las eliminaciones y el tiempo de vuelta, para que todos sepan quién es el mejor.
Aplicar el ordenamiento en el código de Verse te puede ayudar a elevar tu nivel de juego y a mejorar aspectos de tu desarrollo. Por ejemplo, ¿qué pasa si ordenas una matriz de jugadores de acuerdo con su puntuación en un torneo, donde queden eliminados los que tuvieron la menor cantidad de puntos en cada ronda? Al ordenar esta matriz al final de cada ronda, puedes encontrar con rapidez a los jugadores con las puntuaciones más bajas y establecerlos como espectadores. Por el otro lado, también puedes obtener rápidamente a los jugadores con la mejor puntuación y otorgarles una bonificación para la siguiente ronda. Incluso puedes usar esta lista ordenada para crear tablas de clasificación locales persistentes, para que los jugadores sepan a quién vigilar durante el juego. Y si tienes una lista de personas a las que te gustaría mencionar en tu isla, puedes ordenar sus nombres alfabéticamente para una fácil visualización.
Cada uno de estos ejemplos utiliza el ordenamiento de distintas maneras, pero en el fondo todos utilizan un algoritmo de ordenamiento para lograr su objetivo. Los algoritmos de ordenamiento implementan la lógica que ordena tus listas, y hay muchos tipos distintos entre los que puedes elegir según tus necesidades. Si bien el ordenamiento es una herramienta eficaz, es importante entender cómo funciona si deseas integrarlo en tus proyectos. Esta página abarca las ideas principales detrás del ordenamiento y cómo elegir el algoritmo que mejor funciona para tu proyecto. Para implementaciones de algoritmos de ordenamiento específicos, revisa el enlace al final de esta página.
Ordenamiento por mezcla
Ordenamiento por mezcla es un algoritmo de ordenamiento basado en el enfoque de "divide y vencerás". Esto significa que el algoritmo divide el grupo de elementos que se tienen que ordenar en grupos más pequeños, y ordena los grupos pequeños. Entonces combina los grupos más pequeños sabiendo que ya están ordenados.
Cómo implementar el ordenamiento por mezcla
La siguiente implementación se llama a sí misma para ordenar por mezcla las matrices divididas, lo cual significa que es una función recursiva. Cuando tienes una función recursiva, es necesario que especifiques un caso base para evitar la recursión infinita. Debido a que este algoritmo divide las matrices a la mitad cada vez, el caso base es la matriz que tiene un solo elemento, por lo tanto, la matriz se considera ordenada cuando tiene un solo elemento y se puede mezclar con otra matriz de un solo elemento y así sucesivamente hasta volver a la matriz completa de elementos.
La siguiente implementación es genérica mediante el uso de tipos paramétricos para sus parámetros. Esto significa que puedes usar el tipo que quieras para los elementos y tu propia función de comparación como argumentos. Así que puedes tener una matriz de enteros para ordenar o una matriz de un tipo más complejo, como una clase que puedes ordenar. La función Compare es otro parámetro al cual puedes pasar tus propias funciones personalizadas. Si quieres ordenar de menor a mayor, o según ciertos campos de una clase, puedes especificarlo en la función personalizada, sin modificar esta implementación genérica de funciones.
Sigue estos pasos para implementar el ordenamiento por mezcla en Verse:
-
Para empezar, escribiremos el caso base: un solo elemento en la matriz. Si hay un solo 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: Longitud > 1 # Verifica que haya más de un elemento en la matriz; de lo contrario, hemos alcanzado el caso base. else: # Devuelve la matriz que se pasó porque alcanzamos el caso base. Array -
Divide la matriz a la mitad.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Longitud > 1 # Verifica que haya más de un elemento en la matriz; de lo contrario, hemos alcanzado el caso base. Mid:int = Floor(Length / 2) # Obtiene el índice medio de la matriz. Left:[]t = Array.Slice[0, Mid] # Divide la matriz a la mitad. Esto mantiene los elementos del principio en índice medio - 1. Right:[]t = Array.Slice[Mid] # Divide la matriz a la mitad. Esto mantiene los elementos desde el índice medio hasta el final de la matriz. else: # Devuelve la matriz que se pasó porque alcanzamos el caso base. Array -
Llama a la función
MergeSorten cada mitad de la matriz inicial y, a continuación, fusiona conMergelas dos mitades entre sí.MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t= Length:int = Array.Length if: Longitud > 1 # Verifica que haya más de un elemento en la matriz; de lo contrario, hemos alcanzado el caso base. Mid:int = Floor(Length / 2) # Obtiene el índice medio de la matriz. Left:[]t = Array.Slice[0, Mid] # Divide la matriz a la mitad. Esto mantiene los elementos del principio en índice medio - 1. Right:[]t = Array.Slice[Mid] # Divide la matriz a la mitad. Esto mantiene los elementos desde el índice medio 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 que se pasó porque alcanzamos el caso base. Array -
Al mezclar las dos mitades entre sí, compara los elementos de cada matriz y los añade a la matriz resultante hasta que se hayan añadido todos los elementos de ambas matrices. Para hacer esto, haz que una variable de índice rastree las posiciones de cada matriz. Cada vez que la función
Compare(Comparar) se ejecuta correctamente, debe añadirse el elemento de la matriz izquierda y su variable de índice debe moverse a la siguiente posición en la matriz; de lo contrario, haz lo mismo con el elemento de la matriz derecha. Una vez que se añadieron todos los elementos de una de las matrices, añade los elementos restantes de la otra matriz que ya está ordenada.# Una función de ayuda para MergeSort que combina las matrices divididas en un orden de acuerdo con la función Comparar. 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{} # Itera a través de todos los elementos en las matrices para añadirlos a la variable MergedArray. loop: if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]): # Compara el elemento de la matriz de la mitad izquierda con el de la matriz de la mitad derecha. # Usa la función Compare que se pasa como argumento if (Compare[LeftElement, RightElement]): set MergedArray += array{LeftElement} set LeftIndex += 1 else: set MergedArray += array{RightElement} set RightIndex += 1 else: # A esta altura, ya añadimos todos los elementos de una de las matrices. # Ahora verifica qué matriz todavía tiene 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]} # Salir del bucle porque ya terminamos de añadir todos los elementos. break # Devuelve la matriz combinada. MergedArray
Secuencia de comandos completa
# Un algoritmo de ordenamiento del tipo "divide y vencerás" que divide una matriz en dos, ordena cada matriz dividida y luego mezcla las matrices entre sí.
# Se trata de una implementación recursiva, donde la función se llama a sí misma para ordenar por mezcla las matrices divididas.
# El caso base (la condición para detener la recursión) es que la matriz tenga un solo elemento.
# Se trata de una implementación genérica que utiliza tipos paramétricos, de modo que puedes proporcionar tu tipo y función de comparación propios como argumentos.
MergeSort<public>(Array:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:type)<transacts>:[]t=
Length:int = Array.Length
if:
Longitud > 1 # Verifica que haya más de un elemento en la matriz; de lo contrario, hemos alcanzado el caso base.
Mid:int = Floor(Length / 2) # Obtiene el índice medio de la matriz.
Left:[]t = Array.Slice[0, Mid] # Divide la matriz a la mitad. Esto mantiene los elementos del principio en índice medio - 1.
Right:[]t = Array.Slice[Mid] # Divide la matriz a la mitad. Esto mantiene los elementos desde el índice medio 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 que se pasó porque alcanzamos el caso base.
Array
# Una función de ayuda para MergeSort que combina las matrices divididas en un orden de acuerdo con la función Comparar.
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{}
# Itera a través de todos los elementos en las matrices para añadirlos a la variable MergedArray.
loop:
if (LeftElement := Left[LeftIndex], RightElement := Right[RightIndex]):
# Compara el elemento de la matriz de la mitad izquierda con el de la matriz de la mitad derecha.
# Usa la función Compare que se pasa como argumento
if (Compare[LeftElement, RightElement]):
set MergedArray += array{LeftElement}
set LeftIndex += 1
else:
set MergedArray += array{RightElement}
set RightIndex += 1
else:
# A esta altura, ya añadimos todos los elementos de una de las matrices.
# Ahora verifica qué matriz todavía tiene 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]}
# Salir del bucle porque ya terminamos de añadir todos los elementos.
break
# Devuelve la matriz combinada.
MergedArray
Cómo elegir un algoritmo
Si bien muchos algoritmos de ordenamiento siguen ideas similares, hay algunas cuestiones que los diferencian y que pueden tener un gran impacto en el modo en que funcionan.
Complejidad temporal
Los algoritmos toman tiempo, y cuanto más tienen que hacer, más tiempo requieren. Hay varios factores que influyen en la complejidad del problema que el algoritmo intenta resolver, y el tiempo que requiere para hacerlo se conoce como complejidad temporal.
Debido a que es casi imposible calcular el tiempo exacto que un algoritmo necesitará para completar la operación debido a varios factores, como el hardware de la computadora, otro código en ejecución o el tipo de datos con el que trabajas, la complejidad temporal, en cambio, se mide en operaciones o según la cantidad de acciones que tiene que llevar a cabo un algoritmo para terminar. Como cada algoritmo es diferente, el tiempo que lleva procesar un conjunto de datos se representa con la notación Big O. La notación Big O no describe la cantidad exacta de operaciones necesarias, sino cómo cambia esa cantidad a medida que aumenta el tamaño de la lista que introduces en el algoritmo.
Por ejemplo, supongamos que escribes un algoritmo para encontrar el número menor en una lista. No sabes si la lista está ordenada, así que el algoritmo tiene que comprobar cada número para saber si es el menor. Si hay tres elementos en la lista, el algoritmo hace tres comprobaciones, y si hay diez elementos, el algoritmo hace diez. Debido a que la cantidad de operaciones aumenta de forma lineal con el tamaño de la entrada de la lista, la complejidad temporal es lineal, u O(n), donde n es la cantidad de elementos de la lista. Si el algoritmo tuviera que hacer dos operaciones por elemento, como copiar cada elemento en una lista distinta después de cada comprobación, la complejidad temporal sería O(2n), ya que la cantidad de operaciones es 2 * NumberOfItems.
¿Y qué pasa si el algoritmo solo quería comprobar si había elementos en la lista? Debido a que el algoritmo solo hace una operación independientemente del tamaño de la entrada, la complejidad temporal debería ser constante u O(1). Hay muchos otros ejemplos, como el tiempo cuadrático (O(n^2)) o el factorial (O(n!)), pero lo importante es que cada uno describe cómo aumenta la cantidad de operaciones realizadas en función del tamaño de la entrada.
Complejidad en ordenamiento
La medición de la complejidad temporal de los algoritmos de ordenamiento se vuelve mucho más complicada debido a los distintos estados en que podría estar una lista antes del ordenamiento. ¿Qué pasa si ya está ordenada? ¿Qué pasa si está ordenada en orden descendente? El rendimiento de un algoritmo de ordenamiento podría variar de manera significativa según estos factores, de modo que los algoritmos de ordenamiento típicamente se miden según sus complejidades temporales en el mejor, peor y promedio de los casos.
Por ejemplo, observemos el algoritmo de ordenamiento por burbuja. En el mejor de los casos, dada una lista que ya está ordenada, el ordenamiento por burbuja solo tiene que comprobar cada par de elementos, pero no será necesario hacer ningún intercambio. Esto significa que la complejidad temporal en el mejor de los casos será O(n), lo cual es genial. Pero ¿qué pasa en la situación opuesta, donde la lista está ordenada en sentido contrario? En esta situación, el ordenamiento por burbuja tendrá que hacer n verificaciones e intercambiar n veces cada elemento de la lista, lo que significa que la complejidad temporal en el peor de los casos será n * n u O(n^2). Esto se considera lento en comparación con otros algoritmos de ordenamiento y puede salirse de control muy rápido, porque el algoritmo tendría que realizar cien operaciones como mínimo para procesar una lista de diez elementos. ¿Puedes imaginarte cuántas operaciones se requerirían para cien elementos? ¿Y si son mil?
El rendimiento de los algoritmos de ordenamiento tiende a estar más cerca del caso promedio, en lugar de los escenarios de mejor y peor caso. Por ejemplo, la complejidad del caso promedio del ordenamiento por mezcla es O(nlogn). Esto se considera una buena referencia, ya que muchos otros algoritmos de ordenamiento comunes tienen complejidades del mejor caso, peor caso y caso promedio a este nivel o muy cerca. El ordenamiento por burbuja anterior tiene una complejidad de caso promedio de O(n^2), así que incluso en el caso promedio, todavía es relativamente lento.
Conocer la complejidad temporal es importante cuando se elige un algoritmo, porque deseas que la ejecución del código sea rápida y su rendimiento sea similar, independientemente del tipo de entrada. Para ver algunos ejemplos de algoritmos de ordenamiento comunes eficaces, consulta Ordenamiento por mezcla y Ordenamiento rápido. Los dos algoritmos tienen las mismas complejidades de O(nlogn) en el mejor caso, peor caso y caso promedio y son un buen punto de partida para cualquier situación de ordenamiento.
Complejidad espacial
Además de la complejidad temporal, también es importante considerar todo lo que tiene que crear tu algoritmo para terminar el ordenamiento. Esto se conoce como complejidad espacial o la cantidad de datos adicionales creados al ejecutar el algoritmo. Al igual que la complejidad temporal, la complejidad espacial se mide con la notación Big_O, que varía entre algoritmos. Por ejemplo, debido a que el ordenamiento por mezcla divide una lista en n sublistas, tiene una complejidad espacial de O(n). Los algoritmos que ordenan objetos en su lugar (solo modifican los datos existentes en vez de crear nuevos) tienen una complejidad espacial de O(1). Si vas a trabajar con listas muy extensas, la complejidad espacial puede ser algo para tener en cuenta cuando selecciones el algoritmo.
Debido a que Verse es un lenguaje de programación funcional, las operaciones de API de estructura de datos devuelven versiones modificadas del elemento original que se pasa como entrada. Por ejemplo, las dos funciones de matriz Insert() y RemoveElement() no modifican la matriz original. En cambio, crean y devuelven una matriz nueva después de que se ejecuta la función. Esto puede aumentar los requisitos de complejidad temporal y espacial para tener en cuenta la creación de estos elementos nuevos.
Estabilidad
A menudo, al ordenar, el algoritmo va a encontrarse con empates. Por ejemplo, si tenemos dos jugadores, cada uno con una puntuación de cinco, ¿cómo debe ordenarlos el algoritmo? En este escenario, un algoritmo estable conservará el orden en que aparecen en la lista los elementos iguales después del ordenamiento. Por lo tanto, si el jugador uno estaba antes que el jugador dos en la lista antes de ordenar, la lista ordenada aún tendrá el jugador uno antes que el jugador dos.
Sin embargo, un algoritmo inestable no conservará este orden, lo que significa que el jugador dos puede aparecer antes que el jugador uno. Esto es importante si el código prioriza los primeros elementos de la lista, como si quisieras que los tres mejores jugadores por puntuación aparezcan en una tabla de clasificación. En esa situación, querrías contar con un algoritmo estable para asegurarte de que quien haya logrado esa puntuación primero permanezca en la tabla de clasificación.
Cómo probar los algoritmos y generar sus perfiles
Si bien es bueno saber cómo se espera que el algoritmo se ejecute dada las complejidades temporal y espacial, es incluso más importante medir cómo funciona verdaderamente en las entradas reales. Desarrollar algoritmos de ordenamiento puede ser una tarea complicada, así como puede ser difícil identificar si el código funciona de forma coherente para 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 existe regresión en el rendimiento si cambias la implementación de lo que estás probando. Sigue estos pasos para configurar un archivo de prueba para los algoritmos de ordenamiento y datos de salida sobre su rendimiento:
-
Crea una función falible con el nombre
RunArrayTest.# Prueba la función para ordenar las matrices y generar un perfil del código. RunArrayTest()<decides><transacts>:void= -
Añade el argumento para la matriz en la que deseas ejecutar el ordenamiento y la función de comparación que se usará.
# Prueba la función para ordenar las matrices y generar un perfil del código. RunArrayTest(ActualArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void= # Ejecución del ordenamiento por mezcla ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) -
Ahora tendrás que comparar la matriz ordenada con los resultados esperados. Añade el argumento de la matriz esperada para compararla con la matriz real ordenada y verificar que el resultado sea correcto.
Compara los elementos de
ResultArraycon los deExpectedArray. La funciónRunArrayTestes falible, así que tan pronto como un elemento no coincida, la función de prueba falla.# Prueba la función para ordenar las matrices y generar un perfil del código. RunArrayTest(ActualArray:[]t, ExpectedArray:[]t, Compare(L:t, R:t)<decides><transacts>:t where t:subtype(comparable))<decides><transacts>:void= # Ejecución del ordenamiento por mezcla ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # Verifica que la prueba haya pasado y ordenado la matriz según lo esperado. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected -
Añade una función de argumento para mostrar en pantalla las matrices en cada paso, para que puedas compararlas si falla la prueba y comprender cómo corregir el código que estás probando.
# Prueba la función para ordenar las matrices y generar un perfil del 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= # Ejecución del ordenamiento por mezcla ResultArray := SortingAlgorithms.MergeSort(ActualArray, Compare) # Muestra en pantalla las matrices real, esperada y de resultado para resolver errores. ProjectLog("Actual: {ArrayToString(ActualArray)}") ProjectLog("Expected: {ArrayToString(ExpectedArray)}") ProjectLog("Result: {ArrayToString(ResultArray)}") # Verifica que la prueba haya pasado y ordenado la matriz según lo esperado. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected -
La función de prueba comprueba la precisión del resultado, pero también puedes obtener más información de dicha prueba. Al utilizar la expresión del perfil, puedes medir el rendimiento de los algoritmos si registras el tiempo que tardan para completar la tarea.
Esto es útil si deseas comparar el rendimiento de distintos algoritmos de ordenamiento o probar cómo se ejecutan, dadas las diferentes entradas. Los algoritmos individuales pueden tener un rendimiento muy distinto según las entradas en el mejor y peor de los casos, y la generación de perfiles te permite encontrar y probar esos casos para saber en qué debes fijarte. Por medio de varias pruebas, puedes medir el rendimiento promedio del algoritmo y estimar cómo funcionará en las entradas de un tamaño determinado.
-
Añade un argumento de cadena denominado
Descriptionque explique en qué se enfoca la prueba. Puedes añadirlo a la expresiónprofilepara registrar la descripción con el valor cronometrado.# Prueba la función para ordenar las matrices y generar un perfil del 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 el ordenamiento por mezcla y genera un perfil del código. ResultArray := profile(Description): SortingAlgorithms.MergeSort(ActualArray, Compare) # Muestra en pantalla las matrices real, esperada y de resultado para resolver errores. ProjectLog("Actual: {ArrayToString(ActualArray)}") ProjectLog("Expected: {ArrayToString(ExpectedArray)}") ProjectLog("Result: {ArrayToString(ResultArray)}") # Verifica que la prueba haya pasado y ordenado la matriz según lo esperado. for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]): Result = Expected
Cómo escribir casos de prueba
Empieza de forma simple. Aísla lo que vas a someter a prueba. Prueba una matriz de enteros para ordenar los valores de menor a mayor.
-
Crea una función de comparación para enteros.
# Función de comparación que se usará como argumento para ordenar los 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 a una cadena.
# Función auxiliar para convertir una matriz de enteros a 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 de Verse para ejecutar la prueba.
# Este archivo contiene pruebas para verificar que el algoritmo de ordenamiento se comporta según lo esperado. # Las pruebas también incluyen la generación del perfil 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 proyectos para imprimir mensajes de las funciones que no están en una clase con un registro. # La impresión que no es registrador es <no_rollback>, así que no se puede usar en una función <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 por Verse que se puede colocar en un nivel. # Coloca en el nivel para ejecutar pruebas y generar el perfil del código. test_sorting := class(creative_device): # Se ejecuta cuando el dispositivo se inicia en un juego en ejecución OnBegin<override>()<suspends>:void= # Matrices de ejemplo para usar en la prueba. Test1ExpectedIntArray:[]int = array{} Test1ActualIntArray:[]int = array{} # Ejecuta las pruebas y notifica si generaron errores o se completaron correctamente. if: RunArrayTest["Matriz de números enteros ordenados de menor a mayor", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString] then: ProjectLog("Se han superado todas las pruebas.") else: ProjectLog("No se han superado una o varias pruebas.") -
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) -
Para ejecutar la prueba, arrastra el dispositivo de Verse hacia tu nivel
A continuación te damos más ideas de pruebas que puedes ejecutar:
* Ordena una matriz de enteros de mayor a menor.
# Función de comparación que se usa como argumento para ordenar los enteros de mayor a menor.
IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
Left > Right
* Ordena una matriz de enteros que tiene valores repetidos.
Test3ExpectedIntArray:[]int = array{0, 1, 1, 2, 3, 3}
Test3ActualIntArray:[]int = Shuffle(Test3ExpectedIntArray)
* Ordena una clase por uno de sus campos.
# Clase de ejemplo para probar el ordenamiento.
player_stats := class<unique>:
Wins:int = 0
RoundsPlayed:int = 0
# Función de comparación que se usa como argumento para ordenar las 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 de estadísticas del jugador a 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 += ", "
Secuencia de comandos completa
# Este archivo contiene pruebas para verificar que el algoritmo de ordenamiento se comporta según lo esperado.
# Las pruebas también incluyen la generación del perfil 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 proyectos para imprimir mensajes de las funciones que no están en una clase con un registro.
# La impresión que no es registrador es <no_rollback>, así que no se puede usar en una función <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 por Verse que se puede colocar en un nivel.
# Coloca en el nivel para ejecutar pruebas y generar el perfil del código.
test_sorting := class(creative_device):
# Se ejecuta cuando el dispositivo se inicia en un juego en ejecución
OnBegin<override>()<suspends>:void=
# Matrices de ejemplo para usar en 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 generaron errores o se completaron correctamente.
if:
RunArrayTest["Matriz de números enteros ordenados de menor a mayor", Test1ActualIntArray, Test1ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
RunArrayTest["Matriz de números enteros ordenados de mayor a menor", Test2ActualIntArray, Test2ExpectedIntArray, IsIntGreaterThan, IntArrayToString]
RunArrayTest["Matriz de números enteros ordenados de menor a mayor con repeticiones", Test3ActualIntArray, Test3ExpectedIntArray, IsIntSmallerThan, IntArrayToString]
RunArrayTest["Matriz de estadísticas de jugadores ordenadas de mayor a menor por número de victorias", Test4ActualPlayerStats, Test4ExpectedPlayerStats, IsWinsGreaterThan, PlayerStatsWinsArrayToString]
then:
ProjectLog("Se han superado todas las pruebas.")
else:
ProjectLog("No se han superado una o varias pruebas.")
# Prueba la función para ordenar las matrices y generar un perfil del 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 el ordenamiento por mezcla y genera un perfil del código.
ResultArray := profile(Description):
SortingAlgorithms.MergeSort(ActualArray, Compare)
# Muestra en pantalla las matrices real, esperada y de resultado para resolver errores.
ProjectLog("Actual: {ArrayToString(ActualArray)}")
ProjectLog("Expected: {ArrayToString(ExpectedArray)}")
ProjectLog("Result: {ArrayToString(ResultArray)}")
# Verifica que la prueba haya pasado y ordenado la matriz según lo esperado.
for (Index -> Result : ResultArray, Expected := ExpectedArray[Index]):
Result = Expected
# Función auxiliar para convertir una matriz de enteros a 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 de estadísticas del jugador a 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 usará como argumento para ordenar los enteros de menor a mayor.
IsIntSmallerThan(Left:int, Right:int)<decides><transacts>:int=
Left < Right
# Función de comparación que se usa como argumento para ordenar los enteros de mayor a menor.
IsIntGreaterThan(Left:int, Right:int)<decides><transacts>:int=
Left > Right
# Clase de ejemplo para probar el ordenamiento.
player_stats := class<unique>:
Wins:int = 0
RoundsPlayed:int = 0
# Función de comparación que se usa como argumento para ordenar las 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 usa como argumento para ordenar las 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 ordenamiento distinto. Puedes encontrar las siguientes implementaciones de otros algoritmos:
-
Añade más casos de prueba para aumentar la cobertura del probador. ¿Se te ocurren casos extremos que el probador no cubra actualmente? ¿O tipos de datos más complejos?