<jupyter_start><jupyter_text>![Logo_unad](https://upload.wikimedia.org/wikipedia/commons/5/5f/Logo_unad.png)Escuela de Ciencias Básicas, Tecnología e IngenieríaECBTICurso:Introducción al lenguaje de programación PythonFebrero de 2020 Sesión 09 - Ordenamiento y Búsqueda  Docente: *<NAME>, I.C. Ph.D.*   Ordenamiento - **Ordenación o Clasificación de datos ($sort$, en inglés):** Operación consistente en disponer un conjunto —estructura— de datos en algún determinado orden con respecto a uno de los campos de elementos del conjunto.  - **Ejemplo:** cada elemento del conjunto de datos de una guía telefónica tiene un campo nombre, un campo dirección y un campo número de teléfono; la guía telefónica está dispuesta en orden alfabético de nombres; los elementos numéricos se pueden ordenar en orden creciente o decreciente de acuerdo al valor numérico del elemento. - En terminología de ordenación, el elemento por el cual está ordenado un conjunto de datos (o se está buscando) se denomina clave. - Una colección de datos (Estructura) puede ser almacenada en un archivo, un arreglo (lista, tupla, diccionario) u otra estructura especial.- Un arreglo se dice que está ordenado por la clave $k$ si está en orden ascendente o descendente con respecto a la clave.   - El arreglo se dice que está en orden ascendente si: $𝑖<𝑗$, esto implica que $𝑘_𝑖 \leq 𝑘_j$  - y se dice que está en orden descendente si:$𝑖>𝑗$, esto implica que $𝑘_𝑖 \geq 𝑘_j$   Algoritmos de Ordenamiento Existen muchos algoritmos de ordenamiento, cuál es el “mejor”? **Eficiencia:** factor que mide la calidad y rendimiento de un algoritmo. El más eficiente es el que:    - Resuelve en menor tiempo de ejecución en computador;    - Menor número de instrucciones.- A veces no se cuenta con un mecanismo que permita cuantificar la $eficiencia$.- El mejor criterio para medirla es aislar una operación específica clave en la ordenación.- Se empleará como medida de $eficiencia$ el número de comparaciones efectuada entre elementos.  - $A$ será más eficiente que $B$ si se requiere un menor número de comparaciones. - En el caso de ordenar elementos de un arreglo vectorial, el número de comparaciones será función del número de elementos, $n$, del arreglo: $n+4$, $n^2$, etc.- Los métodos de ordenación se suelen dividir en dos grandes grupos:  - **Directos:** `Burbuja, Selección, Inserción`.    - **Indirectos:** `Shell, Ordenación Rápida, Ordenación por Mezcla, Radixsort`.  Ordenamiento por intercambio - Basado en la lectura sucesiva de la lista a ordenar, comparando el elemento inferior de la lista con los restantes y efectuando el intercambio de posiciones cuando el orden de la comparación no sea el correcto.**Ejemplo:** Ordenar el arreglo $[8, 4, 6, 2]$ ![Ordena_Intercambio0.PNG](attachment:Ordena_Intercambio0.PNG) - El elemento de índice $0$ se compara con cada elemento posterior del arreglo de índices $1$, $2$ y $3$.- En cada comparación se comprueba si el elemento siguiente es menor que el del índice $0$, en este caso se intercambian.- Después de terminar todas las comparaciones, el elemento menor se localiza en el índice $0$. ![Ordena_Intercambio1.PNG](attachment:Ordena_Intercambio1.PNG) - El algoritmo continua comparando el elemento de índice $1$ con los elementos posteriores de índices $2$ y $3$. En cada comparación, si el elemento mayor está en el índice $1$ se intercambian los elementos.- Después de hacer todas las comparaciones, el segundo elemento de menor valor del arreglo se almacena en el índice $1$. ![Ordena_Intercambio2.PNG](attachment:Ordena_Intercambio2.PNG) La sublista a considerar es $8$, $6$. Una única comparación produce el arreglo ordenado. - El método utiliza dos bucles anidados.- Suponiendo que el arreglo es de tamaño $n$, el rango del ciclo externo irá desde el índice $0$ hasta $n-2$.- Por cada índice $i$, se comparan los elementos posteriores de índices $j=i+1, i+2, \ldots, n-1$. El intercambio ($swap$) de los elementos $a_i$, $a_j$ se realiza en un bloque:$$aux = a_i$$$$a_i = a_j$$$$a_j = aux$$  - Ordenamiento de Burbuja: ![Ordena_Burbuja.PNG](attachment:Ordena_Burbuja.PNG)<jupyter_code># Ordenamiento burbuja

miLista =[8,4,6,2]
print("lista desordenada: ", miLista)
n = len(miLista)

for i in range(1,n):
    for j in range(0,n-i):
        if miLista[j] > miLista[j+1]:
            aux = miLista[j]
            miLista[j] = miLista[j+1]
            miLista[j+1] = aux

print("lista ordenada: ", miLista)<jupyter_output>lista desordenada:  [8, 4, 6, 2]
lista ordenada:  [2, 4, 6, 8]<jupyter_text>Ordenamiento por Selección Los pasos del algoritmo son:1. Seleccionar el elemento de menor valor del arreglo, intercambiarlo con el primer elemento, $a_0$. Con esto, la entrada de menor valor está en la primera posición del arreglo.2. Considerar las posiciones del arreglo $a_1, a_2, \ldots$, seleccionar el elemento de menor valor e intercambiarlo con $a_1$. Las dos primeras entradas están en orden.3. Continuar este proceso encontrando o seleccionando el elemento de menor valor de los restantes elementos del arreglo, intercambiándolos adecuadamente. **Ejemplo:** Ordenar el arreglo $[51,  21,  39,  80,  36]$ ![Ordena_Seleccion3.PNG](attachment:Ordena_Seleccion3.PNG) ![Ordena_Seleccion_Seudocodigo.PNG](attachment:Ordena_Seleccion_Seudocodigo.PNG)<jupyter_code># Ordenamiento Selección

miLista = [51,21,39,80,36]
print("lista desordenada: ", miLista)
n = len(miLista)

for i in range(0,n-1):
    minimo = i
    for j in range(i+1, n):
        if miLista[j] < miLista[minimo]:
            minimo = j
    aux = miLista[i]
    miLista[i] = miLista[minimo]
    miLista[minimo] = aux

print("lista ordenada: ", miLista)<jupyter_output>lista desordenada:  [51, 21, 39, 80, 36]
lista ordenada:  [21, 36, 39, 51, 80]<jupyter_text>Ordenamiento por Insersión Los pasos del algoritmo son:1. El primer elemento, $a_0$ se considera ordenado; es decir el arreglo inicial consta de un elemento.2. Se inserta $a_1$ en la posición correcta, delante o detrás de $a_0$, dependiendo de que sea mayor o menor.3. Por cada ciclo o iteración $i$ (𝑑𝑒𝑠𝑑𝑒 $i = 1$ hasta $n-1$) se explora la sublista $a_{i-1} \ldots, a_{0}$ buscando la posición correcta de inserción; a la vez se mueve hacia la derecha en la sublista una posición todos los elementos mayores que el elemento a insertar $a_i$, para dejar vacía esa posición.4. Insertar el elemento en la posición correcta. **Ejemplo:** Ordenar el arreglo $[50,  20,  40,  80,  30]$ ![Ordena_Insersion.PNG](attachment:Ordena_Insersion.PNG) ![Ordena_Insersion_Seudocodigo.PNG](attachment:Ordena_Insersion_Seudocodigo.PNG)<jupyter_code># Algoritmo de insersion

miLista = [50,20,40,80,30]

print("LIsta desordenada: ", miLista)

n = len(miLista)

for i in range(1,n):
    actual = miLista[i]
    j = i
    while j > 0 and miLista[j-1] > actual:
        miLista[j] = miLista[j-1]
        j = j - 1
    miLista[j] = actual
print("LIsta ordenada: ", miLista)<jupyter_output><empty_output><jupyter_text>Ordenamiento Shell **Inserción directa:** Cada elemento se compara con los elementos contiguos a su izquierda, uno tras otro.- Si el elemento a insertar es el menor hay qué realizar muchas comparaciones antes de colocar en su lugar definitivo.**Shell:** modifica los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño.- Generalmente se toma como salto inicial $n/2$ ($n$, número de elementos), luego se reduce el salto a la mitad en cada repetición hasta que le salto es de tamaño $1$. **Ejemplo:** ordenar el arreglo $[6, 1, 5, 2, 3, 4, 0]$- $n = 7$, salto inicial $n/2 \approx 3$ ![Ordena_Shell.PNG](attachment:Ordena_Shell.PNG) ![Ordena_Shell_Seudocodigo.PNG](attachment:Ordena_Shell_Seudocodigo.PNG)<jupyter_code>#Ordenamiento Shell
miLista = [6,1,5,2,3,4,0]

print("LIsta desordenada: ", miLista)

n = len(miLista)

intervalo = n//2
while intervalo > 0 :
    for i in range(intervalo, n):
        j = i
        aux = miLista[i]
        while j >= intervalo and miLista[j - intervalo] > aux:
            miLista[j] = miLista[j - intervalo]
            j = j - intervalo
            miLista[j] = aux
    if intervalo == 2:
        intervalo = 1
    else:
        intervalo = intervalo // 2

print("LIsta sordenada: ", miLista)<jupyter_output><empty_output><jupyter_text>Búsqueda Cuando se trabaja con grandes cantidades de datos es necesario determinar si una estructura contiene un valor que coincida con un cierto valor clave. El proceso de encontrar un elemento específico se denomina búsqueda.  Se analizarán dos técnicas de búsqueda:  - Lineal o secuencial: más sencilla,   - Binaria o dicotómica: más eficiente.**Ejemplo:** encontrar un nombre en una guía telefónica para consultar su teléfono.  Búsqueda Secuencial- El algoritmo de búsqueda secuencial compara cada elemento del conjunto de datos con la clave de búsqueda. - Dado que el conjunto no está en un orden particular, es probable que el elemento a buscar sea el primer elemento, el último o cualquier otro. - En promedio, el algoritmo tendrá que comparar la clave de búsqueda con al menos la mitad de los elementos. - Este método funciona bien con conjuntos pequeños o no ordenados. La eficiencia de la búsqueda secuencial o lineal es pobre. **Ejemplo:** Buscar el elemento `u`: ![Busqueda01.PNG](attachment:Busqueda01.PNG)  Pseudocódigo: ![Busqueda03.PNG](attachment:Busqueda03.PNG)<jupyter_code>#lista = ['c','o','m','p','u','t','a','c','i','o','n']
clave = input("Ingrese el elemento a encontrar")
lista = "computacion"
n = len(lista)
for i in range(n):
    if lista[i] == clave:
        print("la clave está en la posición: ", i)<jupyter_output><empty_output><jupyter_text>![Busqueda04.PNG](attachment:Busqueda04.PNG)<jupyter_code>mayor = lista[0]
for i in range(1,n):
    if lista[i] > mayor:
        mayor = lista[i]
        j = i
print("el mayor es: ", mayor, " y se encuentra en la posición ", j)<jupyter_output><empty_output><jupyter_text>![Busqueda05.PNG](attachment:Busqueda05.PNG)<jupyter_code>mayor = lista[0]
for i in range(1,n):
    if lista[i] < mayor:
        mayor = lista[i]
print("el mayor es: ", mayor)<jupyter_output><empty_output><jupyter_text>Eficiencia y Complejidad Considerando la cantidad de comparaciones**- Mejor caso: 1.** El elemento buscado está en la primera posición, es decir, se hace una sola comparación.**- Peor caso: n.** El elemento buscado está en la última posición, necesitando igual número de comparaciones que la cantidad total de elementos en el arreglo.**- Caso promedio: n/2.** El elemento buscado estará cerca de la mitad, necesitando, en promedio, la mitad de comparaciones.La velocidad de ejecución depende linealmente del tamaño del arreglo.  Búsqueda Binaria- La búsqueda secuencial se aplica a cualquier lista. - Si la lista está ordenada, la búsqueda binaria proporciona una técnica de búsqueda mejorada. - Una búsqueda binaria típica es la búsqueda de una palabra en un diccionario. - Una idea similar se aplica en la búsqueda en una lista ordenada.   - Se sitúa la lectura en el centro de la lista y se comprueba si la clave coincide con el valor del elemento central. Si no se encuentra el valor de la clave, se sigue la búsqueda uno en la mitad inferior o superior del elemento central de la lista.    - En general, si los datos de la lista están ordenados se puede utilizar esa información para acortar el tiempo de búsqueda. **Algoritmo:** Suponiendo la lista almacenada en un arreglo, los índices de la lista son: `bajo=0` y `alto=n-1`, y `n` es el número de elementos en el arreglo.1. Calcular el índice del punto central del arreglo: `central = mod((bajo+alto)/2)` (división entera)2. Comparar el valor de este elemento central con la clave: ![Binaria01.PNG](attachment:Binaria01.PNG) - Si `a[central]<clave`, la nueva sublista de búsqueda tiene por valores extremos de su rango `bajo = central+1 … alto`.- Si `a[central]>clave`, la nueva sublista de búsqueda tiene por valores extremos de su rango `bajo … central-1 = alto`. ![Binaria02.PNG](attachment:Binaria02.PNG) El algoritmo se termina bien o porque se ha encontrado la clave o porque el valor `bajo` excede a `alto` y el algoritmo devuelve el indicador de fallo `-1` (búsqueda no encontrada). **Ejemplo:** Buscar la clave `40` en el siguiente arreglo: ![Binaria03.PNG](attachment:Binaria03.PNG) ![Binaria04.PNG](attachment:Binaria04.PNG) Buscar en la sublista derecha de Central: ![Binaria05.PNG](attachment:Binaria05.PNG) Buscar en la sublista derecha de Central: ![Binaria06.PNG](attachment:Binaria06.PNG) El algoritmo ha requerido 3 comparaciones frente a 8 comparaciones que se hubieran requerido con la búsqueda secuencial.  Algoritmo ![Binaria07.PNG](attachment:Binaria07.PNG)<jupyter_code>lista = [-8, 1, 3, 6, 9, 15, 23, 87, 109]
dato = 87

inf = 0
sup = len(lista) - 1
while inf <= sup:
    centro = (sup - inf) // 2 + inf
    if lista[centro] == dato:
        print('el dato está en la posición ', centro)
        break
    else:
        if dato < lista[centro]:
            sup = centro - 1
        else:
            inf = centro + 1
else:
    print('El elemento no se encuentra en la lista')<jupyter_output><empty_output><jupyter_text>Eficiencia y ComplejidadConsiderando la cantidad de comparaciones**- Mejor caso: 1.** El elemento buscado está en el centro, por lo tanto se hace una sola comparación.**- Peor caso: log(n).** El elemento buscado está en una esquina.**- Caso promedio: log(n/2).**La velocidad de ejecución depende logarítmicamente del tamaño del arreglo.  Comparación: Búsqueda Binaria y Secuencial ![ComparacionBinariaSecuencial.png](attachment:ComparacionBinariaSecuencial.png)  Una breve, brevísima introducción a la generación de números aleatorios...<jupyter_code>import random as rnd<jupyter_output><empty_output><jupyter_text>Todas las funciones del módulo dependen de la función básica *random()*, que genera **UN** valor aleatorioa de punto flotante que cumple con una distribución uniforme en el intervamo semi-abierto $[0.0,1.0)$<jupyter_code>a = rnd.random()
print(a)<jupyter_output><empty_output><jupyter_text>Si lo que se quiere es generar **un** valor entero aleatorio en un rango especificado:<jupyter_code>b = rnd.randint(165,324)
print(b)
a = rnd.randrange(0,100, 2)
print(a)<jupyter_output><empty_output><jupyter_text>Si lo que se quiere es generar una lista de valores aleatorios...<jupyter_code>listarnd = []
b = rnd.randint(0,100)
print(b)
for i in range(b):
    c = rnd.randint(0,10)
    listarnd.append(c)

print(listarnd)<jupyter_output><empty_output><jupyter_text>Y si se quiere seleccionar un valor aleatoriamente de la lista...<jupyter_code>print(rnd.choice(listarnd))<jupyter_output><empty_output><jupyter_text>Otra forma alternativa (y más eficiente) de generar una lista de valores usando *list comprenhension*...<jupyter_code>a = rnd.randint(0,100)
b = rnd.randint(0,100)
print("rango aleatorio de los números aleatorios: ",a)
print("cantidad aleatoria de números aleatorioas a ser creados ",b)
z = [rnd.randint(0,a) for i in range(b)]
print(z)<jupyter_output><empty_output><jupyter_text>Como estas, existen muchas otras funciones para generar números aleatorios. Los invito a que las exploren.<jupyter_code>def busqueda2(a,x):
    print(a)
    n = len(a)
    for i in range(n):
        if a[i] == x:
            print("el elemento está en la posición:", i)
            #break


lista = "paralelepipedo"

busqueda2(lista,"e")
def BusquedaMayor(a):
    n = len(a)
    mayor = "a"
    for i in range(n):
        if a[i] > mayor:
            mayor = a[i]
    print("La letra de mayor valor es: ", mayor)


lista = "paralelepipedo"

BusquedaMayor(lista)
def BusquedaMenor(a):
    n = len(a)
    menor = "z"
    for i in range(n):
        if a[i] < menor:
            menor = a[i]
    print("La letra de mayor valor es: ", menor)


lista = "paralelepipedo"

BusquedaMenor(lista)
numero = int(input("Ingrese el número: "))
x = 2
resto = numero % x

while (resto != 0) and (x < numero):
    x = x + 1
    resto = numero % x

if x == numero:
    print("El número {0} es primo".format(numero))
else:
    print("El número {0} no es primo".format(numero))<jupyter_output><empty_output><jupyter_text>copiado de listas<jupyter_code>import timeit

COUNT = 50000000
print("Array duplicating. Tests run", COUNT, "times")
setup = 'a = [0,1,2,3,4,5,6,7,8,9]; import copy'

print("b = list(a)\t\t", timeit.timeit(stmt='b = list(a)', setup=setup, number=COUNT))
print("b = copy.copy(a)\t", timeit.timeit(stmt='b = copy.copy(a)', setup=setup, number=COUNT))
print("b = a.copy()\t\t", timeit.timeit(stmt='b = a.copy()', setup=setup, number=COUNT))
print("b = a[:]\t\t", timeit.timeit(stmt='b = a[:]', setup=setup, number=COUNT))
print("b = a[0:len(a)]\t\t", timeit.timeit(stmt='b = a[0:len(a)]', setup=setup, number=COUNT))
print("*b, = a\t\t\t", timeit.timeit(stmt='*b, = a', setup=setup, number=COUNT))
print("b = []; b.extend(a)\t", timeit.timeit(stmt='b = []; b.extend(a)', setup=setup, number=COUNT))
print("b = []; for item in a: b.append(item)\t", timeit.timeit(stmt='b = []\nfor item in a:  b.append(item)', setup=setup, number=COUNT))
print("b = [i for i in a]\t", timeit.timeit(stmt='b = [i for i in a]', setup=setup, number=COUNT))
print("b = [*a]\t\t", timeit.timeit(stmt='b = [*a]', setup=setup, number=COUNT))
print("b = a * 1\t\t", timeit.timeit(stmt='b = a * 1', setup=setup, number=COUNT))<jupyter_output>Array duplicating. Tests run 50000000 times
b = list(a)		 7.0040055440003925
b = copy.copy(a)	 16.520983460000025
b = a.copy()		 4.074136729000202
b = a[:]		 4.2738537780001025
b = a[0:len(a)]		 6.9480276250001225
*b, = a			 7.86900979200027
b = []; b.extend(a)	 4.920738523999717
b = []; for item in a: b.append(item)	 34.28185710400021
b = [i for i in a]	 20.60310467799991
b = [*a]		 3.2428117169997677
b = a * 1		 4.174813147999885
{'fraction_non_alphanumeric': 0.10914719954967633, 'fraction_numerical': 0.028257810301153954, 'mean_word_length': 4.517391304347826, 'pattern_counts': {'":': 0, '<': 71, '<?xml version=': 0, '>': 73, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '16', 'dir': 'jupyter-structured-clean-dedup', 'id': '104508', 'license': 'MIT', 'n_tokens_mistral': 6814, 'n_tokens_neox': 6595, 'n_words': 2144, 'path': 'Sesion_09_Ordenamiento_y_Busqueda-sltn.ipynb', 'repo_name': 'UNADCdD/Python-intro', 'size': '17787'}