Łączenie proste

0
procedure Simple_Merging_Sort (name:string);
 var
		k, i, j, kol, tmp:longint;
		a1, a2:string;
		f, f1, f2:text;
 begin
	kol := 0;
	assign(f,name);
	assign(f1,'temp1.txt');
	assign(f2,'temp2.txt');
	{$I-}
		reset(f);
	{$I+}
	if ioresult<>0 then
		writeln('')
	else
		begin
			while ( not eof (f) ) do
			begin
				readln(f,a1);
				inc(kol);
			end;
			close(f);
		end;
		k := 1;
		while ( k < kol ) do
		begin
			reset(f);
			rewrite(f1);
			rewrite(f2);
			if ( not eof (f) ) then readln(f,a1);
			while ( not eof (f) ) do
			begin
				i := 0;
				while (  (i < k) and (not eof (f)) ) do
				begin
					writeln(f1,a1);
					readln(f,a1);
					inc(i);
				end;
				j := 0;
				while (  (j < k) and (not eof (f))) do
				begin
					writeln(f2,a1);
					readln(f,a1);
					inc(j);
				end;
			end;
			close (f2);
			close (f1);
			close (f);


			rewrite(f);
			reset(f1);
			reset(f2);
			if ( not eof (f1) ) then readln(f1,a1);
			if ( not eof (f2) ) then readln(f2,a2);
			while ( not eof (f1) and not eof (f2) ) do
			begin
				i := 0;
				j := 0;
				while ( (i < k) and (j < k) and (not eof (f1)) and (not eof (f2)) )do
				begin
					if ( a1 < a2 ) then
					begin
						writeln(f,a1);
						readln(f1,a1);
						inc(i) ;
					end
					else
					begin
						writeln(f,a2);
						readln(f2,a2);
						inc(j) ;
					end;
				end;
				while ( (i < k) and (not eof (f1)) ) do
				begin
					writeln(f,a1);
					readln(f1,a1);
					inc(i) ;
				end;
				while ( (j < k) and (not eof (f2)) ) do
				begin
					writeln(f,a2);
					readln(f2,a2);
					inc(j) ;
				end;
			end;
			while ( not eof (f1) ) do
			begin
				writeln(f,a1);
				readln(f1,a1);
			end;
			while ( not eof (f2) ) do
			begin
				writeln(f,a2);
				readln(f2,a2);
			end;
			close (f2);
			close (f1);
			close (f);
			k :=k*2;
		end;
		erase(f1);
		erase(f2);
end; 

Procedura nie łączy poprawnie plików
Po kilku uruchomieniach wydaje mi się że podczas scalania nie kopiuje całego pliku
Jak poprawić tę procedurę

1
  1. nazwy zmiennych nic nikomu nie mówią
  2. podziel to na procedury
  3. pewny jesteś tego
writeln(f,a1);
readln(f1,a1);
  1. po co te warunki w pętli łączącej? (i < k)
0

@abrakadaber co do 4. wiesz jak działa iteracyjne scalanie gdy mamy dwie tablice pomocnicze
3. Tak to może gubić linie zwłaszcza gdy po przeczytaniu linii dostaniemy warunek kończący pętle
Co do 4. chodzi o to aby w jednej pętli przekopiować ciąg posortowany
Po k iteracjach mamy posortowane ciągi długości 2^k

1
i,j,k,kol to są liczniki więc nie bardzo wiem jak je inaczej nazwać , f,f1,f2 to zmienne plikowe
Jak się komu nie podoba to w edytorze jest taka opcja i stosunkowo łatwo zmienić tylko nie widzę innych nazw
2
Na stack overflow widziałem jak jeden umieścił iteracyjną wersję sortowania przez łączenie tablic w jednej procedurze i tam się nie czepiali
Poza tym nie bardzo wiem jaki fragment tej procedury wydzielić i co on miałby robić

@abrakadaber twoje podpowiedzi Newbiemu niewiele pomogą
Co do 4. jaką masz propozycję na uproszczenie warunków dla pętli while

2

Mam taką propozycję - skasuj ten kod i przygotuj się najpierw merytorycznie.
To co masz teraz nie kwalifikuje się nawet pod nazwę "newbie" - to jest jakiś potworek.

Poczytaj trochę o

I to nie jest procedura tylko cały program wp...isany w jedną procedurę.
Programowałeś wcześniej w COBOL-u?

0

To może zacznijmy od iteracyjnego sortowania tablic

procedure mergeSort(var A:TArray;size:integer)
var curr,left,mid,right:integer;
begin
     curr:=1;
     while(curr<=size-1)  do
     begin
          left:=0;
          while(left<size-1) do
          begin
              mid:=left+curr-1;
               if(left+2*curr-1<size-1) then
                  right:=left+2*curr-1
               else right:=size-1;
                merge(A,left,mid,right);
              left:=left+2*curr;      
          end;
          curr:=curr*2;
     end;
end;

Procedura przystosowana jest do tablic indeksowanych od zera
Jak zmienić indeksy aby procedura działała dla tablic indeksowanych od jedynki

Poza tym mam wątpliwości czy przy liniowej procedurze scalającej procedura sortująca nadal będzie O(nlogn)

0

Jak zmienić indeksy aby procedura działała dla tablic indeksowanych od jedynki

Hmm... a w jakim celu chcesz to zmienić?

Indeksowanie od 0 jest stosowane wszędzie, w znakomitej większości różnych algorytmów, praktycznie w każdym języku programowania. Jest tak oczywiste, że indeksowanie od 1 najczęściej uznaje się po prostu za błąd projektowy, wynikający z niewiedzy kodera. No chyba że odmienna indeksacja jest koniecznością. Czy w Twoim przypadku jest?

0

Bawię się programem do schematów blokowych i chciałbym prześledzić działanie tej procedury a w programie do schematów blokowych
tablice są indeksowane od jedynki
Próbowałem samemu przesunąć indeksy ale wychodziły one poza zaallokokowaną przez program tablicę

Algorytmy napisane u Cormena też mają indeksowanie od jedynki a procedurę scalającą napisałem na podstawie algorytmu znalezionego u Cormena
(eng version , w wersji polskiej napisanie procedury scalającej zostawili jako zadanie domowe)
Zastanawiam się też nad złożonością czasową - procedura scalająca działa w czasie liniowym ale znajduje się w dwóch zagnieżdżonych pętlach
Ciekawy jestem czy iteracyjny algorytm scalania tablic można przystosować do łączenia plików

Co do procedury scalającej ustawiłem indeksy dla dwóch "połówek" tablicy pomocniczej oraz wyjściowej tablicy
Ustawiłem też zmienne oznaczające liczbę elementów w każdej z "połówek" tablicy pomocniczej
Do przekopiowania wyjściowej tablicy do tablicy pomocniczej użyłem pojedynczej pętli for
Kopiowanie elementów z pomocniczej tablicy do wyjściowej tablicy rozbiłem na trzy pętle while
Właściwe sortowanie odbywa się podczas kopiowania elementów z tablicy pomocniczej do wyjściowej tablicy

1

Bawię się programem do schematów blokowych i chciałbym prześledzić działanie tej procedury a w programie do schematów blokowych tablice są indeksowane od jedynki

No to niedobrze, że od początku uczą złych praktyk. Bardziej humanistyczny ten program, niż programistyczny.

Próbowałem samemu przesunąć indeksy ale wychodziły one poza zaallokokowaną przez program tablicę

Najpierw postaraj się zrozumieć jak ten algorytm działa, a jak to zrozumiesz to będziesz wiedział jak zmieniają się indeksy i będziesz sobie mógł je zmodyfikować. Ogólnie nie polecam indeksowania od innej liczby niż 0, ale jak chcesz to się baw.

Ciekawy jestem czy iteracyjny algorytm scalania tablic można przystosować do łączenia plików

Najpierw zastanów się nad tym, czy ma to sens. Jeśli uważasz że jest sens to napisz sobie poprawnie działający algorytm dla tablic. A jak już będziesz miał prawidłowy kod to przystosuj go pod obsługę łączenia plików. Różnica jest taka, że tablice masz już w pamięci, a pliki musisz dopiero załadować.

0

Z tą procedurą to już sobie poradziłem tylko jak przystosować ten algorytm do scalania plików

0

Znalazlem u pewnego kolesia kod rozbity na trzy procedury
Jak go skompilowaem i uruchomiem to okazalo sie ze program nie dosc ze nie kopiuje calego
pliku to nawet nie sortuje poprawnie tego co przekopiowal

Procedura rozdzielajaca


procedure Split(partLength:longint;var inFile,auxFileOne,auxFileTwo:text);
var buffer:string;
    counter:longint;
begin
  repeat
     counter:=1;
     while((counter<=partLength)and(not eof(inFile)))do
     begin
       ReadLn(inFile,buffer);
       WriteLn(auxFileOne,buffer);
       counter:=counter+1
     end;
     counter:=1;
     while((counter<=partLength)and(not eof(inFile)))do
     begin
       ReadLn(inFile,buffer);
       WriteLn(auxFileTwo,buffer);
       counter:=counter+1
     end;
  until eof(inFile);
end;

Procedura scalajaca


procedure Combine(partLength:longint;var auxFileOne,auxFileTwo,inputFile:text);
var bufferOne,bufferTwo:string;
    counterOne,counterTwo:longint;
begin
  if not eof(auxFileOne)then
      ReadLn(auxFileOne,bufferOne);
  if not eof(auxFileTwo)then
      ReadLn(auxFileOne,bufferTwo);
  while((not eof(auxFileOne))and(not eof(auxFileTwo)))do
  begin
    counterOne:=1;
    counterTwo:=1;
    repeat
      if(bufferOne<bufferTwo)then
      begin
        WriteLn(inputFile,bufferOne);
        if not eof(auxFileOne)then
             ReadLn(auxFileOne,bufferOne);
        counterOne:=counterOne+1;
      end
      else
      begin
        WriteLn(inputFile,bufferTwo);
        if not eof(auxFileTwo)then
             ReadLn(auxFileTwo,bufferTwo);
        counterTwo:=counterTwo+1;
      end;
    until not ((counterOne<=partLength)and(counterTwo<=partLength)
               and(not eof(auxFileOne))and(not eof(auxFileOne)));
    while((counterOne<=partLength)and(not eof(auxFileOne)))do
    begin
      ReadLn(auxFileOne,bufferOne);
      WriteLn(inputFile,bufferOne);
      counterOne:=counterOne+1;
    end;
    while((counterTwo<=partLength)and(not eof(auxFileTwo)))do
    begin
      ReadLn(auxFileTwo,bufferTwo);
      WriteLn(inputFile,bufferTwo);
      counterTwo:=counterTwo+1;
    end;
  end;
  while(not eof(auxFileOne))do
  begin
    ReadLn(auxFileOne,bufferOne);
    WriteLn(inputFile,bufferOne);
  end;
  while(not eof(auxFileTwo))do
  begin
    ReadLn(auxFileTwo,bufferTwo);
    WriteLn(inputFile,bufferTwo);
  end;
end;

Procedura sortujaca


procedure main;
var inputFile,auxFileOne,auxFileTwo:text;
    inputFileName,auxFileNameOne,auxFileNameTwo:string;
    partLength:longint;
    exitCond:boolean;
begin
  inputFileName:=ParamStr(1);
  auxFileNameOne:=copy(inputFileName,1,Pos('.',inputFileName)-1)+'_01.txt';
  auxFileNameTwo:=copy(inputFileName,1,Pos('.',inputFileName)-1)+'_02.txt';
  
  assign(inputFile,inputFileName);
  assign(auxFileOne,auxFileNameOne);
  assign(auxFileTwo,auxFileNameTwo);
  
  partLength:=1;
  exitCond:=false;
  repeat
    
    Reset(inputFile);
    ReWrite(auxFileOne);
    ReWrite(auxFileTwo);
    
    Split(partLength,inputFile,auxFileOne,auxFileTwo);
    
    Close(auxFileOne);
    Close(auxFileTwo);
    Close(inputFile);
    
    ReWrite(inputFile);
    Reset(auxFileOne);
    Reset(auxFileTwo);
    
    if not eof(auxFileTwo)then
    begin
      Combine(partLength,auxFileOne,auxFileTwo,inputFile);
      partLength:=2*partLength;
    end
    else
       exitCond:=true;
    
    Close(auxFileTwo);
    Close(auxFileOne);
    Close(inputFile);
    
  until exitCond;
end;

Nie moge zlokalizowac bledu

0
  1. po co te warunki w pętli łączącej? (i < k)

Tutaj uzytkownik chyba nie zna algorytmu (albo udaje)

W sortowaniu przez laczenie wystepuja tzw serie czyli uporzadkowane ciagi elementow (tutaj skladowych pliku)
Przy scalaniu plikow bierze sie pod uwage wystepujace w nim serie
W laczeniu prostym zaklada sie ze poczatkowe serie sa dlugosci 1
Tutaj dlugosc serii w danej iteracji jest stala (zwykle jest potega dwojki jesli korzystamy z dwoch plikow pomocniczych)
W laczeniu naturalnum koniec serii ustala sie czytajac i porownujac dwa kolejne elementy
a co za tym idzie dlugosc serii w danej iteracji jest zmienna
Zmienne i oraz j to liczniki przeczytanych elementow a k to dlugosc serii
(liczniki byly inicjowane zerem stad nierownosc ostra)

1 użytkowników online, w tym zalogowanych: 0, gości: 1