Algoritmos de ordenamiento
Los algoritmos de ordenamiento nos permite reorganizar información de una manera especial basándonos en un criterio de ordenamiento.
- Es mucho mas eficiente trabajar con datos cuando la información esta ordenada.
- Reduce significativamente la complejidad de los problemas y es una técnica que reduce la complejidad de búsqueda.
Podemos ordenar cualquier dato que sea comparable, por ejemplo:
- Números
- Meses
- Nombres
Es decir como podemos libros, alumnos, ciudades, etc. Podemos ordenar cualquier cosa que tenga algún identificador o dato que sea comparable.
Es un algoritmo de ordenamiento que requiere O (n2) operaciones para ordenar una lista de N elementos.
Su funcionamiento es el siguiente:
- Buscar el mínimo elemento de la lista
- Intercambiarlo con el primero
- Buscar el siguiente mínimo en el resto de la lista
- Intercambiarlo con el segundo
Y en general:
- Buscar el mínimo elemento entre una posición i y el final de la lista
- Intercambiar el mínimo con el elemento de la posición i
fun <T:Comparable<T>>selectionsort(items:MutableList<T>):MutableList<T>{
if (items.isEmpty()){
return items
}
for (idx in 0..items.count()){
val array = items.subList(0,items.count()-idx)
val minItem = array.min()
val indexOfMinItem = array.indexOf(minItem)
if (minItem != null) {
items.removeAt(indexOfMinItem)
items.add(minItem)
}
}
return items
}Complejidad computacional:
- Mejor caso : Ω (n2)
- Promedio : O (n2)
- Peor de los casos : O (n2)
Es importante recordar que la notación, ya sea O, Ω o Θ, expresa el crecimiento asintótico de una función, no tiene nada que ver intrínsecamente con los algoritmos en sí mismo. Puedes encontrar mas información aquí
Es un algoritmo de clasificación eficiente O (N log N) , que sirve como un método sistemático para colocar los elementos de una matriz en orden.
La eficiencia algorítmica es una propiedad de un algoritmo que se relaciona con la cantidad de recursos computacionales utilizados por el algoritmo.
Los recursos computacionales más simples son el tiempo de cálculo , la cantidad de pasos necesarios para resolver un problema y el espacio de memoria.
Su funcionamiento es el siguiente:
- Elegir un elemento del arreglo de elementos a ordenar, al que llamaremos pivote.
- Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
- La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
- Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.
fun <T:Comparable<T>>quicksort(items:List<T>):List<T>{
if (items.count() < 2){
return items
}
val pivot = items[items.count()/2]
val equal = items.filter { it == pivot }
val less = items.filter { it < pivot }
val greater = items.filter { it > pivot }
val quick = quicksort(less) + equal + quicksort(greater)
return quick
}Complejidad computacional:
- Mejor caso : Ω(n log(n))
- Promedio : Θ(n log(n))
- Peor de los casos : O(n^2)
Es un algoritmo de clasificación simple que construye la matriz final ordenada (o lista) un elemento a la vez. Es mucho menos eficiente en listas grandes que los algoritmos más avanzados como Quicksort.
Su funcionamiento es el siguiente:
Este metodo funciona de la siguiente manera, toma cada elemento del arreglo y lo compara con elementos que se encuentran en posiciones anteriores. Si resulta que el elemento con el que se está comparando es mayor que el elemento a ordenar, estos se intercambian de posición. Si por el contrario, resulta que el elemento con el que se está comparando es menor que el elemento a ordenar, se detiene el proceso de comparación pues, se encontró que el elemento ya está ordenado y se coloca en su posición.
fun <T:Comparable<T>> insertionsort(items:MutableList<T>):List<T>{
if (items.isEmpty()){
return items
}
for (count in 1..items.count() - 1){
val item = items[count]
var i = count
while (i>0 && item < items[i - 1]){
items[i] = items[i - 1]
i -= 1
}
items[i] = item
}
return items
}Complejidad computacional:
- Mejor caso : Ω(n)
- Promedio : Θ(n^2)
- Peor de los casos : O(n^2)