- TIPO BURBUJA
Pasar a través del arreglo de datos varias veces en forma secuencial. Cada paso consiste en la comparación de cada elemento en el arreglo con su sucesor (x[i] con x[i+1]) y el intercambio de los dos elementos si no están en el orden correcto.
Ejemplo:
25 57 48 37 12 92 86 33
En el cual:
x[0] con x[1] (25 con 57) no intercambio.
x[1] con x[2] (57 con 48) intercambio.
x[2] con x[3] (57 con 32) intercambio.
x[3] con x[4] (57 con 12) intercambio.
x[4] con x[5] (57 con 92) no intercambio.
x[5] con x[6] (92 con 86) intercambio.
x[6] con x[7] (92 con 33) intercambio.
Quedando:
25 48 37 12 57 86 33 92
El conjunto completo de iteraciones es:
iteración 0 : 25 57 48 37 12 92 86 33
iteración 1: 25 48 37 12 57 86 33 92
iteración 2: 25 37 12 48 57 33 86 92
iteración 3: 25 12 37 48 33 57 86 92
iteración 4: 12 25 37 33 48 57 89 92
iteración 5: 12 25 33 37 48 57 89 92
ANALISIS DE PROGRAMA BURBUJA
package ordenaburbuja;
public class OrdenaAlgoritmo {//Esto es innecesario ya que es redundante con el metodo ordenamiento mejorado.
public static void ordenar( int [] arreglo) {
int pasadas = 0;
int comparaciones = 0;
for (int i = 0; i < arreglo.length; i++) {
++pasadas;
for (int j = 0; j < arreglo.length - 1; j++) {
++comparaciones;
if (arreglo[j] > arreglo[j + 1]) {
intercambiar(arreglo, j, j+1);
}
}
}
estadisticas(pasadas, comparaciones);
}
public static void ordenarMejorado( int [] arreglo) {
int pasadas = 0;
int comparaciones = 0;
boolean hayCambios = true;
for (int i = 0; hayCambios ; i++) {//Es innecesaria utilizar la variable de tipo boleano.
++pasadas;
hayCambios = false;
for (int j = 0; j < arreglo.length - 1; j++) {
++comparaciones;
if (arreglo[j] > arreglo[j + 1]) {
intercambiar(arreglo, j, j+1);
hayCambios = true;
}
}
}
estadisticas(pasadas, comparaciones);// Esta parte no se utiliza.
}
private static void intercambiar(int [] arreglo, int a, int b) {//Esta parte no se utilizaparanada.
int tmp = arreglo[a];
arreglo[a] = arreglo[b];
arreglo[b] = tmp;
}
private static void estadisticas( int pasadas, int comparaciones) {
System.out.println( "Pasadas: " + pasadas );
System.out.println( "Comparaciones: " + comparaciones );
}
}
package ordenaburbuja;
public class OrdenaBurbuja {
public static void main (String args[]) {
int [] valores = {15,35,01,05,04,03,19,45,13,02,55,8,
78,997,451,546,12,16,24,103,99,784,4541,15};
//OrdenaAlgoritmo.ordenar(valores);
OrdenaAlgoritmo.ordenarMejorado(valores);
// Mostrar arreglo.
for (int i = 0; i < valores.length ; i++)
System.out.println ( "valores["+i+"]: "+ valores[i]);
}
}
- TIPO QUICKSORT
Método más eficiente y veloz de los métodos de ordenación interna.
La idea central de este algoritmo consiste en los siguiente:
Se toma un elemento x de una posición cualquiera del arreglo.
Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.
Se toma un elemento x de una posición cualquiera del arreglo.
Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los elementos que se encuentren a su derecha sean mayores o iguales a x.
ANALISIS DE PROGRAMA QUICKSORT
package quicksort;//Nombre del paquete.
public class Ordenador {//Nombre de la clase.
public int[] quicksort(int numeros[])//Se declara sobrecargas de metodo.
{
return quicksort(numeros,0,numeros.length-1);//Se van generando las líneas impresas, el 0 no tiene ningún valor y no influye en izq.
}
public int[] quicksort(int numeros[],int izq,int der)//Se comparan el numero de la izq con los numeros de la der.
{
if(izq>=der)//Si izq es mayor igual que der….
return numeros;//Los numeros se retornan.
int i=izq,d=der;//se declaran variables de tipo int.
if(izq!=der)//Si izq es diferente de der….
{
int pivote;//declaras pivote de tipo int.
int aux; ;//declaras aux de tipo int.
pivote = izq;
while(izq!=der)//izq será diferente de der.
{
public int[] quicksort(int numeros[],int izq,int der)//Se comparan el numero de la izq con los numeros de la der.
{
if(izq>=der)//Si izq es mayor igual que der….
return numeros;//Los numeros se retornan.
int i=izq,d=der;//se declaran variables de tipo int.
if(izq!=der)//Si izq es diferente de der….
{
int pivote;//declaras pivote de tipo int.
int aux; ;//declaras aux de tipo int.
pivote = izq;
while(izq!=der)//izq será diferente de der.
{
imprimeArreglo(numeros);//se imprime la línea del arreglo.
while(numeros[der]>=numeros[pivote] && izq<der)//si los números de la derecha son mayores iguales que el numero pivote los menores serán acomodados del lado izquierdo.
der--;//La derecha se recorrerá hacia el lado izquierdo.
while(numeros[izq]<numeros[pivote] && izq<der)//los números de la izq son menores que el numero pivote; e izquierda es menor que derecha….
izq++;//Izq se recorrerá hacia el lado derecho.
der--;//La derecha se recorrerá hacia el lado izquierdo.
while(numeros[izq]<numeros[pivote] && izq<der)//los números de la izq son menores que el numero pivote; e izquierda es menor que derecha….
izq++;//Izq se recorrerá hacia el lado derecho.
if(der!=izq)//Si der es diferente que izq…
{
//Intercambiara los números en las lineas
aux = numeros[der];//Tu aux será igual a tus números de der.
numeros[der]= numeros[izq];//Los números der son iguales a números izq.
numeros[izq]=aux;}//Los números izq serán iguales a aux.
}
if(izq==der){// Se usa para comparar los números iguales.
quicksort(numeros,i,izq-1);//Se usa para comparar los números iguales.
quicksort(numeros,izq+1,d);//Se mandan al método.
}
}
else
return numeros;//Retorna la variable números.
return numeros;//Retorna la variable números.
}
aux = numeros[der];//Tu aux será igual a tus números de der.
numeros[der]= numeros[izq];//Los números der son iguales a números izq.
numeros[izq]=aux;}//Los números izq serán iguales a aux.
}
if(izq==der){// Se usa para comparar los números iguales.
quicksort(numeros,i,izq-1);//Se usa para comparar los números iguales.
quicksort(numeros,izq+1,d);//Se mandan al método.
}
}
else
return numeros;//Retorna la variable números.
return numeros;//Retorna la variable números.
}
public void imprimeArreglo(int arreglo[])
{
String imp="";//Te imprime cada renglon.
for(int i=0;i<arreglo.length;i++)
{
if(i!=arreglo.length-1)
imp=imp+arreglo[i]+",";
else
imp=imp+arreglo[i]+"";
}
System.out.println(imp);
}
public static void main(String[] args) {
int array[] ={4,2,5,7,6,1,3};//se crea el arreglo.Ordenador a = new Ordenador();//Se crea un objeto.
a.quicksort(array);//El arreglo llama a el primer quicksort.
}
System.out.println(imp);
}
public static void main(String[] args) {
int array[] ={4,2,5,7,6,1,3};//se crea el arreglo.Ordenador a = new Ordenador();//Se crea un objeto.
a.quicksort(array);//El arreglo llama a el primer quicksort.
}
}
- TIPO SHELL SORT
Ordena subgrupos de elementos separados K(incremento) unidades original.
Después de que los primeros K subgrupos han sido ordenados, se escoge un nuevo valor de K más pequeño, y el arreglo es de nuevo partido entre el nuevo conjunto de subgrupos. Cada uno de los subgrupos mayores es ordenado y el proceso se repite de nuevo con un valor más pequeño de K.
Eventualmente el valor de K llega a ser 1, de tal manera que el subgrupo consiste de todo el arreglo ya casi ordenado.
Cuando el incremento toma un valor de 1, todos los elementos pasan a formar parte del subgrupo y se aplica inserción directa.
El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego se va reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1.
BUSQUEDA SECUENCIAL
Recorre el vector desde el primer elemento hasta el último. Si se encuentra el elemento buscado se debe visualizar un mensaje similar a “Fin de Búsqueda” o “Elemento encontrado” y otro que diga “posición=” en caso contrario, visualizar un mensaje similar a “Elemento no existe en la Lista”.
Este tipo de búsqueda compara cada elemento del vector con el valor a encontrar hasta que este se consiga o se termine de leer el vector completo.
BUSQUEDA BINARIA
El método mas eficiente de búsqueda en una tabla secuencial sin utilizar índices o tablas auxiliares es la búsqueda binaria. Para poder llevarse acabo esta, necesita tener el arreglo ordenado. Básicamente, el argumento se compara con la llave del elemento intermedio de la tabla. Si son iguales, la búsqueda termina exitosamente; en caso contrario, debe buscarse en la mitad superior o inferior en la tabla en una forma similar.
EJEMPLO
* Se toma el elemento central y se divide el array en dos:
{1,2,3,4}-5-{6,7,8,9}
Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray: {1,2,3,4}
Se vuelve a dividir el array en dos:
{1}-2-{3,4}
Como el elemento buscado es mayor que el central, debe estar en el segundo subarray: {3,4}
Se vuelve a dividir en dos:
{}-3-{4}
Como el elemento buscado coincide con el central, lo hemos encontrado.
{1,2,3,4}-5-{6,7,8,9}
Como el elemento buscado (3) es menor que el central (5), debe estar en el primer subarray: {1,2,3,4}
Se vuelve a dividir el array en dos:
{1}-2-{3,4}
Como el elemento buscado es mayor que el central, debe estar en el segundo subarray: {3,4}
Se vuelve a dividir en dos:
{}-3-{4}
Como el elemento buscado coincide con el central, lo hemos encontrado.
* Si al final de la búsqueda todavía no lo hemos encontrado, y el subarray a dividir está vacío {}, el elemento no se encuentra en el array.
PROGRAMA
* public class BusquedaAlgoritmo {
* public static int buscar( int [] arreglo, int dato) {
* int inicio = 0;
* int fin = arreglo.length - 1;
* int pos;
* while (inicio <= fin) {
* pos = (inicio+fin) / 2;
* if ( arreglo[pos] == dato )
* return pos;
* else if ( arreglo[pos] < dato ) {
* inicio = pos+1;
* } else {
* fin = pos-1;
* }
* }
* return -1;
* }
* }
* class BusquedaBinaria {
* public static void main (String args[]) {
* // Llenar arreglo
* int [] edades = new int [35];
* for (int i = 0; i < edades.length ; i++)
* edades[i] = i*i ;
* // Mostrar arreglo.
* for (int i = 0; i < edades.length ; i++)
* System.out.println ( "edades["+i+"]: "+ edades[i]);
* int resultado = BusquedaAlgoritmo.buscar(edades, 9);
* if (resultado != -1) {
* System.out.println ( "Encontrado en: "+ resultado);
* } else {
* System.out.println ( "El dato no se encuentra en el arreglo, o el arreglo no estA ordenado." );
* }
* }
* }
HASH
Una función de hash es una función para resumir o identificar probabilísticamente un gran conjunto de información, dando como resultado un conjunto imagen finito generalmente menor (un subconjunto de los números naturales por ejemplo). Varían en los conjuntos de partida y de llegada y en cómo afectan a la salida similitudes o patrones de la entrada. Una propiedad fundamental del hashing es que si dos resultados de una misma función son diferentes, entonces las dos entradas que generaron dichos resultados también lo son.
Las tablas hash, una de las aplicaciones más extendidas de las funciones de hash, aceleran el proceso de búsqueda de un registro de información según una clave (nota: este uso de la palabra poco se relaciona con su significado habitual). Por ejemplo, una cadena alfanumérica puede ser utilizada para buscar la información de un empleado en la base de datos de un sistema.
La utilización de tablas hash provee un acceso casi directo a dichos registros, lo que significa que, en promedio, una búsqueda puede llegar a requerir sólo uno o dos intentos en la memoria o el archivo que contiene la información. Naturalmente, se prefiere una buena función de hash que evitará colisiones de hash.
