Sortowanie linii w pliku

Sortowanie linii w pliku można podzielić na dwa etapy

1. Wczytanie fragmentów pliku do dostępnej dla nas pamięci RAM i posortowanie ich ulubioną metodą
   Jaka metoda byłaby najlepsza ?

Sortowanie przez scalanie
+nie zwolni do n^2
+jest stabilny
+można usunąć rekurencje
+nadaje się do sortowania list czy plików
-wymaga dodatkowej pamięci (więc jeśli nie zależy nam na stabilności to lepiej z niego na razie zrezygnować)

Sortowanie szybkie
+w przypadku średnim jest podobno dość szybki
-może zwolnić do n^2
-nie jest stabilny
-nie jest aż tak dobre do sortowania list czy plików jak sortowanie przez scalanie
-usunięcie rekurencji wymaga dodatkowej tablicy o liczbie elementów proporcjonalnej do liczby elementów sortowanej tablicy (nie nadaje się do naszego sortowania)

Sortowanie przez kopcowanie
+nie zwolni do n^2
+można usunąć rekurencję (u Cormena pojawia się rekurencyjne przywracanie kopca)
+sortuje w miejscu
-nie jest stabilny
-nadaje się tylko do sortowania tablic (ale to nam nie przeszkadza)

Jeżeli nie zależy nam na stabilności to dobrym wyborem jest posortowanie tego co można wczytać do pamięci przez kopcowanie

2. To czego nie uda nam się posortować w pamięci RAM sortujemy przez scalanie

Z posortowaniem tego co można wczytać do pamięci RAM nie będzie problemu
Problemem może być sortowanie plików przez scalanie
Sortowanie w pamięci RAM może jedynie przygotować początkowe serie
ale nie załatwi problemu sortowania

U Diksa i Ryttera jest taki opis algorytmu

Scalanie wielofazowe z 4 plikami {Tak je nazwali}

Załóżmy że bloki zostały rozłożone na pliki P0 i P1.
Pliki P2 i P3 są początkowo puste.

i1:=0; i2:=1; {numery plików wejściowych, tzn. otwartych do czytania}
j1:=2; j2:=3; {numery plików wyjściowych, tzn. otwartych do pisania}

dopóki jest więcej niż jeden blok wykonuj
a) scal pierwszy blok na Pi1 z pierwszym blokiem na Pi2 i powstający blok zapisz na Pj1
b) scal następny blok na Pi1 z następnym blokiem na Pi2 i powstający blok zapisz na Pj2
c) powtarzaj kroki a) i b) (kładąc powstające bloki na przemian na pliki Pj1 i Pj2) aż zostanie osiągnięty koniec plików Pi1 i Pi2
d) przewiń wszystkie pliki do początku; dodaj liczbę 2 mod 4 do i1, i2, j1, j2, odwracając w ten sposób rolę plików wejściowych i wyjściowych

Problem w tym jak zapisać ten algorytm w języku programowania

Problem w tym jak zapisać ten algorytm w języku programowania

od poczatku

Z czym konkretnie masz problem? Jakie jest jedno konkretne pytanie. Czego dokladnie nie umiesz

Nie bardzo rozumiem o co chodzi ale może odpowiedź znajdziesz w tych algorytmach
algorytmy

Masz tam zarówno wytłumaczenie jak i przykładowe implementacje

Zajrzyj sobie do "Perełek Programowania", nie pamietam, która część, tam jest opisany podobny problem - sortowania gdy nia ma miejsca w pamięci.

Jak sortujesz linie w pliku, to jaką Ci różnicę robi, czy algorytm sortujący jest stabilny czy nie? Jedyna sytuacja, w której dwie linie porównują się ≤ oraz ≥ jest wtedy, gdy to są takie same linie, więc nie da się stwierdzić, czy ich kolejność została przestawiona czy nie.

"Jak sortujesz linie w pliku, to jaką Ci różnicę robi, czy algorytm sortujący jest stabilny czy nie? "

Też tak myślałem że jeśli sortujemy pojedyncze linie to nie zależy nam na stabilności
a zatem dobrym wyborem będzie wczytanie tego co się da do pamięci i posortowanie tego przez kopcowanie
i z tym nie będzie problemu

Jednak samo sortowanie w pamięci RAM nie wystarczy bo przypuśćmy że mamy takie sytuacje

1. Mamy bardzo mało dostępnej pamięci RAM jak np w DOS
2. Plik do posortowania jest zbyt duży aby wczytać go do pamięci

Problem jest w tym że Cormen ograniczył się do sortowania tablic a na podstawie jego opisu algorytmów łatwo było napisać kod

Przeanalizujmy opis algorytmu u Diksa linia po linii

Załóżmy że blok to ciąg uporządkowany zwany serią

dopóki jest więcej niż jeden blok wykonuj
Zadeklarować zmienną logiczną czy zdefiniować funkcję
jak wykryć że jest więcej bloków nie komplikując kodu (tzn aby nadal mieć nlogn)

scal pierwszy blok na Pi1 z pierwszym blokiem na Pi2 i powstający blok zapisz na Pj1

Tutaj można by napisać procedurę scalającą
Trzeba uważać aby cały plik został skopiowany
Czy tutaj łańcuch reprezentujący linię opakować w rekord ze zmienną logiczną przechowującą wynik sprawdzania czy osiągneliśmy koniec bloku
Jeśli chodzi o procedurę scalającą to mam tylko tę na tablicach Czy można ją przystosować do scalania bloków pobranych z plików

przewiń wszystkie pliki do początku; dodaj liczbę 2 mod 4 do i1, i2, j1, j2, odwracając w ten sposób rolę plików wejściowych i wyjściowych

Tutaj może być konieczne zamknięcie plików i ich ponowne otwarcie