Burbuja
La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es necesario revisar varias veces toda la lista hasta que no se necesiten más intercambios, lo cual significa que la lista está ordenada. Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas".
PROGRAMAS
PROGRAMA1
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]);
}
}
Programa2
class OrdenaAlgoritmo {
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++) {
++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);
}
private static void intercambiar(int [] arreglo, int a, int b) {
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 );
}
}
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]);
}
}
videos
TIPO QUICKSORT
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.
Pivote: Es un numero del arreglo que tomaremos como referencia para reorganizar el arreglo de numeros y ordenarlo. En pocas palabras tomamos todos los numeros mayores que el que hayamos elegido como pivote y los colocamos a la derecha del mismo, y todos los que sean menores que este los colocamos del lado izquierdo.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.
Punteros izquierdo y derecho:
El quicksort utiliza 2 punteros como referencia, uno izquierdo y uno derecho, normalmente cuando se ordena de menor a mayor el izquierdo simboliza el lado de números menores y el derecho los números mayores. A medida que analizamos el arreglo, los punteros se acercan el uno a otro y cuando se encuentran en una ubicación se coloca en esta el pivote y se separa el arreglo en 2 arreglos mas pequeños. Posteriormente se vuelve a aplicar el algoritmo a los arreglos mas pequeños hasta que se logre ordenar la secuencia tal y como se ha visto en el vídeo anterior.
PROGRAMA 1
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.
}
VIDEOS
TIPO SHELL SORT
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:
- El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
- El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.
El algoritmo Shell sort mejora el ordenamiento por inserción comparando elementos separados por un espacio de varias posiciones. Esto permite que un elemento haga "pasos más grandes" hacia su posición esperada. Los pasos múltiples sobre los datos se hacen con tamaños de espacio cada vez más pequeños. El último paso del Shell sort es un simple ordenamiento por inserción, pero para entonces, ya está garantizado que los datos del vector están casi ordenados.
PROGRAMA
package equipo;
public class ShellSort
{
private long[] data;
private int len;
public ShellSort(int max) {
data = new long[max];
len = 0;
}
public void insert(long value)
{
data[len] = value;
len++;
}
public void display()
{
System.out.print("Datos:");
for (int j = 0; j < len; j++)
System.out.print(data[j] + " ");
System.out.println("");
}
public void shellSort()
{
int inner, outer;
long temp;
//find initial value of h
int h = 1;
while (h <= len / 3)
h = h * 3 + 1; // (1, 4, 13, 40, 121, ...)
while (h > 0) // decreasing h, until h=1
{
// h-sort the file
for (outer = h; outer < len; outer++)
{
temp = data[outer];
inner = outer;
// one subpass (eg 0, 4, 8)
while (inner > h - 1 && data[inner - h] >= temp)
{
data[inner] = data[inner - h];
inner -= h;
}
data[inner] = temp;
}
h = (h - 1) / 3; // decrease h
}
}
public static void main(String[] args)
{
int maxSize = 10;
ShellSort arr = new ShellSort(maxSize);
for (int j = 0; j < maxSize; j++)
{
long n = (int) (java.lang.Math.random() * 99);
arr.insert(n);
}
System.out.println("Datos no Ordenados");
arr.display();
arr.shellSort();
arr.display();
}
}
VIDEOS
BUSQUEDAS
BINARIA
La búsqueda binaria consiste en dividir el array por su elemento medio en dos subarrays más pequeños, y comparar el elemento con el del centro. Si coinciden, la búsqueda se termina. Si el elemento es menor, debe estar (si está) en el primer subarray, y si es mayor está en el segundo. Por ejemplo, para buscar el elemento 3 en el array {1,2,3,4,5,6,7,8,9} se realizarían los siguientes pasos:
· 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.
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." );
}
}
}
VIDEOS
SECUENCIAL
Este método se usa para buscar un elemento de un vector, es explorar secuencialmente el vector, es decir; recorrer el vector desde el prior 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.
PROGRAMA
["aarona","aashta","abelarda","abelia","abigail","a bril"] , todos de
tipo String y queremos saber si ya existe el nombre : "Abigail" en nuestro vector entonces tenemos que hacer lo siguiente:
public class BSecuencial {
public static void main(String[] args)throws IOException {
BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
int encontrados=0;
String [] VectorNombres = {"Aarona","Aashta","Abelarda","Abelia","Abigail ",
"Abril"};
System.out.print("Digite el nombre que desea buscar: ");
String nombre = entrada.readLine();
// entrada de dato a buscar
for (int i=0; i<VectorNombres.length;i++){
if(nombre.equalsIgnoreCase(VectorNombres[i])){
JOptionPane.showMessageDialog(null,"Elemento encontrado "+VectorNombres[i],"Encontrado",
JOptionPane.INFORMATION_MESSAGE);
encontrados++;
continue;
}
}
if(encontrados == 1 ){
System.out.println("Fin de busqueda, encontrado "+encontrados+" elemento igual");
}else{
System.out.println("Fin de busqueda, encontrados "+encontrados+" elementos iguales");
}
}
}
tipo String y queremos saber si ya existe el nombre : "Abigail" en nuestro vector entonces tenemos que hacer lo siguiente:
public class BSecuencial {
public static void main(String[] args)throws IOException {
BufferedReader entrada = new BufferedReader (new InputStreamReader(System.in));
int encontrados=0;
String [] VectorNombres = {"Aarona","Aashta","Abelarda","Abelia","Abigail ",
"Abril"};
System.out.print("Digite el nombre que desea buscar: ");
String nombre = entrada.readLine();
// entrada de dato a buscar
for (int i=0; i<VectorNombres.length;i++){
if(nombre.equalsIgnoreCase(VectorNombres[i])){
JOptionPane.showMessageDialog(null,"Elemento encontrado "+VectorNombres[i],"Encontrado",
JOptionPane.INFORMATION_MESSAGE);
encontrados++;
continue;
}
}
if(encontrados == 1 ){
System.out.println("Fin de busqueda, encontrado "+encontrados+" elemento igual");
}else{
System.out.println("Fin de busqueda, encontrados "+encontrados+" elementos iguales");
}
}
}
VIDEOS
TIPO HASH
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.
No hay comentarios:
Publicar un comentario