- Métodos de ordenación y búsqueda
- Métodos de ordenación
- Métodos de búsqueda
En este repositorio veremos diferentes métodos de ordenación y el tiempo que tardan en ordenar o buscar los datos dentro de un array. Su tamaño iniciara con 1.000 sigue con 5.000 en 5.000 hasta 100.000. Para asegurarnos que la prueba es lo más imparcial posible se ordenara el array 3 veces distintas con números aleatorios por cada tamaño del array.
Si quieres podrás revisar el código en este repositorio.
Los métodos de ordenación nos permite ordenar arrays. Pero ojo, debemos tener en cuenta que dependiendo del método de ordenación así será su eficiencia. Por lo que debemos tener en cuenta el tipo de datos que vamos a ordenar y el tamaño del array.
Puedes visualizarlos aquí
Es un método de ordenación con eficiencia O(n²). Es decir, el tiempo de ejecución es proporcional al cuadrado del tamaño del array. Este método consiste en ir comparando cada elemento con el siguiente, y si el elemento actual es mayor que el siguiente, se intercambian. Este proceso se repite hasta que no se producen más intercambios. Este método es muy sencillo de implementar, pero no es el más eficiente.
fun burbuja(array: IntArray) {
var aux: Int
for (i in 0 until array.size) {
for (j in 0 until array.size - 1) {
if (array[j] > array[j + 1]) {
aux = array[j]
array[j] = array[j + 1]
array[j + 1] = aux
}
}
}
}El método burbuja escala de forma exponencial pero más exagerado en comparación a otros métodos como veremos más adelante. Este metodo solo es viable cuando tengamos que ordenar pocos datos.
El algoritmo de la siguiente gráfica lo podrás encontrar en este archivo los datos dependen de la máquina que los procese por lo que tus datos serán distintos a los míos pero la forma de la gráfica sera muy similar.
Si quieres comprobar los resultados del algoritmo en mi máquina puedes encontrarlo en el siguiente pdf. La gráfica de la tabla la encontraras en esta hoja de calculo
El algoritmo de selección. su eficiencia es de O(n²). Consiste en ir buscando el elemento más pequeño del array y colocarlo en la primera posición, luego el segundo más pequeño y colocarlo en la segunda posición, y así sucesivamente. Este método es más eficiente que el método de la burbuja, ya que solo hace una comparación por cada iteración. En definitiva, en cada iteración, se selecciona el menor elemento del subvector no ordenado y se intercambia con el primer elemento de este subvector.
fun seleccion(array: IntArray) {
var aux: Int
var min: Int
for (i in 0 until array.size) {
min = i
for (j in i + 1 until array.size) {
if (array[j] < array[min]) {
min = j
}
}
aux = array[i]
array[i] = array[min]
array[min] = aux
}
}El método de selección al igual que el burbuja cuanto más tenga que ordenar el tiempo se incrementa de forma exponencial aunque de forma mucho más eficiente. Es más rápido que el metodo burbuja pero sigue siendo inviable con arrays de gran tamaño
El algoritmo de la siguiente gráfica lo podrás encontrar en este archivo los datos dependen de la máquina que los procese por lo que tus datos serán distintos a los míos pero la forma de la gráfica sera muy similar.
Si quieres comprobar los resultados del algoritmo en mi máquina puedes encontrarlo en el siguiente pdf. La gráfica de la tabla la encontraras en esta hoja de calculo
El algoritmo de inserción. Su eficiencia es O(n²). Es decir, el tiempo de ejecución es proporcional al cuadrado del tamaño del array. Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado. Después, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara con todos los elementos ya ordenados, deteniéndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazados una posición a la derecha) o cuando ya no se encuentran elementos (todos los elementos fueron desplazados y este es el más pequeño). En este punto se inserta el elemento k+1 debiendo desplazarse los demás elementos. En definitiva, nn cada iteración, se selecciona el menor elemento del subvector no ordenado y se intercambia con el primer elemento de este subvector.
fun insercion(array: IntArray) {
var aux: Int
var j: Int
for (i in 1 until array.size) {
aux = array[i]
j = i - 1
while (j >= 0 && array[j] > aux) {
array[j + 1] = array[j]
j--
}
array[j + 1] = aux
}
}El método de inserción al igual que el burbuja y el de selección cuanto más tenga que ordenar el tiempo se incrementa de forma exponencial aunque de forma un poco más eficiente que el metodo de selección. Es un poco más rápido que el metodo selección pero sigue siendo inviable con arrays de gran tamaño
El algoritmo de la siguiente gráfica lo podrás encontrar en este archivo los datos dependen de la máquina que los procese por lo que tus datos serán distintos a los míos pero la forma de la gráfica sera muy similar.
Si quieres comprobar los resultados del algoritmo en mi máquina puedes encontrarlo en el siguiente pdf. La gráfica de la tabla la encontraras en esta hoja de calculo
El algoritmo de Shell es una mejora del algoritmo de inserción. Su eficiencia es de O(n log n). Este método consiste en ordenar los elementos de un array de forma que los elementos que están lejos entre sí se ordenan primero. En lugar de comparar elementos adyacentes, se comparan elementos que están separados por un intervalo. Este intervalo se va reduciendo hasta que llega a 1. Este método es más eficiente que el método de inserción, ya que en cada iteración, se comparan elementos que están separados por un intervalo. En definitiva, en cada iteración, se selecciona el menor elemento del subvector no ordenado y se intercambia con el primer elemento de este subvector.
fun shell(array: IntArray) {
var aux: Int
var j: Int
var intervalo = 1
while (intervalo < array.size) {
intervalo = intervalo * 3 + 1
}
while (intervalo > 0) {
for (i in intervalo until array.size) {
aux = array[i]
j = i
while (j > intervalo - 1 && array[j - intervalo] >= aux) {
array[j] = array[j - intervalo]
j -= intervalo
}
array[j] = aux
}
intervalo = (intervalo - 1) / 3
}
}El método de shellSort es mucho más eficiente que los anteriores métodos y no escala de manera tan abrupta como el burbuja pero si sus valores son más dispares entre pruebas. Es muy eficiente a la hora de ordenar cuando el tamaño del array es grande.
El algoritmo de la siguiente gráfica lo podrás encontrar en este archivo los datos dependen de la máquina que los procese por lo que tus datos serán distintos a los míos pero la forma de la gráfica sera muy similar.
Si quieres comprobar los resultados del algoritmo en mi máquina puedes encontrarlo en el siguiente pdf. La gráfica de la tabla la encontraras en esta hoja de calculo
El algoritmo de quicksort es el algoritmo más rápido que veremos. Su eficiencia es de O(n log n). Consiste en dividir el array en dos partes, una con los elementos menores que el pivote y otra con los elementos mayores que el pivote. Luego se ordenan las dos partes de forma recursiva. Trabaja de la siguiente manera:
- Se toma un elemento arbitrario del vector, al que denominaremos pivote (p).
- Se divide el vector de tal forma que todos los elementos a la izquierda del pivote sean menores que él, mientras que los que quedan a la derecha son mayores que él.
- Ordenamos, por separado, las dos zonas delimitadas por el pivote.
- Es recursivo, de ahí su gran ventaja. Repetimos el proceso recursivamente conc ad aparte, hasta que al salir todas las llamadas tenemos el vector completo.
fun pivote(array: IntArray, izq: Int, der: Int): Int {
var i = izq
var j = der
var pivote = array[izq]
while (i < j) {
while (array[i] <= pivote && i < j) {
i++
}
while (array[j] > pivote) {
j--
}
if (i < j) {
val aux = array[i]
array[i] = array[j]
array[j] = aux
}
}
array[izq] = array[j]
array[j] = pivote
return j
}
fun quicksort(array: IntArray, izq: Int, der: Int) {
var piv: Int
if (izq < der) {
piv = pivote(array, izq, der)
quicksort(array, izq, piv - 1)
quicksort(array, piv + 1, der)
}
}El método de shellSort es mucho más eficiente que los anteriores métodos y no escala de manera tan abrupta como el burbuja pero si sus valores son más dispares entre pruebas. Es muy eficiente a la hora de ordenar cuando el tamaño del array es grande.
El algoritmo de la siguiente gráfica lo podrás encontrar en este archivo los datos dependen de la máquina que los procese por lo que tus datos serán distintos a los míos pero la forma de la gráfica sera muy similar.
Si quieres comprobar los resultados del algoritmo en mi máquina puedes encontrarlo en el siguiente pdf. La gráfica de la tabla la encontraras en esta hoja de calculo
El ranking de los algoritmos de búsqueda es el siguiente:
1º QuickSort
2º ShellSort
3º Inserción
4º Selección
5º Burbuja
Se puede ver claramente la diferencias entre los algoritmos aunque el quickSortResultados y el shellSort tienen valores muy cercanos la diferencia entre los distintos algoritmos es considerablemente grande cuanto más datos tenemos que ordenar
Los métodos de búsqueda nos servirán para encontrar un elemento en un array.
Puedes visualizarlos aquí
La búsqueda secuencial o lineal consiste en recorrer el vector hasta devolver el elemento buscado. Su eficiencia es de O(n). Es el método más sencillo de búsqueda, pero no es el más eficiente.
fun busquedaSecuencial(array: IntArray, elemento: Int): Int {
for (i in array.indices) {
if (array[i] == elemento) {
return i
}
}
return -1
}El método secuencial o lineal con tamaño pequeño es menos eficiente con un tamaño mayor. El tiempo que tarda en buscar el el carácter con el mismo tamaño no tiene valores similares entre las pruebas como sucedía con los de ordenación.
El algoritmo de la siguiente gráfica lo podrás encontrar en este archivo los datos dependen de la máquina que los procese por lo que tus datos serán distintos a los míos pero la forma de la gráfica sera muy similar.
Si quieres comprobar los resultados del algoritmo en mi máquina puedes encontrarlo en el siguiente pdf. La gráfica de la tabla la encontraras en esta hoja de calculo
En la búsqueda binaria partimos de un array ordenado. Su eficiencia es de O(n log n). Se compara el dato buscado con el elemento en el centro del vector:
- Si coinciden, hemos encontrado el dato buscado.
- Si el dato es mayor que el elemento central del vector, tenemos que buscar el dato en segunda mitad del vector (mejor recursivamente).
- Si el dato es menor que el elemento central del vector, tenemos que buscar el dato en la primera mitad del vector (mejor recursivamente).
// Versión Iterativa
fun busquedaBinariaIterativa(array: IntArray, elemento: Int): Int {
var centro: Int
var inf = 0
var sup = array.size - 1
while (inf <= sup) {
centro = (sup + inf) / 2
if (array[centro] == elemento) {
return centro
} else if (elemento < array[centro]) {
sup = centro - 1
} else {
inf = centro + 1
}
}
return -1
}
// Versión recursiva
fun busquedaBinariaRecursiva(array: IntArray, elemento: Int, inf: Int, sup: Int): Int {
if (inf > sup) {
return -1
}
val centro = (sup + inf) / 2
return if (array[centro] == elemento) {
centro
} else if (elemento < array[centro]) {
busquedaBinariaRecursiva(array, elemento, inf, centro - 1)
} else {
busquedaBinariaRecursiva(array, elemento, centro + 1, sup)
}
}El metodo de busqueda binaria iterativa y recursiva tardan lo mismo o muy parecido a el metodo lineal y entre ellos aun que con un tamaño pequeño en el array ha tardado en la primera prueba más que el metodo lineal los datos son similares.
El algoritmo de la siguiente gráfica lo podrás encontrar en este archivo los datos dependen de la máquina que los procese por lo que tus datos serán distintos a los míos pero la forma de la gráfica sera muy similar.
Si quieres comprobar los resultados del algoritmo en mi máquina puedes encontrarlo en el siguiente pdf. La gráfica de la tabla la encontraras en esta hoja de calculo
El algoritmo de la siguiente gráfica lo podrás encontrar en este archivo los datos dependen de la máquina que los procese por lo que tus datos serán distintos a los míos pero la forma de la gráfica sera muy similar.
Si quieres comprobar los resultados del algoritmo en mi máquina puedes encontrarlo en el siguiente pdf. La gráfica de la tabla la encontraras en esta hoja de calculo
Al calcular la media para saber que metodo de busqueda es más eficiente veremos que es el lineal con 66.469,65 ns seguido del binario iterativo con 88.361,35 ns y por último el metodo binario recursivo con 100.194,65. Esto es así porque el metodo binario con arrays pequeños tiene más picos puntuales que suben la media pero a partir del tamaño de 35000 ya todos tienen una media muy similar entre si.