Para evitar confusiones, es un ejercicio de la guía "complementaria" de 83 ejercicios:

32) Dado un archivo de alumnos inscriptos para cursar por año completo (desordenado) donde cada registro contiene:
a) Nro. de legajo (5 digitos)
b) Especialidad (1 a 10)
c) Turno ('M', 'T' ó 'N')
d) División (1 a 100)
Desarrollar el programa que genere otro archivo con la misma cantidad de registros pero ordenado por especialidad, turno y division.
Nota: no hay mas de 100 alumnos por cada división y se disponen de 550kb de memoria.


Comentario:
En ejercicios anteriores acostumbraba hacer búsqueda binaria, y meter en un array la posición del legajo en el archivo (siendo la posición del array el legajo). Sin embargo, acá me confundo cuando hay que ordenar por tres, y no se me ocurre una estrategia para hacer con arrays.

Espero puedan ayudarme (preferentemente armenlo en Visio, aunque me da igual como lo expliquen mientras lo pueda entender), ¡gracias!

mira, con 550 kb te haces alto guiso (?)

legajo: 5 digitos ponele longword -> 4 bytes
especialidad: 1 digito, byte -> 1 byte
turno: un char (o como dicen los eruditos locos, un int, en fin, tamos todos locos) -> 1 byte
division: 1 a 100, byte -> 1 byte

total= 7 bytes
sumale un puntero
total =11 bytes

supongamos caso maximo: 100 alumnos en las 100 divisiones:
100*100 = 10000
10000 * 11 bytes = 110000 bytes = 107.42 kb

y te dan 550 kb

si multiplicas eso por 5 te da 537.109 kb (te sobra). Podes hacer 5 listas iguales.

A lo que voy, es que te recontra regalan espacio. Ahora, con todo ese espacio, no vas a hacer 5 listas.

Lo que podes hacer es esto:

1) Haces un array de registros cuyo indice es la especialidad(1 a 10) y su unico campo es un puntero a una lista de turnos
sumario de memoria hasta ahora: 10 filas * 1 columna de 4 bytes = 40 bytes ;
cada puntero apunta a una lista con 3 nodos (mañana, tarde, noche) eso es (1 byte + 4 bytes del puntero) * 3 (cantidad de nodos) = 15 bytes;
esos 15 bytes van a estar para las 10 filas, asi que 15 bytes * 10 filas= 150 bytes
Entonces hasta ahora tenemos: 40 bytes + 150 bytes = 190 bytes

2) Insertar los alumnos en la especialidad que corresponda, turno que corresponda, ordenado por especialidad
Si tomamos caso maximo de alumnos, como puse antes seria: 100 alumnos en las 100 divisiones: 100*100 = 10000 bytes; 10000 * 11 bytes = 110000 bytes = 107.42 kb


A eso le sumamos los 190 bytes de lo demas: 190 bytes + 107.42 kb < 550 kb

Te dan 550 kb. RECONTRA OPTIMO.

Capaz hay otra forma mas optima, npi (ni puta idea)


Para armar el archivo, recorres cada fila del array, clavas por turno todos los alumnos. Bueno, se entiende por donde va la idea ?

edit: sume mal los bytes al final

Off-topic:

Me aguantás hasta esta noche y te respondo? Mí estar en el laburou y se me complica

Ah, y te lo escanearía, pero mi cuaderno lo tiene Rulo. Pero llego a casa y te digo qué opino del ejercicio

bleh, hice las cosas rapido y me falto aclarar:
cada nodo de turno tiene un puntero a una lista con los alumnos, ordenado por division.

te sigue sobrando memoria

(31-05-2012 11:01)el pibe escribió:  bleh, hice las cosas rapido y me falto aclarar:
cada nodo de turno tiene un puntero a una lista con los alumnos, ordenado por division.

te sigue sobrando memoria

No me hables de nodos ni punteros que recién lo estoy viendo. Me basta con tocarlo entre archivos y registros solamente, o como mucho con arrays .


Leí lo primero y con lo de punterios medio que me mataste, así que improvisaré algo hasta tanto (o sea, voy a tratar de descifrar tu "estrategia" y ver que puedo sacar. Le mando un "gracias" igual por la intención .

(31-05-2012 10:06)nanuiit escribió:  Pero llego a casa y te digo qué opino del ejercicio

Leí muy por arriba porque estoy con diez mil cosas, pero si podés usar un array como para ordenar ahí mientras vas leyendo, podés hacer un InsertaOrdenadoArray por más de un criterio
Eso es válido y aplica a la época de la cursada en la que estás

---

Ese ejercicio cuando habla de memoria, es memoria estática.. creo que la parte de dinámica es por arriba del ejercicio 50.

Volviendo, si tuviera el cuaderno, ahí tenía la resolución más óptima.

Me acuerdo que era un ejercicio super fulero.
De muy buenas y primeras, y no es la solución más feliz, yo grabaría en el array las posibles combinaciones entre especialidad, turno y división. Total, sabés que como máximo hay 100 divisiones

Entonces tendrías (1 byte de especialidad + 1 byte de turno + 1 byte de división) * 100 = 300 bytes
Leeria en el archivo, me fijaria si los datos de estas tres cosas coinciden con las del array; de no ser así grabo una nueva combinación en el vector

Una vez que hago eso puedo reordenar el array (burbujeo), o antes podría haberlo insertado ordenado.

Después tomo el vector, que como está ordenado lo uso para ir buscando en el archivo y entonces voy haciendo eso mientras grabo en el archivo nuevo.

No es de lo más feliz...


Creo que la otra solución era usar el array para grabar por curso.. y cada vez que leías todo el curso, vaciabas el array, que tampoco me convence

Te agrego otra posibilidad, usando segmentación.

Es muy parecido a lo que decía nanuiit, pero sin ordenar.

utilizo un array compuesto por:
(1 byte de especialidad + 1 byte de turno + 1 byte de división + 4 bytes de legajo) * 3000 = 21000 bytes < 20 kb

El 3000 es por la combinación de ocurrencias :
10 especialidades * 3 turnos * 100 divisiones = 3000 ocurrencias

Lo siguiente a realizar es completar el array inicializandolo con todas las especialidades posibles, combinado con todos los turnos posibles y todas las divisiones posibles y el campo de legajo en cero.

Luego leo el primer registro y busco secuencialmente (aunque podría ser binaria) su especialidad en el array que esta ordenado, luego busco desde el principio de ese subgrupo el turno, para buscas en el principio de ese subsubgrupo la division que le corresponde, y en ese lugar guardo el legajo. Asi por cada registro.

Entonces me queda cargado el array con el contenido del archivo pero con el orden pedido.

Ahora recorro este array y grabo en el archivo nuevo siempre que no encuentre en cero el legajo.

Como moraleja usas mucha mas memoria y la carga inicial de la matriz puede ser conflictiva pero evitas el ordenamiento que baja la performance de un pgm.

Saludos!