Share
Si le dieran un pedazo de papel con una lista de 1,000 nombres y le pidieran que buscara algún nombre, pero esta lista no estaba en ningún orden (por ejemplo, orden alfabético), sería muy frustrante, ¿no es así? Poner esa lista en orden, aunque lleva mucho tiempo, hace que sea más fácil encontrar el nombre. Por lo tanto, tener las cosas en orden es un deseo natural que tenemos los seres humanos, y buscar esta lista claramente tomaría menos esfuerzo que buscar una lista desordenada.
Vayamos al mundo de las computadoras, donde las listas que se requieren para buscar son muy grandes y donde el rendimiento puede verse afectado incluso con las computadoras rápidas. En este caso, tener un adecuado clasificación y búsqueda El algoritmo sería una solución a tal problema. Mientras clasificación Se trata de poner una lista de valores en orden., buscando es el proceso de encontrar la posición de un valor dentro de una lista.
Para dejar en claro cuán crítico puede ser este problema, permítame mostrarle lo que Donald Knuth, un científico informático, matemático y profesor emérito estadounidense de la Universidad de Stanford mencionó en The Art of Computer Programming, vol.3, Clasificación y búsqueda, página 3:
Los fabricantes de computadoras de la década de 1960 estimaron que más del 25 por ciento del tiempo de ejecución en sus computadoras se gastaba en la clasificación, cuando se tenía en cuenta a todos sus clientes. De hecho, hubo muchas instalaciones en las que la tarea de clasificación fue responsable de más de la mitad del tiempo de computación. De estas estadísticas, podemos concluir que (i) hay muchas aplicaciones importantes de clasificación, o (ii) muchas personas clasifican cuando no deberían, o (iii) algoritmos de clasificación ineficientes han sido de uso común.
En este tutorial, describiré específicamente la Selección de selección algoritmo (ordenamiento) y el Busqueda lineal algoritmo (búsqueda).
los Selección de selección El algoritmo se basa en la selección sucesiva de valores mínimos o máximos. Supongamos que tenemos una lista que queremos clasificar en orden ascendente (de valores más pequeños a valores más grandes). El elemento más pequeño estará al principio de la lista, y el elemento más grande estará al final de la lista.
Digamos que la lista original tiene el siguiente aspecto:
| 7 | 5 | 3.5 | 4 | 3.1 |
Lo primero que hacemos es encontrar el mínimo Valor en la lista, que es en nuestro caso. 3.1.
Después de encontrar el valor mínimo., intercambiar Ese valor mínimo con el primer elemento de la lista. Es decir, swap 3.1 con 7. La lista ahora se verá como sigue:
| 3.1 | 5 | 3.5 | 4 | 7 |
Ahora que estamos seguros de que el primer elemento está en la posición correcta en la lista, repetimos el paso anterior (encontrar el valor mínimo) comenzando desde segundo Elemento en la lista. Podemos encontrar que el valor mínimo en la lista (a partir del segundo elemento) es 3.5. Así que ahora intercambiamos 3.5 con 5. La lista ahora se convierte en la siguiente:
| 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, verificamos el valor mínimo en el resto de la lista, que está comenzando desde el tercer elemento 5. El valor mínimo en el resto de la lista es 4, y ahora lo cambiamos con 5. La lista se convierte así en lo siguiente:
| 3.1 | 3.5 | 4 | 5 | 7 |
Así que ahora estamos seguros de que la primera Tres Los elementos están en las posiciones correctas, y el proceso continúa de esa manera..
Veamos cómo se implementa el algoritmo de selección de selección en Python (basado en Isai Damier):
def selectionSort (aList): para i en rango (len (aList)): menos = i para k en rango (i + 1, len (aList)): si 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
Probemos el algoritmo agregando las siguientes declaraciones al final del script anterior:
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) imprimir my_list
En este caso, debería 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]
los Búsqueda lineal algorithm es un algoritmo simple, donde se investiga cada elemento de la lista (comenzando desde el primer elemento) hasta que se encuentra el elemento requerido o se llega al final de la lista.
El algoritmo de búsqueda lineal se implementa en Python de la siguiente manera (basado en 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
Probemos el código. Ingrese la siguiente declaración al final de la secuencia de comandos de Python anterior:
Accentsconagua
bag = ['book', 'pencil', 'pen', 'note book', 'sacapuntas', 'rubber'] item = input ('¿Qué item desea buscar en la bolsa?') itemFound = linearSearch (artículo, bolsa) si artículo Encontrado: imprimir 'Sí, el artículo está en la bolsa' otra cosa: imprimir 'Vaya, su artículo no parece estar en la bolsa'Cuando entras en el entrada, asegúrese de que esté entre comillas simples o dobles (es decir,. 'lápiz'). Si usted ingresa 'lápiz', por ejemplo, debería obtener el siguiente resultado:
Sí, el artículo está en la bolsa.
Considerando que, si entras 'regla' Como entrada, obtendrás la siguiente salida:
Vaya, parece que tu objeto no está en la bolsa.
Como podemos ver, Python demuestra de nuevo que es un lenguaje de programación que facilita la programación de conceptos algorítmicos como lo hicimos aquí, al tratar con clasificación y buscando algoritmos.
Es importante tener en cuenta que existen otros tipos de algoritmos de clasificación y búsqueda. Si desea profundizar en tales algoritmos utilizando Python, puede consultar esta página.
