#1 [ALGORITMO] Algoritmo de quicksort
Programación /
[ALGORITMO] Algoritmo de quicksort
Participa en el tema [ALGORITMO] Algoritmo de quicksort en el foro Programación.
Tengo este algorito que casi me revienta el craneo de verdad ya no se que ...3
-
desconectado-
3
MENSAJES
#21 Re: Algoritmo de quicksort
Tengo este algorito que casi me revienta el craneo de verdad ya no se que hacer
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package Ordenamiento;
/**
*
* @author Clases
*/
publicclass quickSort {
//----------------------------------------------------------------------------------------
// Ordena la matriz de objetos especificada, utilizando el algoritmo
// de ordenacion rapida
//-----------------------------------------------------------------------------------------
publicvoid quicksort (T [ ] data, int min, int max)
{
int indexofpartition;
if (max - min > 0)
{
// crea las particiones
indexofpartition = findPartition(data, min, max) ;
// ordena el lado izquierdo
quickSort(data, min, indexofpartition - 1) ;
// ordena el lado derecho
quickSort(data, indexofpartition + 1, max) ;
}
}
//---------------------------------------------------------------------------------------------
// Metodo privado de localizacion de particion utilizado por el metodo
// basado en el algoritmo de ordenacion rápida.
//---------------------------------------------------------------------------------------------
privateint findPartition(T [ ] data, int min, int max)
{
int left, right;
T temp, partitionelement;
// utilizar el primer elemento como punto de particion
partitionelement = data [min];
left = min;
right = max;
while (left <right)
{
// Buscar un elemento que sea mayor que el elemento de particion
while (data[left]. compareTo(partitionelement) <= 0 && left < right)
left++;
// Buscar un elemento que sea menor que el elemento de particion
while (data[right]. compareTo(partitionelement) > 0)
right--;
// intercambiar los elementos
if (left < right)
{
temp = data[left];
data[left] = data[right];
data[right] = temp;
}
}
// mover el elemento de particion hasta el indice de particion
temp = data[min];
data[min] = data[right];
data[right] = temp;
return right;
}
}
Bueno lo que me piden es lo siguiente:
me piden que cree un programa principal donde se usen todos estos metodos usando el algoritmo planteado aca desde un paquete.
Tambien me piden que cree un arreglo tipo String y que luego lo pase a tipo objeto.
Ademas de esto me piden que los elementos del arreglo y su tamaño se generen de manera aleatoria usando el Math.random.
Plz necesito ayuda le agradecere en todo lo que me puedan ayudar
Editado por gusy2k - 16.06.2009 22:46 hs. -
-
desconectado-
83
MENSAJES
#22 Re: Algoritmo de quicksort
no recuerdo bien la sintaxis de java, pero en este caso, tendras que invocar el package desde otra clase utilizando "import Ordenamiento", luego en tu programa (main() de la clase principal) creas un objeto QuickSort y llamas al metodo quicksort() con el vector a ordenar y los otros parametros...
lo de generar los elementos aleatorios me imagino que debe ser vector[0]=Math.random();vector[1]=Math.random(); etc etc; asi por la cantidad de elementos de tu vector
en cuanto a lo del string a tipo objeto no se a que se refiere
ahora si, ponete a laburar que no es dificil...
saludos y suerte! -
-
desconectado-
1,771
MENSAJES
#23 Re: Algoritmo de quicksort
Interesante problema. El algoritmo que sigue debería andar, aunque es posible que exista otro más rápido:Originalmente publicado por Luzzzzzz
Hola!! Gracias por la suerte!
Les cuento q me puso un 9. pero no me alcanzo
vieron sobre esos concursos que dan en las olimpiadas de la oia? supongo q tienen idea de q hablo...
Bueno, la cosa es que desde hace tiempo que lo hice, y ahora de nuevo, y sigue sin salirme una cosita...
El ejercicio es el de las Banderas (lo aclaro por si alguno lo conoce), y el problema es con el punto D, que pide hallar el mayor largo de subsecuencia en comun entre varias secuencias numericas. Yo hice una lista para ver con que frecuencia se repiten, pero no llego a nada, porque siempre hay un numero nuevo q genera una subsecuencia distinta.
Lo que hay q hacer es, a partir de un numero N, con 10<=N<=500, ir sumando al numero actual, la suma de sus cifras, por ejemplo, si tengo 17, entonces el siguiente es 17+1+7=25.
Puede haber 100 secuencias distintas, por lo q la idea de comparar los vectores me daria una cantidad de comparaciones de 2^n, (siendo n la cant de secuencias), y si tengo 100 secuencias, mi programa podria nunca terminar....ja
las secuencias que encontre son:
10 - 11 - 13 - 17 - 25 - 32 - 37 - 47 - 58
14 - 19 - 29 - 40 - 44 - 52 - 59 - 73
15 - 21 - 24 - 30 - 33 - 39 - 51 - 57 - 69
16 - 23 - 28 - 38 - 49 - 62 - 70
18 - 27 - 36 - 45 - 54 - 63 - 72 - 81 - 90 - 99 - 117 - 126 (la unica con la particularidad q la suma de sus partes siempre es 9)
20 - 22 - 26 - 34 - 41 - 46 - 56
31 - 35 - 43 - 50 - 55 - 65
42 - 48 - 60
...y sigue...
con lo q siempre aparece un numero q no figura en ninguna secuencia.
Y las secuencias del problema pueden empezar en cualquier numero y ser de distinto largo, por ejemplo:
13 - 17 - 25 - 32 - 37
14 - 19 - 29 - 40 - 44 - 52 - 59
51 - 57 - 69
10 - 11 - 13 - 17 - 25 - 32
40 - 44 - 52 - 59 - 73
15 - 21 - 24 - 30 - 33
aca habria dos posibles respuestas, pero alcanza con una: decir q la maxima subsecuencia en comun es de longitud 4, entre la secuencia 2 y 5
Con lo q no tengo idea de como hacer para encontrar un algoritmo que encuentre la maxima secuencia repetida entre una infernal cantidad de secuencias.
Alguno sabe?? se le ocurre algo?? Se los agradecere mucho! tengo miedo de q eso aparezca en el final...
1) Para cada secuencia, obtener todas las subsecuencias posibles. Precederlas por su longitud y seguirlas por el identificador (puede ser un número) de la secuencia de donde se tomó.
2) Ordenar lexicográficamente todas las subsecuencias, de mayor a menor.
3) Recorrer las subsecuencias ordenadas. De las que tengan la misma longitud, verificar si son iguales exceptuando el último elemento, y si son iguales, verificar que el conjunto de todos los últimos elementos contenga todos los identificadores de las subsecuencias originales.
4) La subsecuencia correspondiente al primer conjunto encontrado de la manera anterior, exceptuando el primero y el último elemento, es la subsecuencia buscada. -
- desconectado
-
3
MENSAJES
#24 Re: Algoritmo de quicksort
Originalmente publicado por leomalevo no recuerdo bien la sintaxis de java, pero en este caso, tendras que invocar el package desde otra clase utilizando "import Ordenamiento", luego en tu programa (main() de la clase principal) creas un objeto QuickSort y llamas al metodo quicksort() con el vector a ordenar y los otros parametros...
lo de generar los elementos aleatorios me imagino que debe ser vector[0]=Math.random();vector[1]=Math.random(); etc etc; asi por la cantidad de elementos de tu vector
en cuanto a lo del string a tipo objeto no se a que se refiere
ahora si, ponete a laburar que no es dificil...
saludos y suerte!
Gracias de verdad ya no me llegaban las ideas la manera en que me plantearon el ejercicio me hizo complicarme mas de lo que debia muchsimas gracias
-
-
desconectado-
2
MENSAJES
-
- Relacionados
- Populares
- Usuarios Destacados
Estadísticas del tema
- 24 RESPUESTAS
- 8529 VISTAS
- 12 USUARIOS RESPONDIERON
Contacto | Acerca de | Ayuda | Términos Legales | privacidad | Pautas de convivencia | Mapa de los foros | TrabajÁ con nosotros
©2008 Psicofxp.com S.A. - Todos los derechos reservados
©2008 Psicofxp.com S.A. - Todos los derechos reservados
