Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 19 vistas

    Lab08 - Ordenamiento I

    Cargado por

    Josue Camasca Atmi
    Este documento describe varios algoritmos de ordenamiento comunes como el método de burbuja, selección, inserción directa e inserción binaria. Explica cada algoritmo con detalles sobre su funcionamiento, complejidad y código de implementación.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Lab08 - Ordenamiento I

    Cargado por

    Josue Camasca Atmi
    19 vistas27 páginas
    Este documento describe varios algoritmos de ordenamiento comunes como el método de burbuja, selección, inserción directa e inserción binaria. Explica cada algoritmo con detalles sobre su funcionamiento, complejidad y código de implementación.

    Descripción original:

    lab-8

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento describe varios algoritmos de ordenamiento comunes como el método de burbuja, selección, inserción directa e inserción binaria. Explica cada algoritmo con detalles sobre su funcionamiento, complejidad y código de implementación.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    19 vistas27 páginas

    Lab08 - Ordenamiento I

    Cargado por

    Josue Camasca Atmi
    Este documento describe varios algoritmos de ordenamiento comunes como el método de burbuja, selección, inserción directa e inserción binaria. Explica cada algoritmo con detalles sobre su funcionamiento, complejidad y código de implementación.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 27

    LAB 08: Algoritmos de

    Ordenamiento I
    IS141 - ALGORITMOS

    Prof. Carlos Vila


    carlos.vila@outlook.com
    Contenido

    Método Burbuja
    Método Selección
    Método Inserción Directa
    Método Inserción Binaria
    Método Shell
    Método QuickSort
    Método HeapSort

    Your logo here


    Algoritmos de Ordenamiento
     Introducción
     Algoritmos de
    Ordenamiento

    Your logo here


    Algoritmos de Odenamiento
     En computación y matemáticas un
    algoritmo de ordenamiento es un algoritmo
    que pone elementos de una lista o un
    vector en una secuencia dada por una
    relación de orden, es decir, el resultado de
    salida ha de ser una permutación —o
    reordenamiento— de la entrada que
    satisfaga la relación de orden dada.

    Your logo here


     Ordenamientos eficientes son importantes
    para optimizar el uso de otros algoritmos
    (como los de búsqueda y fusión) que
    requieren listas ordenadas para una
    ejecución rápida. También es útil para
    poner datos en forma canónica y para
    generar resultados legibles por humanos.

    Your logo here


    Quicksort en acción sobre una lista de números
    aleatorios. Las líneas horizontales son valores
    pivote.

    Your logo here


    Algoritmos de Ordenamiento
     Método Burbuja
     Método Selección
     Método Inserción Directa
     Método Inserción Binaria
     Método Shell
     Método QuickSort
     Método HeapSort

    Your logo here


    Método Burbuja
     Definición
     Código
     Conejos y Tortugas

    Your logo here


    Método de Bubuja
    También es conocido como el método del
    intercambio directo.
    La Ordenación de burbuja (Bubble Sort en inglés) es
    un sencillo algoritmo de ordenamiento. Funciona
    revisando cada elemento de la lista que va a ser
    ordenada con el siguiente, intercambiándolos de
    posición si están en el orden equivocado.
    Es necesario revisar varias veces toda la lista hasta
    que no se necesiten más intercambios, lo cual
    significa que la lista está ordenada.

    Your logo here


    Representación animada de ordenación de un conjunto de
    números mediante el algoritmo burbuja. Comenzando desde el
    inicio del vector, se compara cada par de elementos
    adyacentes. Si ambos no están ordenados (el segundo es
    menor que el primero), se intercambian sus posiciones. En cada
    iteración, un elemento menos necesita ser evaluados (el último),
    ya que no hay más elementos a su derecha que necesiten ser
    comparados, puesto que ya están ordenados.

    Your logo here


    Your logo here
    Código
    elementos = [1,3,5,4,7,9,8,6];
    numero = len(elementos);

    i= 0;
    while (i < numero):
    j = i;
    while (j < numero):
    if(elementos[i] > elementos[j]):
    temp = elementos[i];
    elementos[i] = elementos[j];
    elementos[j] = temp;
    j= j+1;
    i=i+1;

    for elemento in elementos:


    print (elemento);
    Your logo here
    Ejemplo del ordenamiento de burbuja
    ordenando una lista de números aleatorios.

    Your logo here


    Conejos y Tortugas
    La posición de los elementos en el ordenamiento de
    burbuja juegan un papel muy importante en la
    determinación del rendimiento. Los elementos
    mayores al principio de la lista son rápidamente
    movidos hacia abajo, mientras los elementos
    menores en el fondo de la lista se mueven a la parte
    superior muy lentamente. Esto llevó a nombrar estos
    elementos conejos y tortugas, respectivamente.

    Your logo here


    Método Selección
     Algoritmo
     Código
     Ventajas
     Desventajas

    Your logo here


    Método de Selección
    El ordenamiento por selección (Selection Sort
    en inglés) es un algoritmo de ordenamiento
    que requiere O(𝑛2 ) operaciones para ordenar
    una lista de n elementos.

    Your logo here


    Algoritmo
     Buscar el mínimo elemento de la
    lista
     Intercambiarlo con el primero
     Buscar el siguiente mínimo en el
    resto de la lista
     Intercambiarlo con el segundo

    Your logo here


    Código

    def selectionsort(lista,tam):
    for i in range(0,tam-1):

    min=i

    for j in range(i+1,tam):
    if lista[min] > lista[j]:
    min=j;

    aux=lista[min];
    lista[min]=lista[i];
    lista[i]=aux;

    Your logo here


    Ventaja
    Este algoritmo mejora ligeramente el
    algoritmo de la burbuja. En el caso de tener
    que ordenar un vector de enteros, esta
    mejora no es muy sustancial, pero cuando
    hay que ordenar un vector de estructuras
    más complejas, la operación intercambiar()
    sería más costosa en este caso.
    Este algoritmo realiza muchas menos
    operaciones intercambiar() que el de la
    burbuja, por lo que lo mejora en algo.

    Your logo here


    Desventaja
     Otra desventaja de este algoritmo respecto a
    otros como el de burbuja o de inserción directa es
    que no mejora su rendimiento cuando los datos ya
    están ordenados o parcialmente ordenados.
     Así como, por ejemplo, en el caso de la
    ordenación de burbuja se requeriría una única
    pasada para detectar que el vector ya está
    ordenado y finalizar, en la ordenación por
    selección se realizarían el mismo número de
    pasadas independientemente de si los datos están
    ordenados o no.

    Your logo here


    Método Inserción Directa
     Definición
     Código

    Your logo here


    Inserción Directa
     El ordenamiento por inserción (insertion sort
    en inglés) es una manera muy natural de
    ordenar para un ser humano, y puede
    usarse fácilmente para ordenar un mazo
    de cartas numeradas en forma arbitraria.
    Requiere O(n²) operaciones para ordenar
    una lista de n elementos.

    Your logo here


    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.

    Your logo here


    Ejemplo de ordenamiento por inserción
    ordenando una lista de números aleatorios.

    Your logo here


    Código

    def insercionDirecta(lista,tam):
    for i in range(1,tam):
    v=lista[i];
    j=i-1;
    while j >= 0 and lista[j] > v:
    lista[j+1] = lista[j];
    j=j-1;
    lista[j+1]=v;

    Your logo here


    Bibliografía
     Algoritmos de Ordenamiento
    › https://es.wikipedia.org/wiki/Algoritmo_de_ordenamiento
    › https://saforas.wordpress.com/2011/01/24/metodos-de-ordenamiento-
    hechos-en-python/

     Ordenamiento Burbuja
    › https://es.wikipedia.org/wiki/Ordenamiento_de_burbuja
    › https://www.youtube.com/watch?v=tKH7nzbtXrc

     Ordenamiento por Selección


    › https://es.wikipedia.org/wiki/Ordenamiento_por_selecci%C3%B3n
    › https://www.youtube.com/watch?v=KCvr7eHXEHE

    Your logo here


    Bibliografía
     Ordenamiento por Inserción Directa
    › https://es.wikipedia.org/wiki/Ordenamiento_por_inserci%C3%B3n
    › https://www.youtube.com/watch?v=o9xAPPWvSo0
    › https://www.youtube.com/watch?v=PUudQLFI8bA

     Ordenamiento shell
    › https://www.youtube.com/watch?v=ATUKgp3R87E

    Your logo here

    También podría gustarte