lab oratorio algoritmia estructura datos - sesion 12

Laboratorio de Algoritmia y Estructura de Datos I Página 1

UNIVERSIDAD CATÓLICA DE SANTA MARÍAPROGRAMA PROFESIONAL DE INGENIERÍA DE SISTEMAS

SESIÓN 12:

ORDENACIÓN Y BÚSQUEDA. Parte I

IOBJETIVOS

• Explicar los principales métodos de ordenamiento.• Explicar los principales métodos de búsqueda.• Aplicar métodos de ordenamiento y búsqueda a la solución de problemas reales.

IITEMAS A TRATAR

Método de ordenación por Intercambio. Método de ordenación por Inserción. Método de ordenación Burbuja. Método de ordenación por selección.

IIIMARCO TEORICO

ORDENACIÓN

La ordenación de los datos consiste en disponer un conjunto de datos (o una estructura) en algún determinado orden con respecto a alguno de sus campos.Orden: Relación de una cosa con otra.Clave: Campo por el cual se ordena.Según donde estén almacenados los datos a Ordenar, podemos decir que la Ordenación es:Interna: Arrays, listas o árbol. Típicamente en RAM.Externa: En Archivos en discos o cintas.

ORDENUna lista de datos está ordenada por la clave k si la lista está en orden con respecto a la clave anterior.

Mgter. Carlo Corrales D. - Mgter. Karim Guevara P. - Mgter. Juan P. Apaza C. Sesión 12


Este Orden puede ser:Ascendente: (i<j) entonces (k[i]<=k[j]) {nuestros ej}Descendente: (i>j) entonces (k[i]>=k[j])Hay Numerosos Métodos de Ordenamiento que difieren en eficiencia.Análisis de algoritmo orientado a las comparaciones realizadas por cada uno.Las comparaciones serán función de “n”. Siendo “n” el tamaño del vector a Ordenar.

CLASIFICACIÓN DE MÉTODOS DE ORDENACIÓN

Todos los métodos se verán con Orden Ascendente.Analizaremos los siguientes métodos:Básicos: Son eficaces en Listas pequeñas- Burbuja e Intercambio: simple pero Ineficiente.- Inserción: Recomendado.Avanzados: Son eficaces en Listas grandes.- Shell: muy extendido.

ORDENACIÓN POR INTERCAMBIO

El más sencillo de todos. Se basa en:la lectura sucesiva de la lista a ordenar, comparando el elemento inferior de la lista con todos los restantes.Efectuando el Intercambio de posiciones cuando el orden resultante no sea correcto.Siendo n la cantidad de elementos, Realizará al menos n–1 pasadas.

ORDENACIÓN POR INTERCAMBIO: EJEMPLOOrdenar la siguiente secuencia de números: 8, 4, 6, 2

SOLUCIÓNPasada 0:Se compara a[0] con todos, así primero se cambia a[0] con a[1] pues a[0] > a[1] y debe serAscendente, es decir a[0]<a[1] …y por ultimo a[0] con a[3]



Pasada 1:El elemento mas pequeño esta en a[0] y se analiza la sublista restante.Al cabo de la pasada, el segundo mas chico esta en a[1]….

Pasada 2:

Pasada i: Al cabo de la pasada i, el elemento de orden i, está en a[i]

ORDENACIÓN POR INTERCAMBIO: CODIFICACIÓN EN C/C++

void ordIntercambio (int a[], int n){int i, j, aux; /* se realizan n-1 pasadas, a[o] ... a[n-2] */for (i = 0 ; i <= n-2 ; i++)/* coloca mínimo de a[i+1]...a[n-1] en a[i] */

for (j = i+1 ; j <= n-1 ; j++)if (a[i] > a[j]){ aux = a[i];

a[i] = a[j];a[j]= aux ;

}}

Complejidad (n–1)(n–2)Del Orden F(n)=n2.

Intercambio.cpp#include<iostream.h>#include<stdlib.h>#define N 4void ordIntercambio (int a[], int n){int i, j, aux; /* se realizan n-1 pasadas, a[o] ... a[n-2] */for (i=0;i<=n-2;i++)/* coloca minimo de a[i+1]...a[n-1] en a[i] */

for (j=i+1;j<=n-1;j++)if (a[i] > a[j]){ aux=a[i];

a[i]=a[j];a[j]=aux;

}}



void mostrar(int a[],int n){

int i;for(i=0;i<n;i++){

cout<<a[i]<<",";}

}int main(char *arg){

int v[]={8, 4, 6, 2};ordIntercambio(v,N);mostrar(v,N);cout<<endl<<endl;system("PAUSE");;return 0;

}

Presione F5 o haga clic en

PROPUESTOSOrdenar manualmente usando el método de Intercambio la siguiente secuencia.10, 5, 2, 6, 7, 3, 8, 9,14,34,11,1,4

ORDENACIÓN POR INSERCIÓN

Similar al proceso de ordenar tarjetas en un tarjetero por orden alfabético:Consiste en insertar un elemento en su posición correcta, dentro de una lista que ya estáOrdenada.Algoritmo:El 1er elemento a[0] se lo considera ordenadoSe inserta a[1] en la posición correcta, delante o detrás del a[0], según sea mayor o menorPor cada bucle i (desde i=1 hasta n–1) se explora la sublista a[0]..a[i–1] buscando la posicióncorrecta de inserción del elemento a[i]Al dejar vacío la posición a[i] se impone un desplazamiento de todo el vector, desde el lugarde inserción.

ORDENACIÓN POR INSERCIÓN: EJEMPLOOrdenar la siguiente secuencia de números: 85, 87, 81,4, 22, 71, 78



SOLUCIÓN



ORDENACIÓN POR INSERCIÓN: CODIFICACIÓN EN C/C++

void ordInsercion (int [] a, int n){

int i, j, aux;for (i = 1; i < n; i++) // El índice j explora sublista a[i-1]..a[0]{ // buscando posición correcta del elemento destino, para asignarlo en a[j] */

j = i;aux = a[i]; /* se localiza el punto de inserción explorando hacia

abajo */while (j > 0 && aux < a[j-1])/* desplazar elementos hacia arriba para hacer espacio */{

a[j] = a[j-1];j--;

}a[j] = aux;

}}

Complejidad n(n–1)Del Orden F(n)=n2.

Insercion.cpp#include<iostream.h>#include<stdlib.h>#define N 4void ordInsercion(int a[],int n){

int i, j, aux;for (i = 1; i < n; i++) // El índice j explora sublista a[i-1]..a[0]{ // buscando posición correcta del elemento destino, para asignarlo en a[j] */

j = i;aux = a[i]; // se localiza el punto de inserción explorando hacia abajo while (j > 0 && aux < a[j-1])/* desplazar elementos hacia arriba para hacer espacio */{

a[j] = a[j-1];j--;

}a[j] = aux;

}}void mostrar(int a[],int n){


cout<<a[i]<<",";}


int v[]={8, 4, 6, 2};ordInsercion(v,N);mostrar(v,N);cout<<endl<<endl;system("PAUSE");;return 0;

}




PROPUESTOSOrdenar manualmente usando el método de Inserción la siguiente secuencia.10, 5, 2, 6, 7, 3, 8, 9,14,34,11,1,4

ORDENACIÓN POR BURBUJA

Los elementos burbujean:Los mas grandes, caen al fondo del array (posición n)Los mas chicos suben a la cima (posición 0).Estudia parejas de elementos Adyacentesa[0] y a[1], a[1] y a[2]…a[i] y a[i+1]… a[n–2] y a[n–1].Si a[i+1] < a[i] Entonces Los INTERCAMBIAAlgoritmo:Pasada 0: considera desde (a[0], a[1]) hasta (a[n–2], a[n–1]).• En a[n–1] esta el elemento mas grande.Pasada 1: considera desde (a[0], a[1]) hasta (a[n–3], a[n–2]).• En a[n–2] esta el segundo elemento mas grande.Pasada i: considera desde (a[0], a[1]) hasta (a[n–i–2], a[n-i–1]).• En a[n–i–1] esta el elemento de orden i.El proceso termina con la pasada n–1• El elemento mas pequeño esta en a[0].

ORDENACIÓN POR BURBUJA: EJEMPLOOrdenar la siguiente secuencia de números: 50, 20, 40, 80, 30



SOLUCIÓN

Pasada 0:



ORDENACIÓN POR BURBUJA: CODIFICACIÓN EN C/C++void ordBurbuja (int a[], int n){ int interruptor = 1;

int pasada, j;for (pasada=0;pasada<n-1 && interruptor;pasada++){

long aux;/* bucle externo controla la cantidad de pasadas */interruptor = 0;for (j = 0; j < n-pasada-1; j++)

if (a[j] > a[j+1]) /* elementos desordenados, es necesariointercambio */{

interruptor = 1;aux = a[j];a[j] = a[j+1];a[j+1] = aux;

}}

}

Mejor Caso: en una lista ordenada, hará una sola pasada: F(n)=nPeor Caso: F(n)=n2

Burbuja.cpp#include<iostream.h>#include<stdlib.h>#define N 5void ordBurbuja (int a[], int n){ int interruptor = 1;

int pasada, j;for (pasada=0;pasada<n-1 && interruptor;pasada++){

long aux;/* bucle externo controla la cantidad de pasadas */interruptor = 0;for (j = 0; j < n-pasada-1; j++)

if (a[j] > a[j+1])/* elementos desordenados, es necesario intercambio */{

interruptor = 1;aux = a[j];a[j] = a[j+1];a[j+1] = aux;

}}

}void mostrar(int a[],int n){


cout<<a[i]<<",";}


int v[]={50, 20, 40, 80, 30};ordBurbuja(v,N) ;mostrar(v,N);cout<<endl<<endl;system("PAUSE");;return 0;

}




PROPUESTOSOrdenar manualmente usando el método de Burbuja la siguiente secuencia.10, 5, 2, 6, 7, 3, 8, 9,14,34,11,1,4

ORDENACIÓN POR SELECCIÓN

− En cada paso seleccionamos el elemento de menor valor de los no ordenados y lo colocamoscomo primero de los no ordenados:



Para i=1 hasta n-1 hacerAsignar a k el menor valor de v[i..n]Intercambiar v[i] con v[k]

Fpara

void ordSeleccion (int A[], int n){

int minimo=0, temp=0;for(int i=0 ; i<n-1 ; i++){

minimo=i;for(int j=i+1 ; j<n ; j++){

if (A[minimo] > A[j])minimo=j;

}temp=A[minimo];A[minimo]=A[i];A[i]=temp;

}}Seleccion.cpp#include<iostream>#include<stdlib.h>#define N 5using namespace std;void ordSeleccion (int A[], int n){

int minimo=0, temp=0;for(int i=0 ; i<n-1 ; i++){

minimo=i;for(int j=i+1 ; j<n ; j++){

if (A[minimo] > A[j])minimo=j;

}temp=A[minimo];A[minimo]=A[i];A[i]=temp;

}}



void mostrar(int a[],int n){


cout<<a[i]<<",";}


int v[]={50, 20, 40, 80, 30};ordSeleccion(v,N) ;mostrar(v,N);cout<<endl<<endl;system("PAUSE");;return 0;

}

PROPUESTOSOrdenar manualmente usando el método de Selección la siguiente secuencia.10, 5, 2, 6, 7, 3, 8, 9,14,34,11,1,4



IV(La práctica tiene una duración de 4 horas) ACTIVIDADES

1. Analizar el procedimiento de ordenación de cada uno de los métodos a través de la siguiente aplicación Java

http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html


http://www.cs.oswego.edu/~mohammad/classes/csc241/samples/sort/Sort2-E.html


2. Verificar el tiempo de ejecución de los siguientes métodos de búsqueda

http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html



3. Verificar la cantidad de comparaciones que efectua los diferentes métodos de ordenamiento

http://maven.smith.edu/~thiebaut/java/sort/



4. Búsqueda Binaria

http://euler.slu.edu/~goldwasser/demos/BinarySearch/



5. Búsqueda Lineal

http://www.cosc.canterbury.ac.nz/mukundan/dsal/LSearch.html



6. Búsqueda Binaria

http://www.cosc.canterbury.ac.nz/mukundan/dsal/BSearch.html



VEJERCICIOS

1. Desarrolle un programa el lenguaje ANSI C que dados dos arreglos A y B cada uno con 10 elementos:

– Llene los arreglos A y B.– Ordene ascendentemente A y B por los métodos de intercambio,

inserción, burbuja y selección.– Mezcle ordenadamente los elementos de A y B en un arreglo C el cual no

debe contener elementos repetidos.

2. Dado un arreglo de tamaño 30 que almacena números reales, desarrolle un programa el lenguaje ANSI C que llene el arreglo. Además, debe permitir ordenar los elementos que están en las posiciones pares en forma ascendente y los elementos que están en las posiciones impares en forma descendente utilizando el algoritmo de selección.Observaciones:

– No utilice otro arreglo para dejar ordenado los elementos.– No ordene los valores al momento de ingresarlos.

3. En los algoritmos Burbuja o Selección, el elemento más pequeño de a[i..n] es colocado en la posición i mediante intercambios, para valores sucesivos de i. Otra posibilidad es colocar el elemento máximo de a[1..j] en la posición j, para valores de j entre n y 1. A este algoritmo se le denomina ordenación por Ladrillos (Bricksort). Implementar dicho algoritmo y estudiar su complejidad.

4. Una variante curiosa de los algoritmos anteriores resulta al combinar los métodos de la Burbuja y de los Ladrillos. La idea es ir colocando alternativamente el mayor valor de a[1..j] en a[j], y el menor valor de a[i..n] en a[i]. Implementar dicho algoritmo, conocido como Sacudidas (Shakersort), y estudiar su complejidad.

5. Modificar el algoritmo de ordenación por Selección de forma que se intercambien los elementos únicamente si son distintos. ¿Qué impacto tiene esta modificación sobre la complejidad del algoritmo?

6. Se da un arreglo que contiene N números. Se desea determinar si hay 2 números dentro del arreglo cuya suma sea igual a un número dado K. Por ejemplo, si la entrada es 8, 4, 1, 6, y K es 10, entonces la respuesta es sí (4 y 6). Un número puede ser utilizado dos veces. De un algoritmo de tiempo O(NlogN) para resolver este problema (Pista: ordene los elementos primero. Después de hacer esto, se podrá resolver este problema en tiempo lineal).

7. El problema del k-ésimo elemento: Dado un vector de enteros, queremos encontrar el elemento que ocuparía la posición k si el vector estuviera ordenado en orden creciente (esto es, el k-ésimo menor elemento). Una primera idea para resolver este problema consiste en ordenar primero el



vector y después escoger el elemento en la posición k, pero la complejidad de este algoritmo es O(nlogn). ¿Puede hacerse de alguna forma más eficiente? Considerar la siguiente idea:Ordenar el vector sólo hasta la posición k, utilizando un método incremental como el de Selección.

8. Modificar el algoritmo bubble-sort, de tal manera que dé el comportamiento requerido en las siguientes gráficas. Verificar experimentalmente que la modificación disminuye el tiempo de ordenamiento. Original Modificado: es más rápido.

Original Modificado: es más rápido

VICUESTIONARIO

1. ¿Cuales son los métodos de búsqueda que conoces? ¿Cuál es el mejor?

2. ¿Cuáles son los órdenes de las complejidades de cada uno de los métodos de ordenación y búsqueda vistos en esta práctica? ¿Cuál es el menos complejo?



VIIBIBLIOGRAFIA Y REFERENCIAS

BIBLIOGRAFÍA BÁSICA− D.S.Malik, “DATA STRUCTURES USIGN C++”, Thomson Learning, 2003− J. Galve. “ALGORITMIA”, Ed.Adisson Wesley, España, 2000.− Brassard, “ANÁLISIS DE ALGORITMOS”, Ed. Mc. Graw Hill., España, 1999.,

BIBLIOGRAFÍA COMPLEMENTARIA• Wirth M., “ALGORITMOS Y ESTRUCTURA DE DATOS”, Ed. Addison Wesley,

México, 1997• Aho. “DISEÑO Y ANÁLISIS DE ALGORITMOS”, Ed. Addison Wesley. USA,

1999.

• Deitel & Deitel “COMO PROGRAMAR EN C/C++”. Editorial Prentice Hall, 1995.


lab oratorio algoritmia estructura datos - sesion 12

Documents