Foros aprenderaprogramar.com
Aprender a programar => C, C++, C#, Java, Visual Basic, HTML, PHP, CSS, Javascript, Ajax, Joomla, MySql y más => Mensaje iniciado por: Mac en 28 de Agosto 2014, 05:06
-
Hola no e podido realizar el Quicksort con la temática de recursividad para implementarlo en este programa ! :-\
o Imprimir inversamente el vector. --- REALIZADO RECURIVAMANTE :)
o Sumar todos los datos posiciones impares --- REALIZADO RECURIVAMANTE :)
o Búsqueda Binaria --- REALIZADO RECURIVAMANTE :)
o Quicksort --- DIFÍCILMENTE DE REALIZAR >:( RECURIVAMANTE
Adjunto Código Completo si alguien sabe sobre como implementar el Quicksort Recursivo ! ojala me ayudara ! :(
package vector;
import java.util.Scanner;
public class LLenarVector {
public static void main(String[] Args) {
int encontrado = 0;
int noencontrado = 0;
int nummenu;
int usunum;
int menu = 0;
int tam;
int[] vector = {2, 3, 8, 0, 9, 10, 25, 6};
int dato ;
VectorPrueba miVector = new VectorPrueba(vector);
Scanner leer = new Scanner(System.in);
System.out.println("digite el tamaño del vector ");
tam = leer.nextInt();
while (menu == 0) {
System.out.println(" -- Digite 1 Para Leer y Imprimir Aleatoriamente Vector -- ");
System.out.println(" -- Digite 2 Para Buscar Un Elemento -- ");
System.out.println(" -- Digite 3 Para Imprimir Inversamente El Vector -- ");
System.out.println(" -- Digite 4 Para Sumar Todos Los Datos Posiciones Impares -- ");
System.out.println(" -- Digite 5 Búsqueda Binaria -- ");
System.out.println(" -- Digite 6 Quicksort -- ");
System.out.println(" -- Digite 7 Para Finalizar El Progrma -- ");
nummenu = leer.nextInt();
if (nummenu == 1) {
miVector.rellenar_aleatoriamente(tam);
miVector.leerVector(0, tam);
}
if (nummenu == 2) {
Scanner leerbusca = new Scanner(System.in);
System.out.println("digite un numero que quieres buscar");
usunum = leerbusca.nextInt();
miVector.busqueda_elemento(0, encontrado, usunum, noencontrado, tam);
}
if (nummenu == 3) {
miVector.imprimir_inversamente(tam);
}
if (nummenu == 4) {
System.out.println("La suma de datos en posiciones impares es " + miVector.sumaDatosPosicionesImpares(tam));
}
if (nummenu == 5) {
// ordenar ascndentemente, luego busqueda binaria
System.out.println("digite el numero a buscar en el vector por la busqueda binaria ");
dato = leer.nextInt();
miVector.organizar_ascendentemente(0, tam, 1);
miVector.escribir_vector(0, tam);
miVector.busqueda_binaria(0,tam ,tam, dato,0);
}
if (nummenu == 6) {
miVector.quicksort(vector, 0, 0);
miVector.organizar_ascendentemente(0, tam, 1);
miVector.escribir_vector(0, tam);
}
if (nummenu == 7)
{
break;
}
}
}
}
--------------------------------------------------------------------------------------------------------
package vector;
import java.util.Scanner;
public class VectorPrueba {
private int[] vector;
public VectorPrueba(int[] v) {
vector = v;
}
// usuario digita el numero
public void rellenar_aleatoriamente(int contador) {
if ((contador - 1) == 0) {
vector[0] = (int) (Math.random() * 10);
} else {
vector[contador - 1] = (int) (Math.random() * 10);
rellenar_aleatoriamente(contador - 1);
}
}
int Partition( int[] vector, int left, int right)
{
int pivot = vector[left];
while (true)
{
while (vector[left] < pivot)
left++;
while (vector[right] > pivot)
right--;
if (left < right)
{
int temp = vector[right];
vector[right] = vector[left];
vector[left] = temp;
}
else
{
return right;
}
}
}
public void quicksort( int[] vector, int left, int right )
{
// For Recusrion
if(left < right)
{
int pivot = Partition(vector, left, right);
if(pivot > 1)
quicksort (vector, left, pivot - 1);
if(pivot + 1 < right)
quicksort( vector, pivot + 1, right);
}
}
public void leerVector(int pos, int tamaño) {
if (pos == tamaño - 1) {
System.out.println(" Elemento en posición " + pos + " -- > " + vector[pos]);
}
if (pos != tamaño - 1) {
System.out.println(" Elemento en posición " + pos + " -- > " + vector[pos]);
leerVector(pos + 1, tamaño);
}
}
public void organizar_ascendentemente(int i, int tamaño, int j) {
int temp=1;
if (i<tamaño)
{
if (j<tamaño)
{
if (vector[i] >= vector[j])
{
temp = vector[i];
vector[i] = vector[j];
vector[j] = temp;
}
organizar_ascendentemente(i, tamaño, j + 1);
}
organizar_ascendentemente(i + 1, tamaño, i+2);
}
}
public void escribir_vector(int i, int tamaño) {
if (i < tamaño)
{
System.out.println(" Elemento en posición" + " "+i+ " " + vector[i]);
escribir_vector(i + 1, tamaño);
}
}
public void busqueda_binaria(int i,int z , int tamaño, int dato, int medio) { // con el punto medio teniendo en cuenta un valor digitado con el usuario
if (i < tamaño) {
medio = (i + z) / 2;// me preocupa que bote decimales nito solo el entero ... TT.TT
if (dato > vector[medio]) {
busqueda_binaria( vector[medio+1],z, tamaño, dato, medio );
}
else {
if (dato < vector[medio]) {
busqueda_binaria(i ,vector[medio-1], tamaño, dato, medio);
}
if (dato == vector[medio]) {
System.out.println(" Elemento ha sido encontrado" + " " + vector[medio]);
}
}
}
}
public void busqueda_elemento(int i, int encontrado, int usunum, int noencontrado, int tamaño) {
if (encontrado == 0 && noencontrado == 0) {
if (usunum == vector[i]) // Para cuando esta !
{
System.out.println("el numero se encuentra en la posicion " + i + " " + "en el vector y es" + " " + vector[i]);
encontrado = 1;
} else {
if (i == tamaño - 1) // Para cuando no esta !
{
System.out.println("numero no esta en el vector");
noencontrado = 1;
}
}
busqueda_elemento(i + 1, encontrado, usunum, noencontrado, tamaño);
}
}
public void imprimir_inversamente(int contador) {
if ((contador - 1) > 0) {
System.out.println(" Elemento en posición " + (contador - 1) + " -- > " + vector[contador - 1]);
imprimir_inversamente(contador - 1); //Caso recursivo
} else { //Caso base
System.out.println(" Elemento en posición " + (contador - 1) + " -- > " + vector[contador - 1]);
}
}
public int sumaDatosPosicionesImpares(int contador) {
if (contador <= 1) {
return 0;
} //Termina la recursión
if ((contador % 2) == 0) { //Elemento del vector impar
return (vector[contador - 1] + sumaDatosPosicionesImpares(contador - 2));
} else {
return sumaDatosPosicionesImpares(contador - 1);
}
}
}
-
Nadie Sabe del tema ?¡¿
-
Hola, aquí tienes un quicksort recursivo (está en C, pero no creo que tengas demasiados problemas en trasladarlo a Java): https://www.aprenderaprogramar.com/foros/index.php?topic=1170.msg6485#msg6485
-
ya yo vi ese ejemplo y no me sirvió ?¿ Otro ?¿ recursivo
-
Mira aquí llevas un ejemplo del QuickSort en java:
fichero QuickSortClass.java :
import java.util.Random;
public class QuickSortClass {
public static void quickSort(int[] vector, int izquierda, int derecha) {
int pivote = vector[izquierda];
int i = izquierda;
int j = derecha;
int auxIntercambio;
while (i < j) {
while (vector[i] <= pivote && i < j) {
i++;
}
while (vector[j] > pivote) {
j--;
}
if (i < j) {
auxIntercambio = vector[i];
vector[i] = vector[j];
vector[j] = auxIntercambio;
}
}
vector[izquierda] = vector[j];
vector[j] = pivote;
if (izquierda < j - 1) {
quickSort(vector, izquierda, j - 1);
}
if (j + 1 < derecha) {
quickSort(vector, j + 1, derecha);
}
}
public static void main(String[] arg) {
int[] numeros = new int[40];
Random rnd = new Random();
System.out.println("Vector desordenado");
for (int i = 0; i < numeros.length; i++) {
numeros[i] = rnd.nextInt(50);
System.out.print(numeros[i] + " ");
}
QuickSortClass.quickSort(numeros, 0, numeros.length - 1);
System.out.println("\nVector Ordenado");
for (int n : numeros) {
System.out.print(n + " ");
}
}
}
Una cosa eee, jeje no todo en la vida son algoritmos recursivos...
Bueno un Saludo!!
-
Y no todo en la vida es preguntar... también agradeceríamos que además de hacer preguntas respondieras de vez en cuando a personas que tienen menos conocimientos que tú... Ya se sabe, solidaridad, correspondencia, hoy tú por mí, mañana yo por tí, etc...