Exposiciones

METODOS DE ORDENAMIENTO

 
1. Metodo 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.

Historia:
 
1956 se encuentra expresado en un articulo al que lo llamaron “ordenamiento por intercambio”.
Ventajas:
•Bastante sencillo y mas utilizado por su fácil comprensión y programación
•Código reducido
•Eficaz.

Desventajas:
•Consume bastante tiempo calculo computarizado.
•Requiere de muchas lecturas/escrituras en memoria 



Funcionamiento:

Se le denomina ordenacion por burbuja debido a que los valores mas grandes burbujean a la parte superior de modo similar como suben las burbujas en el agua. 

Tambien es conocido como el metodo del intercambio directo. Dado que solo usa comparaciones para operar elementos, se le considera un algoritmo de comparación, siendo el mas sencillo de implementar.


Codigo en Java  Del Metodo Burbuja:

public class Burbuja {
static int [] vec = {312, 614, 88, 22, 54};
void ordenar (int [] v, int cant) {
if (cant > 1) {
for (int f = 0 ; f < cant - 1 ; f++)//
if (v [f] > v [f + 1]) {
int aux = v [f];
v [f] = v [f + 1];
v [f + 1] = aux;
}
ordenar (v, cant - 1);
}
}
void imprimir () {
for (int f = 0 ; f < vec.length ; f++)
System.out.print (vec [f] + " ");
System.out.println("\n"); }
public static void main (String [] ar) {
Recursivdad r = new Burbuja();
r.imprimir ();
r.ordenar (vec, vec.length);
r.imprimir ();
}
}

 

 

2. Metodo Quick Sort

Es un algoritmo creado por el científico británico en computación C.A.R. Hoare basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

La descripción del algoritmo para el método de ordenamiento quicksort es la siguiente:

• Debe elegir uno de los elementos del arreglo al que llamaremos pivote.
• Debe acomodar los elementos del arreglo a cada lado del pivote, de manera que del lado izquierdo queden todos los menores al pivote y del lado derecho los mayores al pivote; considere que en este momento, el pivote ocupa exactamente el lugar que le corresponderá en el arreglo ordenado.
• Colocado el pivote en su lugar, el arreglo queda separado en dos subarreglos, uno formado por los elementos del lado izquierdo del pivote, y otro por los elementos del lado derecho del pivote.
• Repetir este proceso de forma recursiva para cada subarreglo mientras éstos contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados.

Para elegir un pivote se puede aplicar cualquiera de las siguientes tres opciones:

• El pivote será el primer elemento del arreglo,
• El pivote será el elemento que esta a la mitad del arreglo, o
• Que el pivote se elija de entre tres elementos del arreglo (cualesquiera), los cuales se deben comparar  para seleccionar el valor intermedio de los tres y considerarlo como el pivote.

Codigo En Java Del Metodo Quick Sort:

package javaapplication12

public class quicksort {
public static void main(String a[]){
int i;
int array[] = {12,9,4,99,120,1,3,10,13};
System.out.println(" Quick Sort\n");
System.out.println("Valores antes de QuickSort:\n");
for(i = 0; i < array.length; i++)
System.out.print( array[i]+" "); System.out.println();
quick_srt(array,0,array.length-1);
System.out.print("\n\n\nValores despues de QuickSort:\n\n");
for(i = 0; i <array.length; i++)
System.out.print(array[i]+" ");
System.out.println();
}
public static void quick_srt(int array[],int low, int n){
int lo = low;
int hi = n;
if (lo >= n) {
return;
}
int mid = array[(lo + hi) / 2];
while (lo < hi) {
while (lo<hi && array[lo] < mid) {
lo++;
}
while (lo<hi && array[hi] > mid) {
hi--;
}
if (lo < hi) {
int T = array[lo];
array[lo] = array[hi];
array[hi] = T;
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
quick_srt(array, low, lo);
quick_srt(array, lo == low ? lo+1 : lo, n);
}
}

3. Metodo Shell Sort

Se denomina “SHELL” en honor a su inventor Donald Shell .

Es un algoritmo de ordenación interna muy sencillo pero muy ingenioso, basado en comparaciones e intercambios, y con unos resultados radicalmente mejores que los que se pueden obtener con el método de la burbuja, el de selección directa o el de inserción directa.

Ventajas:

• No requiere memoria adicional.
• Mejor rendimiento que el método de inserción rápido.
• Fácil implementación,

Desventajas: 

• Su funcionamiento puede resultar confuso.
• Suele ser un poco lento. 
• Realiza numerosas comparaciones e intercambios

 Pasos  Para El Ordenamiento:

1. Dividir la lista de elementos (n) entre dos: n/2 
2. Clarificar cada grupo por separado, comparando las parejas de elementos y si no están ordenados se intercambian 
3. Se divide ahora la lista a la mitad: n/4 y nuevamente se clasifica cada grupo por separado.  
4. El algoritmo termina cuando el tamaño del salto es igual a 1

 Codigo En Java Del  Metodo Shell Sort:

/**
* @author Alumno ITCJ-TIC'S
*/
public class shell_sort { public static void shellSort( int b[ ])
{
for(int k= b.length/2; k>0; k=k==2?1:(int)( k/2.2))
{
for(int i=k;i<b.length; i++ )
{
int tmp =b[i];
int j;
for(j=i; j>=k&&tmp<b[j-k]; j-=k)
{
b[j]=b[j-k];
}
b[j]=tmp;
}
}
}
public static void main(String args[]){
int a[]={321, 6, 1, 234, 213, 4, 5, 123}; //Este es el array de elementos que vamos a ordenar
System.out.println("Antes del ordenamiento");
for(int i=0;i<a.length;i++)
{
System.out.print(a[i]+" ");

shellSort(a); //llamada al metodo shellSort
System.out.println("\n");
System.out.println("Ordenado por el método Shell");
for (int i=0;i < a.length;i++){ //Este bucle imprime el contenido del array
System.out.print(a[i]+" ");
}//fin del for
}//fin del main
}//class ShellSort

METODOS DE BUSQUEDA 

1. Metodo Busqueda Secuencial

Pasos para realizar la busqueda secuencial:

1.Consiste en recorrer el arreglo elemento a elemento e ir comparando con el valor buscado.  

2.Se empieza con la primera casilla del arreglo y se observa una casilla tras otra hasta que se encuentra el elemento buscado o se han visto todas las casillas.

3.El resultado de la búsqueda es un solo valor, y será la posición del elemento buscado o cero.

4.El método de búsqueda lineal funciona bien con arreglos pequeños o para arreglos no ordenados. 

Codigo En  Java  De  La Busqueda Secuencial

public class secuencialdesordenado {

public void buscar()

{ 

Scanner leer=new Scanner(System.in);
int i=0;
boolean bandera=false;
int x;
int v[]= new int[10];
for(int c=0;c<v.length;c++)
{
System.out.println("introduce los datos del arreglo");
v[c]=leer.nextInt();
}
System.out.println("introduzca elemento a buscar");
x=leer.nextInt();
do{
if(v[i]==x)
{
bandera=true;
}
else {
bandera=false;
}
i++;
}while(i<v.length && bandera==false);

if(bandera==true)
{
System.out.println("el elemento esta en la posicion "+ i);
}
else if(bandera==false)
{
System.out.println("el elemento no esta en la lista");
}
}

2.  Metodo Busqueda Binaria

Es un método que se basa en la división sucesiva del espacio ocupado por el vector en sucesivas mitades, hasta encontrar el elemento buscado

Ventaja:

La búsqueda binaria es un método eficiente siempre que el vector esté ordenado.

Desventaja:

Si los datos del arreglo no están ordenados no hará la búsqueda, y se necesitaria usar un metodo de ordenamiento.

Codigo en Java  De Busqueda Binaria

 

public class BusquedaBinaria
{ public static int busquedaBinaria(int[] Arreglo, int elemento)
{
int i = 0, centro = 0, posicion = 0, inferior = 0, superior = Arreglo.length-1; while(inferior <= superior)
{
centro = (superior + inferior) / 2; if (Arreglo[centro] == elemento)
{
return centro;} else{ if (Arreglo[centro] > elemento)
{ superior = centro - 1;
}
else
{
inferior = centro + 1;
}
}
}
return -1;
}
public static void main (String[] args)
{
java.util.Scanner Leer = new java.util.Scanner(System.in);
System.out.print("Tamanio del arreglo:");
int tamanioArreglo = Leer.nextInt();
int[] Arreglo = new int[tamanioArreglo];
for(int i=0; i<Arreglo.length; i++)
{
System.out.println("Introduce elemento:"); Arreglo[i] = Leer.nextInt();
}
int A;
for(int i=0;i<Arreglo.length-1;i++)
{
for(int j=0;j<Arreglo.length-i-1;j++)
{
if(Arreglo[j+1]<Arreglo[j])
{
A=Arreglo[j+1];
Arreglo[j+1]=Arreglo[j];
Arreglo[j]=A;
}
}
} System.out.print("Elemento a buscar:" );
int elemento = Leer.nextInt();
System.out.println("dato");
for(int i=0;i<Arreglo.length;i++){
System.out.println(Arreglo[i]);
}
int posicion = busquedaBinaria(Arreglo, elemento);
if(posicion == -1) System.out.println("\nElemento no encontrado");
else
System.out.println("\nElemento " + elemento + " encontrado en la posicion " + posicion);
}
} 

    

}