Tema 11Bsqueda y ordenacin en arreglos

OrdenacinEs un proceso que altera el orden de los elementos de un conjunto.Tiene asociada una relacin de ordenNmeros: valorLetras: alfabetoAuto: Velocidad? Tamao? Autonoma?Amigos: ..?La ordenacin puede ser ascendente o descendente.

OrdenacinMtodosBurbuja (Bubble sort)SeleccinInsercinBurbuja bidireccionalRpido (Quicksort)

Bubble sortLos elementos ms pesados bajanLos elementos ms livianos subenCuando ya no puede bajar ms se sigue con el resto.

Bubble sort1-Como r es ms pesada que a,r baja y a sube2-Como r es ms pesada que c,r baja y c sube

Bubble sortvoid bubblesort(int numeros[]){int i,j;for(i=1;i

SeleccinSe selecciona el minimo valor entre los N elementos y se intercambia con el primero.Se repite la operacin con los N-1 elementos restantes.

Seleccinvoid selectionsort_up(int numeros[]){int i,j,k,r;int n;int inter;for(i=0;i

InsercinOrdena el subarreglos de manera crecienteOrdena los primeros dos elementosLuego va insertando los siguientes en su posicin ordenada en el subarreglo.

Insercinvoid insertionsort_up(int numeros[]){int i,j;int n;for(i=1;i=0)&&(n

QuicksortLos algoritmos anteriores ejecutan un numero de instruccin del orden de N2Ordenar 10 elementos ejecuta a100 instrucciones.Ordenar 100 elementos ejecuta a10000 instrucciones.Ordenar 1000 elementos ejecuta a1000000 instrucciones.

QuicksortN de elementosTiempo de ejecucinaN2

QuicksortQuicksort es un algoritmo de proposito general.Es en la mayoria de los casos el ms eficiente.Tiene un orden a N log(N)Tiene una estructura recursiva.

QuicksortN de elementosTiempo de ejecucinaNlog(N)

BsquedaConsiste en buscar un elemento dentro de un conjuntoRequiere de una relacin de igualdadNmeros: Igual valorCuntos decimales considerar?Letras: mismo smboloMayusculas y minsculas?AutosModelo y aoPlaca patenteCodigo chasisEtc

BsquedaMtodosSecuencialBinaria

Bsqueda secuencialRecorrer uno por uno los elementos.Comparar segn sea el criterio.Se puede querer recuperar el valor o ela posicin.Tiene un orden aN

Bsqueda secuencialint secuencial_search(int numeros[], int valor){

int i=0;for(i=0;i

Bsqueda secuencialEn arreglos bidimensionales el algortimo es similar.Se puede hacer por filas o por columas.Esta decision puede afectar el rendimientoPor lo general, preferir por filas.

Bsqueda secuencialint bisecuencial_search(int numeros[][N], int valor){

int i,j;for(i=0;i

Bsqueda binariaMuy rpidaRequiere datos ordenadosNo sirve para recuperar la posicin original.Encierra el numero bscado achicando a la mitad el intervalo que parece contenerlo.Tiene un orden alog2N

Bsqueda binariaint binary_search(int numeros[], int valor){int i,j,m;insertionsort_up(numeros);i=0;j=N-1;while(i