33
Introducción Motivación Ordenación por selección Algoritmos y Estructuras de Datos II Ordenación 9 de marzo de 2015 Ordenación Algoritmos y Estructuras de Datos II

Ordenacion Seleccion

Embed Size (px)

DESCRIPTION

En ciencias de la computación , la selección especie es un algoritmo de clasificación , en concreto una en el lugar de comparación de orden . Tiene O ( n 2 ) complejidad de tiempo, por lo que es ineficiente en listas grandes, y por lo general realiza peor que el parecido ordenación por inserción . Selección especie se destaca por su sencillez, y tiene ventajas de rendimiento sobre más complicados algoritmos en ciertas situaciones, en particular donde la memoria auxiliar es limitado.El algoritmo divide la lista de entrada en dos partes: la lista secundaria de elementos ya ordenados, que se construye a partir de izquierda a derecha en la parte delantera (izquierda) de la lista, y la lista secundaria de los puntos que quedan pueden ordenar que ocupan el resto de la lista. Inicialmente, la sublista ordenada está vacío y la sublista sin clasificar es la lista completa de entrada. El algoritmo procede por la búsqueda de la más pequeña (o grande, dependiendo del orden de clasificación) elemento de la lista secundaria sin clasificar, el intercambio con el elemento sin clasificar más a la izquierda (ponerlo en orden de clasificación), y mover los límites sublista un elemento a la derecha.

Citation preview

  • IntroduccinMotivacin

    Ordenacin por seleccin

    Algoritmos y Estructuras de Datos II

    Ordenacin

    9 de marzo de 2015

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    Contenidos

    1 Introduccin

    2 Motivacin

    3 Ordenacin por seleccinAlgoritmoEjemploComando forAnlisis

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    Generalidades

    Toda la informacin sobre la materia se encuentra en la wiki,accesible desde cs.famaf.unc.edu.ar/wiki

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    Algoritmos y Estructuras de Datos

    Introduccin a los AlgoritmosAlgoritmos y Estructuras de Datos I

    pre- y post- condicionesqu hace un algoritmo

    Algoritmos y Estructuras de Datos IIcmo hace el algoritmo

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    Ejemplo de qu y cmo de un algoritmo

    Ejemplo: un algoritmo para contar las letras a de un arreglo.Qu: devuelve (o cuenta o computa) el nmero deocurrencias de la letra a del arreglo dado.Cmo: recorre el arreglo de izquierda a derechaincrementando un contador cada vez que lee la letra a.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    Anlisis de algoritmos

    Analizar el cmo permitepredecir el tiempo de ejecucin (eficiencia en tiempo)predecir el uso de memoria (eficiencia en espacio)predecir el uso de otros recursoscomparar distintos algoritmos para un mismo problema

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    Organizacin de la materia

    La materia est organizada en tres partes:Anlisis de algoritmos.

    Cmo se ejecutan los algoritmos y estimar cunto trabajorealiza.

    Estructuras de datos.Tipos de datos concretos y abstractos.

    Algoritmos avanzados.Algunas tcnicas para resolver problemas algortmicos.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    Problema del pintor

    Un pintor tarda una hora y media en pintar una paredde 3 metros de largo. Cunto tardar en pintar unade 5 metros de largo?

    3 metros 90 minutos1 metro 30 minutos

    5 metros 150 minutosSolucin: dos horas y media.El trabajo de pintar la pared es proporcional a su longitud.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    Problema del bibliotecario

    Un bibliotecario tarda un da en ordenaralfabticamente una biblioteca con 1000 expedientes.Cunto tardar en ordenar una con 2000expedientes?

    Razonamiento similar

    1000 expedientes 1 da2000 expedientes 2 das

    Solucin: dos das.Est bien? Es el trabajo de ordenar expedientesproporcional a la cantidad de expedientes a ordenar?

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    Otros problemasdel pintor

    Un pintor tarda una hora y media en pintar una paredcuadrada de 3 metros de lado. Cunto tardar enpintar una de 5 metros de lado?

    9 metros cuadrados 90 minutos1 metro cuadrado 10 minutos

    25 metros cuadrados 250 minutosSolucin: cuatro horas y 10 minutos.El trabajo de pintar la pared cuadrada es proporcional a susuperficie, que es proporcional al cuadrado del lado.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    Otros problemasel del globo esfrico

    Si lleva cinco horas inflar un globo aerosttico esfricode 2 metros de dimetro, cunto llevar inflar uno de4 metros de dimetro?

    El trabajo de inflar el globo es proporcional a su volumen, quees proporcional al cubo del dimetro (V = pid

    3

    6 ).

    dimetro = 2 k metros cbicos 5 horasdimetro = 4 8k metros cbicos 40 horas

    Solucin: cuarenta horas.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    Algoritmos de ordenacin

    Para resolver el problema del bibliotecario, es necesarioestablecer a qu es proporcional la tarea de ordenarexpedientes,estudiar mtodos de ordenacin,asumiremos la existencia de elementos o items a ordenar,relacionados por un orden total,que deben ordenarse de menor a mayor yque no necesariamente son diferentes entre s.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    Cmo?

    Reflexionemos sobre lo siguiente:Qu significa que una secuencia de libros, nmeros,palabras, etc. est ordenada?Cmo hacen para controlar si una secuencia de nmerosest ordenada?

    (a esta pregunta la vamos a continuar en el prctico y en ellaboratorio)

    Cmo haran para ordenar de menor a mayor ciertosdatos o ciertas cosas fsicas que estn desordenados/as?

    nmeroscartas de un juego,palabras,libros.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Ordenacin por seleccinIdea

    Es el algoritmo de ordenacin ms sencillo (pero no elms rpido),selecciona el menor de todos, lo coloca en el primer lugarapartndolo del resto,selecciona el menor de todos los restantes, lo coloca enel segundo lugar apartndolo del resto,selecciona el menor de todos los restantes, lo coloca enel tercer lugar apartndolo del resto,. . . (en cada uno de estos pasos ordena un elemento) . . .hasta terminar.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Ordenacin por seleccinEjemplo

    9 3 1 3 5 2 7

    9 3 1 3 5 2 7

    1 3 9 3 5 2 7

    1 3 9 3 5 2 7

    1 2 9 3 5 3 7

    1 2 9 3 5 3 7

    1 2 3 9 5 3 7

    1 2 3 9 5 3 7

    1 2 3 3 5 9 7

    1 2 3 3 5 9 7

    1 2 3 3 5 9 7

    1 2 3 3 5 9 7

    1 2 3 3 5 7 9

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Demo (www.sorting-algorithms.com)

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Ordenacin por seleccinEn un arreglo

    a

    - -a[1,i)

    mnimos ordenados

    a[i,n]

    an no seleccionados

    1 2 3 i -1 i n-1 n

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Ordenacin por seleccinInvariante

    a

    - -a[1,i)

    mnimos ordenados

    a[i,n]

    an no seleccionados

    1 2 3 i -1 i n-1 n

    Invariante:el arreglo a es una permutacin del original,un segmento inicial a[1,i) del arreglo est ordenado, ydicho segmento contiene los elementos mnimos delarreglo.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Ordenacin por seleccinPseudocdigo

    {Pre: n 0 a = A}proc selection_sort (in/out a: array[1..n] of T)

    var i, minp: nati:= 1 {Inv: Invariante de recin}do i < n minp:= min_pos_from(a,i)

    swap(a,i,minp)i:= i+1

    odend proc{Post: a est ordenado y es permutacin de A}

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Ordenacin por seleccinSwap o intercambio

    {Pre: a = A 1 i,j n }proc swap (in/out a: array[1..n] of T, in i,j: nat)

    var tmp: Ttmp:= a[i]a[i]:= a[j]a[j]:= tmp

    end proc{Post: a[i] = A[j] a[j] = A[i] k. k 6{i,j} a[k]=A[k]}

    Garantiza permutacin!

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Ordenacin por seleccinInvariante de la funcin de seleccin

    a

    - -a[1,i)

    mnimos ordenados

    a[i,n]

    an no seleccionados

    1 2 3 i -1 i n-1 ni minp j n - -a[i,j) cuyo min es a[minp] a[j,n] an por revisar

    Invariante:invariante anterior, yel mnimo del segmento a[i,j) est en la posicin minp.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Ordenacin por seleccinFuncin de seleccin

    {Pre: 0 < i n}fun min_pos_from (a: array[1..n] of T, i: nat) ret minp: nat

    var j: natminp:= ij:= i+1 {Inv: a[minp] es el mnimo de a[i,j)}do j n if a[j] < a[minp] then minp:= j fi

    j:= j+1od

    end fun{Post: a[minp] es el mnimo de a[i,n]}

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Comando for

    Fragmentos de la siguiente forma aparecen con frecuencia:

    k:= ndo k m C

    k:= k+1od

    Por simplicidad, lo reemplazaremos por

    for k:= n to m do C od

    siempre que k no se modifique en C.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Comando forReemplazo en min_pos_from

    fun min_pos_from (a: array[1..n] of T, i: nat) ret minp: natvar j: natminp:= ij:= i+1do j n if a[j] < a[minp] then minp:= j fi

    j:= j+1od

    end funfun min_pos_from (a: array[1..n] of T, i: nat) ret minp: nat

    minp:= ifor j:= i+1 to n do if a[j] < a[minp] then minp:= j fiod

    end fun

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Comando forReemplazo en selection_sort

    proc selection_sort (in/out a: array[1..n] of T)var i, minp: nati:= 1do i < n minp:= min_pos_from(a,i)

    swap(a,i,minp)i:= i+1

    odend proc

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Comando forEn selection_sort

    proc selection_sort (in/out a: array[1..n] of T)var minp: natfor i:= 1 to n-1 do

    minp:= min_pos_from(a,i)swap(a,i,minp)

    odend proc

    fun min_pos_from (a: array[1..n] of T, i: nat) ret minp: natminp:= ifor j:= i+1 to n do if a[j] < a[minp] then minp:= j fiod

    end fun

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Problema del bibliotecarioCuando el algoritmo es la ordenacin por seleccin

    Cmo se respondera el problema del bibliotecario si elalgoritmo utilizado por l fuera el de ordenacin porseleccin?Cunto ms trabajo resulta ordenar 2000 expedientesque 1000 con este algoritmo?Cunto trabajo es ordenar 2000 expedientes (con estealgoritmo)?Cunto trabajo es ordenar 1000 expedientes (con estealgoritmo)?Cunto trabajo es ordenar n expedientes (con estealgoritmo)?

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Problema del bibliotecarioAnlisis

    Para contestar estas preguntas habra que analizar elalgoritmo de ordenacin por seleccin, es decir, contarcuntas operaciones elementales realiza.Cuntas sumas, asignaciones, llamadas a funciones,comparaciones, intercambios, etc.En vez de eso, se elige una operacin representativa.Qu es una operacin representativa?Una tal que se repite ms que o tanto como cualquier otra.Hay que buscar la que ms se repite.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Analizando el procedimiento selection_sort

    selection_sort contiene un ciclo,all debe estar la operacin que ms se repite,encontramos una llamada a la funcin min_pos_from yuna llamada al procedimiento swap,el procedimiento swap es constante (siempre realiza 3asignaciones elementales),la funcin min_pos_from, en cambio, tiene un ciclo,nuevamente all debe estar la operacin que ms serepite,encontramos una comparacin entre elementos de a, yuna asignacin (condicionada al resultado de lacomparacin).

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Analizando ordenacin por seleccinConclusin

    La operacin que ms se repite es la comparacinentre elementos de a,toda otra operacin se repite a lo sumo de maneraproporcional a esa,por lo tanto, la comparacin entre elementos de a esrepresentativa del trabajo de la ordenacin por seleccin.Esto es habitual: para medir la eficiencia de los algoritmosde ordenacin es habitual considerar el nmero decomparaciones entre elementos del arreglo.Veremos luego que acceder (o modificar) una celda de unarreglo es constante: su costo no depende de cul es lacelda, ni de la longitud del arreglo.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Cuntas comparaciones realiza la ordenacin porseleccin?

    Al llamarse a min_pos_from(a,i) se realizan n-icomparaciones.selection_sort llama a min_pos_from(a,i) parai {1,2, . . . ,n 1}.por lo tanto, en total son (n-1) + (n-2) + . . . + (n-(n-1))comparaciones.

    es decir, (n-1) + (n-2) + . . . + 1 = n(n1)2 comparaciones.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Resolviendo el problema del bibliotecarioCon la frmula obtenida

    Para un arreglo de tamao n, son n(n1)2 comparaciones.

    1000 expedientes 499500 comparaciones 1 da2000 expedientes 1999000 comparaciones 4 das

    Solucin: 4 das.

    Ordenacin Algoritmos y Estructuras de Datos II

  • IntroduccinMotivacin

    Ordenacin por seleccin

    AlgoritmoEjemploComando forAnlisis

    Resolviendo el problema del bibliotecarioCon una frmula simplificada

    Como n(n1)2 =n22 n2 , el nmero de comparaciones es

    proporcional n2.

    1000 expedientes 1000000 comparaciones 1 da2000 expedientes 4000000 comparaciones 4 das

    Solucin: 4 das.Conviene utilizar la expresin n2 para contestar la pregunta; esms sencillo y da el mismo resultado.

    Ordenacin Algoritmos y Estructuras de Datos II

    IntroduccinMotivacinOrdenacin por seleccinAlgoritmoEjemploComando forAnlisis