ORDENAMIENTO QUICK SORT
jueves, 23 de septiembre de 2010
miércoles, 8 de septiembre de 2010
Busqueda y Ordenamiento.
BUSQUEDAS
Búsqueda Lineal
La búsqueda lineal consiste en recorrer los elementos de búsqueda de principio hasta el final hasta encontrar la palabra a buscar.
Se pide: Codificar el método search que realiza la búsqueda lineal.
/*
* LinealSearch.java
*
* Created on 27 de marzo de 2003, 10:10
*/
/**
* Realiza la búsqueda lineal entre unas palabras cuyos valores se leen
* por entrada estándar (el teclado).
*/
import java.io.*;
import java.util.StringTokenizer;
public class LinealSearch extends Search {
/** Crea una nueva instancia de LinealSearch */
public LinealSearch(String linea) {
super(linea);
} //Constructor
/*
* Devuelve la posicion(+1) del array de elementos ordenados
* donde se encuentra la palabra pasada por argumento.
* Si no lo encuentra, devuelve -1
*/
public int search(String palabra) {
// Escribir código
//...
return -1;
}
/*
* main de prueba:
* Lee una línea de palabras (ordenadas o no) que se ordenarán dentro del constructor.
* Busca dentro de él la palabra que se pasa en la siguiente línea.
*/
public static void main(String [] args) {
String linea, palabra;
BufferedReader lector= new BufferedReader(new InputStreamReader(System.in));
try {
System.out.print("Palabras donde buscar: ");
if(((linea= lector.readLine())!=null)&&(!linea.equals(""))) {
System.out.print("Palabras (ordenadas) donde buscar: ");
LinealSearch linealSearch= new LinealSearch(linea);
System.out.println(linealSearch.toString());
System.out.print("Palabra a buscar: ");
if (((palabra= lector.readLine())!=null)&&(!palabra.equals(""))) {
int posicion=linealSearch.search(palabra);
if (posicion!=-1) {
System.out.println("Palabra encontrada en la posición "+posicion);
}
else {
System.out.println("Palabra " + palabra +" NO encontrada");
System.out.println("Reescriba la palabra: ");
}
} //if palabra
} //if linea
}
catch(Exception e) {
System.err.println(e);
}
}
}
BÚSQUEDA BINARIA
Uno de los algoritmos de búsqueda más eficiente que existe en la estructura de datos es la búsqueda binaria, las características para poder implementar este algoritmo son las siguientes:
Los datos deben estar contenido en un estructura de datos tipo vector
Los datos del vector deben estar ordenados
Una vez que se cuenten son las características descritas, se divide el vector para poder conocer la posición central y se verifica si es el dato que se esta buscando (lineas 9-12), si es el dato que se busca regresa la posición (índice del vector), en caso de que no sea el dato que buscamos se verifica si es mayor o menor que la posición central y se vuelve a redefinir la posición final o inicial según cumpla la condición (lineas 14-18).
Debido a que el vector se encuentra ordenado si el dato que buscamos es mayor a la posición central se descartan todos los datos que se encuentren en la parte inferior, de la misma manera si el dato que buscamos en menor que la posición central definida se descarta la parte superior del vector.
Una vez que encuentre el dato el método regresara la posición en que lo encontró (linea 12), en caso de no encontrar el dato en el vector regresara el valor -1
La implementación de este ejemplo del algoritmo de búsqueda binaria se encuentra en el lenguaje de programación Java.
ORDENAMIENTOS
ORDENAMIENTO DE BURBUJA
El primer ordenamiento que presentamos es quizá el más ampliamente conocido entre los estudiantes que se inician en la programación. Una de las características de este ordenamiento es que es fácil de entender y programar. Aunque, es uno de los algoritmos mas ineficiente.
La idea básica subyacente en el ordenamiento de burbuja es 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. Considérese el siguiente arreglo de datos:
25 57 48 37 12 92 86 33
En el primer paso se realizan las siguientes operaciones:
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.
Así después del primer paso, el arreglo está en el siguiente orden:
25 48 37 12 57 86 33 92
Obsérvese que después del primer paso, el elemento mayor (en este caso 92) está en la posición correcta dentro del arreglo. En general x[n-i] estará en su posición correcta después de la iteración i. El método se lama ordenamiento de burbuja porque cada número “burbujea” con lentitud hacia su posición correcta. 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
La implementación de este algoritmo en Java queda como:
void Burbuja(int x[], int n)
{
int b, j, t;
do
{
b = 0;
for(j=0; j
{
if(x[j] > x[j+1])
{
t = x[j];
x[j] = x[j+1];
x[j+1] = t;
b++;
}
}
n--;
}
while(b > 0);
}
ORDENAMIENTO QUICK SORT
El ordenamiento de QuickSort (Ordenamiento Rápido) es un algoritmo del tipo divide y venceraz, es el más rápido de todos los algoritmos para ordenar y además es recursivo.
Código de ejemplo:
public void quicksort(int[] vector, int primero, int ultimo) {
int i = primero, j = ultimo;
int pivote = vector[(primero + ultimo) / 2];
int auxiliar;
do {
while (vector[i] < pivote) {
i++;
}
while (vector[j] > pivote) {
j--;
}
if (i <= j) {
auxiliar = vector[i];
vector[i] = vector[j];
vector[j] = auxiliar;
i++;
j--;
}
} while (i <= j);
if (primero < j) {
quicksort(vector, primero, j);
}
if (ultimo > i) {
quicksort(vector, i, ultimo);
}
}
Como ven le estamos enviando un arreglo de enteros (Pero prodria ser un objeto propio o dado caso un arreglo de char, String, etc) como saben cuando se envia un objeto bajo parametro se modifica la referencia en memoria entonces el objeto siempre será el mismo.
ORDENAMIENTO DE ARREGLOS
El siguiente ejercicio permite apreciar la importancia de descomponer los problemas complejos en subproblemas más simples de resolver. La clase Sorter sirve para ordenar arreglos de números reales.
La clase Sorter se usa de la siguiente manera. Suponga que Ud. ha construido su arreglo mediante la declaración:
double[] array= { 5.0, 10.0, -4.0, 15.0, 13.0, 46.0, -2.0};
Para ordenar arreglo se crea un objeto de la clase Sorter pasando como argumento el arreglo:
Sorter sorter= new Sorter(array);
El objeto construido es un ordenador de arreglos de números reales. En este punto, el objeto sorter y la variable array referencian el mismo arreglo. La construcción de sorter no ordena todavía el arreglo. De hecho, el objeto posee métodos para desplegar el contenido del arreglo en pantalla:
sorter.print();
El resultado de esta invocación será:
5.0 10.0 -4.0 15.0 13.0 46.0 -2.0
Para ordenar el arreglo se invoca el método sort:
sorter.sort();
Después de esta llamada el arreglo referenciado por array se encuentra ordenado. Si ahora se invoca sorter.print(), el resultado estará ordenado:
-4.0 -2.0 5.0 10.0 13.0 15.0 46.0
Ejercicios For,While,Do While,
Pares e Impares con For
Pares e Impares con While
Pares e Impares con Do while
Tablas de Multiplicar con For
Tablas de Multiplicar con While
Suscribirse a:
Entradas (Atom)