Busqueda y Ordenacion Con Python

Búsqueda y
ordenación
Matías Bordone - 2020
CC-By international 4.0
La búsqueda
Ejemplo
l = [a,b,c,d,e,f,g] -> existe “el siguiente de”
preguntar si x esta en l
para cada e en l:
pregunto x == e:
return true
return false
La búsqueda secuencial
Testear el código con diferentes
def busquedaSecuencial(unaLista, item): valores hasta que entiendan como
if unaLista==[]: funciona.
return False
http://pythontutor.com/visualize.html
else: #mode=edit
return ((unaLista[0] == item) or
busquedaSecuencial(unaLista[1:],item))
listaPrueba = [1, 2, 32, 8, 17, 19, 42, 13, 0]

print(busquedaSecuencial(listaPrueba, 3))
La búsqueda secuencial
def busquedaSecuencial(unaLista, item):
pos = 0
encontrado = False
while pos < len(unaLista) and not encontrado:
if unaLista[pos] == item:
encontrado = True
else:
pos = pos+1
return encontrado
listaPrueba = [1, 2, 32, 8, 17, 19, 42, 13, 0]

Tiempo en búsqueda Secuencial
En una entrada reciente en el Blog Oficial de Google, ingenieros del buscador explican con
orgullo que Google alcanzó por primer vez un billón de URLs únicas indexadas (¿cuántos
ceros son eso? Un billón = 1,000,000,000,000).
Cuánto demoramos encontrar una página?

3.6ghz - > 3.6*1000*1000*1000 -> 3600000000 operaciones por segundo
1,000,000,000,000/ 360,0000,000 = 277.777777778 segundos
4 minutos y medio para ver si la página está

La búsqueda secuencial ordenada
La búsqueda binaria
buscar una palabra en el diccionario.[0..n] = l
tomo n/2 y veo si es ese el elemento.
0) l[] -> False

1) l[n/2] == e -> True
2) l[n/2] < e -> repito sobre l[n/2..n]
3) l[n/2] > e -> repito sobre l[0..n/2]
def busquedaBinaria(unaLista, item):
primero = 0
ultimo = len(unaLista)-1 La búsqueda
encontrado = False
while primero<=ultimo and not encontrado: binaria

puntoMedio = (primero + ultimo)//2
if unaLista[puntoMedio] == item:
encontrado = True
else:
Testear el código con diferentes
if item < unaLista[puntoMedio]:
valores hasta que entiendan como
ultimo = puntoMedio-1
funciona.
else:
primero = puntoMedio+1
http://pythontutor.com/visualize.ht
ml#mode=edit
return encontrado
listaPrueba = [0, 1, 2, 8, 13, 17, 19, 32, 42,]

print(busquedaBinaria(listaPrueba, 3))
print(busquedaBinaria(listaPrueba, 13))
Tarea: Escribir busqueda binaria
Recursiva
La búsqueda binaria
El número de comparaciones
necesarias para llegar a este punto
es i donde
n((2^i)=1
La solución para i nos da
i=log(n)
El número máximo de
comparaciones es logarítmico con
respecto al número de ítems de la
lista. Por lo tanto, la búsqueda
binaria es
O(log(n))
.
Binaria vs Secuencial
En una entrada reciente en el Blog Oficial de Google, ingenieros del buscador explican con orgullo que
Google alcanzó por primer vez un billón de URLs únicas indexadas (¿cuántos ceros son eso? Un billón
= 1,000,000,000,000).
Cuanto demoramos encontrar una pagina?

3.6ghz - > 3.6*1000*1000*1000 -> 3600000000 operaciones por segundo
1,000,000,000,000/ 360,0000,000 = 277.777777778 segundos ~ 4.5m log(1,000,000,000,000)/

3600,000,000 = 0,000000011 segundos
¿Mucha diferencia no?

Qué es ordenar
Cómo ordenaría esto?
[26,54,93,17,77,31,44,55, 20]
Ordenamiento por selección
Agarro el más grande lo pongo en último lugar
Agarro el 2° más grande y lo pongo en el penúltimo lugar
Agarro el 3° y lo pongo en el último - 3° lugar
...
def ordenamientoPorSeleccion(lista):
for i_ultimo in range(len(lista)-1,0,-1):
i_mayor=0
for i in range(1,i_ultimo+1):
if lista[i]>lista[i_mayor]:
i_mayor = i
temp = lista[i_ultimo]
lista[i_ultimo] = lista[i_mayor]
lista[i_mayor] = temp
lista = [5,1,8]
ordenamientoPorSeleccion(lista)
print(lista)
Ordenamiento
por inserción
Ordenamiento por inserción
agarro el 1° y lo pongo en su lugar en la sublista de la izquierda

Ordenamiento por inserción
def ordenamientoPorInsercion(unaLista):
for indice in range(1,len(unaLista)):
valorActual = unaLista[indice]
posicion = indice
while posicion>0 and unaLista[posicion-1]>valorActual:

unaLista[posicion]=unaLista[posicion-1]
posicion = posicion-1
unaLista[posicion]=valorActual
unaLista = [54,26,93,17,77,31,44,55,20]
ordenamientoPorInsercion(unaLista)
print(unaLista)
Insertar por recursion
Recursión sobre listas: Inserción ordenada
● (inserta e xs) inserta el elemento e en la lista xs delante del primer elemento de xs

mayor o igual que e. Por ejemplo,
#inserta 5 [2,4,7,3,6,8,10] == [2,4,5,7,3,6,8,10]

inserta :: Ord a => a -> [a] -> [a]
inserta e [] = [e]
inserta e (x:xs) | e <= x = e : (x:xs)
| otherwise = x : inserta e xs
Isort
Recursión sobre listas: Ordenación por inserción
● (ordena_por_insercion xs) es la lista xs ordenada mediante inserción, Por ejemplo,
#ordena_por_insercion [2,4,3,6,3] == [2,3,3,4,6]

ordena_por_insercion :: Ord a => [a] -> [a]
ordena_por_insercion [] = []
ordena_por_insercion (x:xs) =
inserta x (ordena_por_insercion xs)
Quicksort - U ordenamiento rápido
Recursión múltiple: Ordenación rápida
● Algoritmo de ordenación rápida:
ordena :: (Ord a) => [a] -> [a]

ordena [] = []
ordena (x:xs) =
(ordena menores) ++ [x] ++ (ordena mayores)
where menores = [a | a <- xs, a <= x]
mayores = [b | b <- xs, b > x]
Quicksort
Quicksort
Quicksort
def ordenamientoRapido(unaLista):
ordenamientoRapidoAuxiliar(unaLista,0,len(unaLista)-1)
def ordenamientoRapidoAuxiliar(unaLista,primero,ultimo):
if primero<ultimo:
puntoDivision = particion(unaLista,primero,ultimo)
ordenamientoRapidoAuxiliar(unaLista,primero,puntoDivision-1)
ordenamientoRapidoAuxiliar(unaLista,puntoDivision+1,ultimo)
def particion(unaLista,primero,ultimo):
valorPivote = unaLista[primero]
marcaIzq = primero+1
marcaDer = ultimo
hecho = False
while not hecho:
while marcaIzq <= marcaDer and unaLista[marcaIzq] <= valorPivote:
marcaIzq = marcaIzq + 1
while unaLista[marcaDer] >= valorPivote and marcaDer >= marcaIzq:
marcaDer = marcaDer -1
if marcaDer < marcaIzq:
hecho = True
else:
temp = unaLista[marcaIzq]
unaLista[marcaIzq] = unaLista[marcaDer]
unaLista[marcaDer] = temp
temp = unaLista[primero]
unaLista[primero] = unaLista[marcaDer]
unaLista[marcaDer] = temp
return marcaDer
Velocidad del ordenamiento
ordenamiento por seleccion n^2 para 9 elementos hacemos 81 comparaciones
ordenamiento por insersion n^2 ->
quicksort n * log n - > 8.58818258495

Busqueda y Ordenacion Con Python

Cargado por

Copyright:

Formatos disponibles

Busqueda y Ordenacion Con Python

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Busqueda y Ordenacion Con Python

Cargado por

Copyright:

Formatos disponibles

Búsqueda y

listaPrueba = [1, 2, 32, 8, 17, 19, 42, 13, 0]

listaPrueba = [1, 2, 32, 8, 17, 19, 42, 13, 0]

Cuánto demoramos encontrar una página?

1,000,000,000,000/ 360,0000,000 = 277.777777778 segundos

4 minutos y medio para ver si la página está

0) l[] -> False

while primero<=ultimo and not encontrado: binaria

listaPrueba = [0, 1, 2, 8, 13, 17, 19, 32, 42,]

Cuanto demoramos encontrar una pagina?

1,000,000,000,000/ 360,0000,000 = 277.777777778 segundos ~ 4.5m log(1,000,000,000,000)/

¿Mucha diferencia no?

Agarro el 2° más grande y lo pongo en el penúltimo lugar

Agarro el 3° y lo pongo en el último - 3° lugar

agarro el 2° y lo pongo en su lugar en la sublista de la izquierda

agarro el 3° y lo pongo en su lugar en la sublista de la izquierda

while posicion>0 and unaLista[posicion-1]>valorActual:

● (inserta e xs) inserta el elemento e en la lista xs delante del primer elemento de xs

#inserta 5 [2,4,7,3,6,8,10] == [2,4,5,7,3,6,8,10]

● (ordena_por_insercion xs) es la lista xs ordenada mediante inserción, Por ejemplo,

#ordena_por_insercion [2,4,3,6,3] == [2,3,3,4,6]

● Algoritmo de ordenación rápida:

ordena :: (Ord a) => [a] -> [a]

ordenamiento por insersion n^2 ->

quicksort n * log n - > 8.58818258495

También podría gustarte