Pascal/Turbo Pascal - Busqueda de la mediana

Hola, he estado mirando por ahí las técnicas "divide y vencerás" y me he encontrado un método, el de la búsqueda de la mediana. Me ha parecido interesante y tan solo veo ejemplos en los libros y pseudocódigo. El caso es que he intentado implementar ese pseudocodigo en pascal para ver como funciona pero nada, no lo he conseguido.

¿Alguien sabe dónde puedo conseguir dicho código? O si alguien lo ha implementado del papel a pascal? Ya sé que por la red hay miles, pero tan solo he encontrado pseudocodigo y no lo implemento bien en pascal...

Espero que alguien me ayude. Gracias!

Yo mientras, seguiré buscando por ahí. Un saludo!

Si la lista está ordenada, la búsqueda de la mediana sólo supone mirar el centro ;-)

Suponiendo un caso de más complejidad (lista desordenada)... ¿por qué no pones el fuente que has intentado, para ver si descubrimos el fallo?

Ok, lo que quiero hacer es buscar la mediana sin ordenar el vector. Tan solo debo poner los menores a la izquierda y mayores a la derecha, pero no debo usar ningun metodo de ordenacion como aparece por la red (ni QuickSort, ni nada de eso). Lo debo hacer como lo explica esta pagina: http://euitio178.ccu.uniovi.es/wiki/index.php/TP:B%C3%BAsqueda_de_la_mediana_-_Divide_y_vencer%C3%A1s

Los datos los leeré desde un fichero de este tipo:
___________
4
156897415
5
46787561
___________

Lo que significa el fichero es que, la primera linea donde aparece solo un numero es la posicion enesima que tengo que hallar, es decir, mirando el primer ejemplo del fichero: buscar qué numero del vector de abajo ocuparía la 4ª posicion si estuviera ordenado (pero sin ordenarlo). Y luego, buscar qué numero del otro vector ocuparía la 5ª posicion si éste estuviera ordenado.

Espero que lo entendáis mejor desde la página que os he proporcionado. Bueno, mi código está fatal pero bueno jejej, por eso os pido ayuda. Yo lo he intentado pero debo tener algun error muy gordo. Y bueno, el código que tengo es este:

(Gracias por la ayuda que me podáis ofrecer)

(*************************************************************************************************************)

program mediana;

uses
crt;

const
OPCIONES_MENU = 2;
MIN = 1;
MAX = 30;

type

Tvect = array [MIN..MAX] of integer;
Taux = array [MIN..MAX] of integer;

var
info : integer;
fich : text;
vect : Tvect;
aux : Taux;
cont, s, p, izda, dcha : integer;

(*************************************************************************************************************)

procedure pivotebis(vect : Tvect; var P : integer; var i : integer; var j : integer; var dcha : integer; var izda : integer);
var
cont1, cont2, x : integer;
begin

cont1 := i - 1;
cont2 := j + 1;

for x := i to j do
begin
if (vect[i] < P) then
begin
aux[cont1] := vect[i];
cont1 := cont1 + 1;
end;

if (vect[i] > P) then
begin
aux[cont2] := vect[i];
cont2 := cont2 -1;
end;
end;

dcha := cont1;
izda := cont2;
writeln();
writeln(' Procediendo a ubicar mayores y menores que el pivote' );
writeln();
writeln('Nnuevo vector: ');

for x := cont1 to cont2 do
begin
write(' ', aux[x]);
end;

writeln();
readln;
readln;
end;

(*************************************************************************************************************)

function mediana(vector : Tvector; i : integer; var j : integer) : integer;
var
med : integer;
begin

med := (i + j) div 2;

if (med < i) then
med := i
else
if (med > i) then
med := i
else
if (med < j) then
med := j
else
if (med > j) then
med := j;

mediana := med;
writeln();
writeln(' El nuevo pivote es : ', med);
writeln();
readln;
end;

(*************************************************************************************************************)

procedure seleccion(vector : Tvector; posic : integer; var dcha : integer);
var
i, j : integer;

begin
i := 1;
j := MAX;

repeat
P := mediana(vect, i, j);
pivotebis(vect, i, j, P, izda, dcha);

if (s > izda) then
j := izda + 1
else if (s < dcha) then
i := dcha - 1;

until ((izda <= s) and (s <= dcha));

writeln( s, '-esima posicion del vector es :', P);
writeln();
end;

(*************************************************************************************************************)

procedure leer_fichero(var fich : text; var vect : Tvect);
begin
assign(fich,'informacion.dat');
reset(fich);

cont := 0;

while not eof(fich) do
begin
while not eoln(fich) do
begin
read(fich, info);
s := info;
write(s);
end;

readln();

while not eoln(fich) do
begin
cont := cont + 1;
read(fich, info);
vect[cont] := info;
write(vect[cont]);
end;

seleccion(vect, s, cont);

if not eof(fich) then
readln(fich);
end;
end;

(*************************************************************************************************************)

procedure elija(selecc : integer);
begin
case selecc of
1 : leer_fichero(fich, vect);
end;
end;

(*************************************************************************************************************)

procedure menu;
var
opc : integer;

begin
repeat
clrscr;
writeln();
writeln('============MENU=============');
writeln('=== ===');
writeln('=== 1. Programa ===');
writeln('=== 2. Exit ===');
writeln('=== ===');
writeln('=============================');
writeln();

write('Elija una opcion: ');
readln(opc);
elija(opc);
until (opc = OPCIONES_MENU);
end;

(*************************************************************************************************************)

begin
menu;
end.

Yo lo que veo aquí es que cometes un grave error al querer leer un archivo de tipo text con Read() y encima asignando el valor leído directamente a un integer, debes estar obteniendo basura...
El resto del programa no lo comprendí.

Eso me lee perfectamente. El resto del programa es lo que necesito implementar para "buscar la mediana", aunque claro, no lo tengo bien implementado jejeje.

Pero lo de leer el fichero me funciona perfecto, me lee los valores exactamente tal y como están en el fichero.

Lo primero y principal: si lo debes hacer como explica la página

http://euitio178.ccu.uniovi.es/wiki/index.php/TP:B%C3%BAsqueda_de_la_mediana_-_Divide_y_vencer%C3%A1s

¿Por qué no sigues su algoritmo, en vez de inventarte tú uno?

El tuyo me cuesta horrores seguirlo. Aun así, algún comentario:

- Eso de que menú llame a Elija, Elija llame Leer_Fichero, Leer_Fichero llame Seleccion (antes de terminar de procesar el fichero y de cerrarlo!) y así sucesivamente, lo hace MUY difícil de leer.

- Pasos "rebuscados": Para leer el fichero, ¿no te bastaría con algo como (suponiendo que cada cifra está en una línea)?

cont := 1;
while not eof(fich) do
begin
readln(fich, vect[cont]);
cont := cont + 1;
end;
close(fich);

- Errores de concepto: "mediana" también lo veo algo engorroso... e incomprensible. Supongamos que miro entre 4 y 10. Al hacer

if (med > i) then
med := i

lo que consigues es que med sea 4... ¡¡¡¡ siempre !!!!

Sólo tendría algo de sentido (como mucho)

if (med < i) then
med := i
else
if (med > j) then
med := j;

aunque si i<j, su media nunca puede ser <i ni <j , así que sobraría todo eso

- Pasos sin completar: pivoteBis parece que recoloca los menores y mayores, unos a un lado y otros a otro, y guarda los valores temporales en "aux"... pero... ¿cuando los haces "definitivos", devolviéndolos a "vect"?

...

Bueno, por eso pregunté, es que no se me ocurre como implementar el metodo de la "mediana". Con respecto al fichero. El primer dato te dice qué posicion quieres buscar, qué valor ocuparía la posicion que te dice el fichero. Y la siguiente línea del fichero te da los valores del vector a utilizar:

El fichero es de este tipo:
______________________

7
8 2 6 3 1 8 2 5 6 7 3 3
______________________

Lo de "¿cuando los haces "definitivos", devolviéndolos a "vect"?", jejej, me di cuenta anoche de que no lo igualo al vector original. Lo que hice fue utilizar un for para igualar el vector "original" al vector "auxiliar"

for n := 1 to tamaño_vector do
vector[n] := aux[n];

Y bueno, Gracias por la ayuda q estoy recibiendo. Yo aún estoy intentando que me funcione...