ordenacion seleccion
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.TRANSCRIPT
-
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