SoloCodigo
Programación General => C/C++ => Mensaje iniciado por: pyro en Martes 8 de Junio de 2004, 07:35
-
:( Hola, yo entiendo el algoritmo de este ordenamiento... y lo he analizado.. pero no estoy pudiendo implementarlo para poder utilizarlo con una matriz de orden n*m...
Este seria el quicksort para un vector unidimensional.. como puedo hacer para implementarlo a un vector con mas dimesiones??
por ejemplo
sea mi matriz [1,2,3]
[4,5,6]
[7,8,9]
y ordenarlo por filas.. y por columnas en forma ascendente o descendiente.. como puedo hacerlo? sin que pase estos datos a un vector.. y luego paso el vector a la matriz de nuevo..
:unsure:
void qsort(int m, int n, int v[])
{
int i, j, k,t ;
static int nivel=0;
if (m<n)
{
i = m;
j = n+1;
k = v[m];
while(1)
{
do {i++;}while (v<k);
do {j--;}while (v[j]>k);
if (i<j)
{
t=v;
v=v[j];
v[j]=t;
}
else
break;
}
t=v[j];
v[j]=v[m];
v[m]=t; nivel++;
qsort(m,j-1,v);
qsort(j+1,n,v);
}
}
-
eso depende de lo que quieras hacer.. trata de ser ma claro..
es decir si lo que quieres-?
- ordenar cada fila de la matrix por aparte
- ordenar toda la matriz como si fuera un unico vector
- ordenar horizontalmente y luego verticalmente conn un criterio determinado
- otras?
-
En realidad ordenar toda la matriz..
por ejemplo si tengo
[2,8,5]
[9,1,6]
[10,15,4]
Ordenarlo por filas seria
[1,2,4]
[5,6,8]
[9,10,15]
y por columnas
[1,5,9]
[2,6,10]
[4,8,15]
seria algo asi.. no se me ocurre como hacerlo.. :blink:
-
solo necesiats copiarla matriz en un vector segun tus necesidads , lo rodenas y luego lo devuelves a la matriz y listo.
-
Otra forma de solucionar el problema :
tenemos una matriz int a[N][N]
[a] - para ordenar por filas creamos una funcion que ordena un array de int de dimension N*N
void SortByRows(int *a)
{
ordenar el array N*N por el metodo requerido
}
llamada a la funcion SortByRows(&a[0][0]);
- ordenar por columnas es un poco mas complicado, pero podemos aprovechar
el resultado anterior y construir la matriz transpuesta del ordenamiento por filas.
SortByColumns = transpuesta de a[N][N]
for(int i = 0;i < N;i++)
for(int j = 0;j < i;j++)
intercambiar los valores de a[j] y a[j]);
exito ! ! !
Nota : una matriz b es transpuesta de otra matriz a, si todas la columnas de a son
filas de b y todas las filas de a son columnas de b.
Por supuesto si b = transp(a), tambien a = transp(B).
-
Hola Gracias JuanK y Noel, mi problema no estaba en hallar la transpuesta sino mas bien.. en como puedo transformar el quicksort de modo a que se adapte para vectores no bidimensionales... pero igual.. muchas gracias por su ayuda..
-
Estimado Pyro : que es lo que quieres ?
Has recibido respuestas de acuerdo a tus preguntas y al ejemplo de input-output
que presentates, y te aseguro que el procedimiento con la "transpuesta" hace exactamente lo que escribistes.
Empezemos de nuevo :
[a] : di exactamente que quieres hacer, cual es tu input y cual es tu output.
: presenta un ejemplo claro y detallado.
No tartes de volvernos locos, que ya lo somos por merito propio.
-
Hola yo de nuevo :unsure:
Mmm a ver si esta vez me explico mejor....
Quiero implementar el quicksort para matrices de elementos FILAS*COLUMNAS... ordenando primero por columnas y luego por filas...
Orden por columnas... m[0][0], m[1][0], m[2][0]........ m[0][1], m[1][1]... y asi... siguiendo... por ejemplo
[10][24][14]
[18][11][ 9]
[ 8][20][34]
y si lo ordeno por columnas...
[ 8][11][20]
[ 9][14][24]
[10][18][34]... y luego hago la transpuesta y tengo la matriz ordenada por filas...
ahora bien... no tengo la menor idea de como implementar el quicksort.. sin tirar fila por fila o colmna por columna a un vector.... :(
-
Me parece que el ultimo tejemplo que enviastes rengea un poco.
Te mando una propuesta, que me creo adecuada a lo que necesitas.
Fijate que cuando ordenas la misma matriz dos veces, una vez segun las lineas y la otra de acuerdo a las columnas, obtienes una matriz que esta ordenada como si en realidad fuera un array lineal.
Yo no use Qsort, pero no es un gran problema hacer el cambio.
-
Creo que mi idea no esta llegando muy bien.. tu programa esta bien.. solo que el ordenamiento debe de ser con todos los elementos...
por ejemplo tu matriz es:
{2,8,5}
{9,1,6}
{10,15,4}
y el ordenamiento por filas serias...
{1,2,4}
{5,6,8}
{9,10,15}...
y el orden por columnas..
{1,5,9}
{2,6,10}
{4,8,15}... no se si me estoy explicando bien :(
El ordenamiento debe ser de todos los elementos.. como si fuese un vector unidimensional.. pero sin tomarlo como tal... me explico :(
-
Me llevo tiempo, pero creo hacer entendido lo que quieres.
Tienes que cambiar a ordenamiento Qsort.
Cuentame como te fue.
-
Hola estuve biendo el codigo.. y probando paso a paso.. y sip es lo que estaba queirendo hacer, ahora... creo que para pasarlo a qsort es casi lo mismo, solo unos pequeños cambios para ver los limites de ordenacion.. o me estoy equivocando? :( voy a seguir con el codigo este fin de semana y luego te lo paso
-
Creo que ya esta.. muchas gracias a todos por su ayuda... :) gracias