Si te dieran un trozo de papel con un lista de 1000 nombres, y quisieras buscar uno en concreto pero dicha lista no viniese ordenada por nada en particular (por ejemplo, orden alfabético), sería muy frustrante, ¿verdad? Ordenar esa lista, a pesar de que nos puede llevar mucho tiempo, hace que el encontrar dicho nombre sea más sencillo. Por lo tanto, tener las cosas en orden es un deseo natural que todos los seres humanos tenemos, y buscar en esa lista requiere menos esfuerzo que, claramente, buscar en una lista desordenada.
Entrando en términos informáticos, las listas donde nos vemos obligados a buscar suelen ser gigantescas, y esto puede afectar al rendimiento incluso en ordenadores rápidos. En este caso, contar con una ordenación adecuada y un buen algoritmo de búsqueda sería la solución óptima al problema. Mientras que la ordenación trata sobre poner una lista de valores en orden, la búsqueda es el proceso de encontrar la posición de un valor dentro de una lista.
Para que quede claro lo importante que puede ser este problema, déjame mostrarte lo que Donald Knuth, un científico de computación, matemático y profesor emérito de la Universidad de Stanford menciona en The Art of Computer Programming, vol.3, Sorting and Searching, página 3:
Los fabricantes de ordenadores de la década de los 60 estiman que más del 25 por ciento del tiempo de ejecución de sus ordenadores se dedicaron a la ordenación, según una encuesta a sus propios clientes. De hecho, había muchas instalaciones en las que la tarea de ordenar era responsable de más de la mitad del tiempo de computación. A partir de estas estadísticas, podemos concluir que, o bien hay muchas aplicaciones importantes de ordenación, o muchas personas ordenan cuando no deben, o los algoritmos de ordenación ineficientes han sido de uso común.
En este tutorial, voy a describir específicamente el algoritmo de ordenación por selección (ordenación) y el algoritmo de búsqueda lineal (búsqueda).
Algoritmo de Ordenación por Seleccion (Selection Sort)
El algoritmo de ordenación por selección se basa en la selección sucesiva de los valores mínimos o máximos. Supongamos que tenemos una lista que queremos ordenar en orden ascendente (de menor a mayor). El elemento más pequeño será el primero de la lista, y el elemento más grande será el último de la lista.
Digamos que la lista original es de la siguiente manera:
| 7 | 5 | 3.5 | 4 | 3.1 |
Lo primero que hacemos es encontrar el valor mínimo de la lista, que en nuestro caso es el 3.1.
Después de encontrar el valor mínimo, movemos dicho valor al primer elemento en la lista. Es decir, intercambiamos 3.1 por 7. La lista ahora se verá de la siguiente manera:
| 3.1 | 5 | 3.5 | 4 | 7 |
Ahora que estamos seguros de que el primer elemento está en la posición correcta de la lista, repetimos el paso anterior (encontramos el valor mínimo) a partir del segundo elemento de la lista. Vemos que el siguiente valor mínimo de la lista (a partir del segundo elemento) es el 3,5. por lo tanto, ahora cambiamos el 3,5 por el 5. La lista ahora se vería de la siguiente manera:
| 3.1 | 3.5 | 5 | 4 | 7 |
En este punto, estamos seguros de que el primer elemento y el segundo elemento están en sus posiciones correctas.
Ahora, comprobamos el valor mínimo del resto de la lista, que empieza a partir del tercer elemento, el 5. El valor mínimo del resto de la lista es el 4, y lo intercambiamos por el 5. Por tanto, la lista se quedaría de la siguiente manera:
| 3.1 | 3.5 | 4 | 5 | 7 |
Así que ahora estamos seguros de que los tres primeros elementos se encuentran en las posiciones correctas. Para los demás elemento se repetiría el proceso anterior.
Vamos a ver cómo el algoritmo de ordenación por selección es implementado en Python (basado en Isai Damier):
def selectionSort(aList):
for i in range(len(aList)):
least = i
for k in range(i+1, len(aList)):
if aList[k] < aList[least]:
least = k
swap(aList, least, i)
def swap(A, x, y):
temp = A[x]
A[x] = A[y]
A[y] = temp
Vamos a probar el algoritmo mediante la inserción de las siguientes declaraciones del script:
my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5] selectionSort(my_list) print my_list
En este caso, debes obtener el siguiente resultado:
[4.6, 4.7, 5.76, 7.3, 7.6, 25.3, 32.4, 43.5, 52.3, 55.3, 86.7]
Algoritmo de Búsqueda Lineal (Linear Search)
El algoritmo de búsqueda lineal es un algoritmo simple, donde cada elemento de la lista (empezando por el primer elemento) es investigado hasta que es encontrado el elemento requerido, o se ha alcanzado el final de la lista.
El algoritmo de búsqueda lineal es implementado en Python de la siguiente manera (en base a la Python School):
def linearSearch(item,my_list):
found = False
position = 0
while position < len(my_list) and not found:
if my_list[position] == item:
found = True
position = position + 1
return found
Vamos a probar el código. Introduce la sentencia al final del script de Python de arriba:
bag = ['book','pencil','pen','note book','sharpener','rubber']
item = input('What item do you want to check for in the bag?')
itemFound = linearSearch(item,bag)
if itemFound:
print 'Yes, the item is in the bag'
else:
print 'Oops, your item seems not to be in the bag'
Cuando se introduzcas el input, asegúrate de que está entre comillas simples o dobles (es decir 'pencil'). Si ingresa 'pencil', por ejemplo, debes obtener el siguiente resultado:
Yes, the item is in the bag
Fuente: code.tutsplus.com