OOP Métodos de Ordenamiento

Programacin orientada a Objeto - POO

1

Programacin Orientada a Objeto

Junio 2014


2

Temario

v Algoritmos de Ordenamientov Algo de recursividad


3

Tipos de Algoritmos

Para poder ordenar una cantidad determinada de nmeros almacenadas en un vector o matriz, existen distintos mtodos (algoritmos) con distintas caracteristicas y complejidad.

Existe desde el mtodo ms simple, como el Bubblesort (o Mtodo Burbuja), que son simples iteraciones, hasta el Quicksort (Mtodo Rpido), que al estar optimizado usando recursin, su tiempo de ejecucin es menor y es ms efectivo.


4

Mtodos Iterativos

Estos mtodos son simples de entender y de programar ya que son iterativos, simples ciclos y sentencias que hacen que el vector pueda ser ordenado.

Dentro de los Algoritmos iterativos encontramos:

vBurbujav InsercinvSeleccinvShellsort


5

Mtodo de la Burbuja

El mtodo de la burbuja es uno de los mas simples, es tan fcil como comparar todos los elementos de una lista contra todos, si se cumple que uno es mayor o menor a otro, entonces los intercambia de posicin.

Por ejemplo, imaginemos que tenemos los siguientes valores:

ndice 0 1 2 3 4

valor 5 6 1 0 3


6

Mtodo de la Burbuja Simplepublic class Arreglos {

public static void Burbuja(int[] vector, int LIMITE){

int i,j;

int temp;

for (i=1; i


7

Mtodo de la Burbuja Optimizadopublic static void Bubblesort(int matriz[]){

int buffer;

int i,j;

for(i = 0; i < matriz.length; i++){

for(j = 0; j < i; j++){

if(matriz[i] < matriz[j]){

buffer = matriz[j];

matriz[j] = matriz[i];

matriz[i] = buffer;

}

}

}

}


8

Mtodos Insercin

public static void Insercion(int[] arreglo){

int aux;

for (int i = 1; i < arreglo.length; i++) {

aux = arreglo[i];

for (int j = i-1; j >=0 && arreglo[j]>aux; j--) {

arreglo[j+1]=arreglo[j];

arreglo[j]=aux;

}

}

}El bucle principal de la ordenacin por insercin va examinando sucesivamente todos los elementos de la matriz desde el segundo hasta el n-simo, e inserta cada uno en el lugar adecuado entre sus predecesores dentro de la matriz.


9

Mtodos Seleccinpublic static void Seleccion(int A[]) { int i, j, menor, pos, tmp; for (i = 0; i < A.length - 1; i++) { // tomamos como menor el primero menor = A[i]; // de los elementos que quedan por ordenar pos = i; // y guardamos su posicin for (j = i + 1; j < A.length; j++){ // buscamos en el resto if (A[j] < menor) { // del array algn elemento menor = A[j]; // menor que el actual pos = j; } } if (pos != i){ // si hay alguno menor se intercambia tmp = A[i]; A[i] = A[pos]; A[pos] = tmp; }

} }

La ordenacin por seleccin funciona seleccionando el menor elemento de la matriz y llevndolo al principio; a continuacin selecciona el siguiente menor y lo pone en la segunda posicin de la matriz y as sucesivamente.


10

Ordenamiento por Mezcla

Este algoritmo consiste bsicamente en dividir en partes iguales la lista de nmeros y luego mezclarlos comparndolos, dejndolos ordenados.

Si se piensa en este algoritmo recursivamente, podemos imaginar que dividir la lista hasta tener un elemento en cada lista, luego lo compara con el que esta a su lado y segn corresponda, lo situa donde corresponde.


11

Ordenamiento por Mezcla


12

Algo de Recursividades una tcnica de programacin que nos permite que un bloque de instrucciones se ejecute n veces. Reemplaza en ocasiones a estructuras repetitivas.

En Java los mtodos pueden llamarse a s mismos. Si dentro de un mtodo existe la llamada a s mismo decimos que el mtodo es recursivo.

Cuando un mtodo se llama a s mismo, se asigna espacio en la pila para las nuevas variables locales y parmetros.

Al volver de una llamada recursiva, se recuperan de la pila las variables locales y los parmetros antiguos y la ejecucin se reanuda en el punto de la llamada al mtodo.


13

Implementacin de un Mtodo Recursivo


14



15



16



17

Problemas tpicos Factorial n!


18

Problemas tpicos Factorial n!


19

Problemas tpicos Ordenamiento de un Vector


20

Problemas tpicos Serie de Fibonacci


21

Muchas GraciasEduardo Canales [email protected]

Slide 1Slide 2Tipos de AlgoritmosMtodos IterativosMtodo de la BurbujaMtodo de la Burbuja SimpleMtodo de la Burbuja OptimizadoMtodos InsercinMtodos SeleccinOrdenamiento por MezclaOrdenamiento por MezclaAlgo de RecursividadImplementacin de un Mtodo RecursivoImplementacin de un Mtodo RecursivoImplementacin de un Mtodo RecursivoImplementacin de un Mtodo RecursivoProblemas tpicos Factorial n!Problemas tpicos Factorial n!Problemas tpicos Ordenamiento de un VectorProblemas tpicos Serie de FibonacciSlide 21

Documents

OOP Métodos de Ordenamiento