algorytm.org

Sortowanie przez łączenie naturalne

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Sortowanie przez łączenie naturalne
Ocena użytkowników:***** / 22
SłabyŚwietny 
Wpisany przez Karol Kokoszka, 28 sierpnia 2005 01:00

Czasami zdarza się, że dane które chcemy posortować nie mieszczą się w pamięci głównej komputera i są przechowywane np. w plikach. Nie mamy wtedy bezpośredniego dostępu do dowolnego elementu ciągu do posortowania (teoretycznie mamy ale wyszukanie kolejnego elementu w ciągu znajdującego się przed elementem który pobraliśmy ostatnio wymaga przejścia pliku od początku).
W takich przypadkach stosuje się np. sortowanie przez łączenie naturalne przy użyciu dwóch plików pomocniczych. Wygląda ono następująco. Zakładamy że sortujemy niemalejąco.
  1. Rozdziela się seriami plik wejściowy na dwa pliki pomocnicze. To znaczy przechodząc plik wejściowy od początku wyszukujemy ciągi posortowane i zamiennie zapisujemy na dwa pomocnicze pliki. W praktyce wygląda to tak, że pobiera się n-ty oraz (n+1)-wszy element z pliku i sprawdza czy (n+1)-wszy jest większy lub równy n-temu. Jeśli tak to należy do ciągu i zapisujemy go na ten sam plik pomocniczy co element n-ty. Jeśli nie to zapisujemy go na inny (drugi) plik pomocniczy i tak w kółko aż do zakończenia pliku wejściowego.
  2. Łączymy serie z plików pomocnicze i kopiujemy do pliku wejściowego (wejściowy lub dla ochrony danych można sobie wziąć kolejny plik pomocniczy i na początku po prostu skopiować plik wejściowy na niego).Łączenie to przebiega analogicznie do scalania ciągów, z tą różnicą, że tutaj oba pliki wejściowe niekoniczenie są całkowicie posortowane.
  3. Wykonujemy zamiennie kroki 1 i 2 aż do momentu w którym otrzymamy w pliku wejściowym tylko jedną serię, która jest naszym posortowanym ciągiem.
Przykład:

Plik wejściowy: 1987457614098134817

Po pierwszym kroku:
Pierwszy plik pomocniczy: 19 7 6 09 134 8 (odstępy pomiędzy seriami)
Drugi plik pomocniczy: 8 457 14 8 17
Plik wejściowy: 1894577146089113478

Po drugim kroku:
Pierwszy plik pomocniczy: 189 146 113478
Drugi plik pomocniczy: 4577 089
Plik wejściowy: 1457789014689113478

Po trzecim kroku:
Pierwszy plik pomocniczy: 1457789 113478
Drugi plik pomocniczy: 014689
Plik wejściowy: 0114456778899 113478

Po czwartym kroku:
Pierwszy plik pomocniczy: 0114456778899
Drugi plik pomocniczy: 113478
Plik wejściowy: 0111134445677788899

W teorii algorytm prezentuje się bardzo prosto, ale problemy mogą być z implementacją. Jednym ze sposobów na zaznaczenie serii w plikach pomocniczych jest umieszczanie pomiędzy nimi znaku #0 (char 0), jednakże nie jest to najlepsze rozwiązanie.
Drugim sposobem jest opakowanie funkcji (na przykładzie pascala) read (odczyt z pliku) w taki sposób żebyśmy mieli dostęp do elementu na który wskazuje wskaźnik, tzn żebyśmy mogli go pobrać nie przesuwając przy tym wskaźnika (standardowo jeżeli odczytamy znak z pliku to wskaźnik przesuwa się na następny element).

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Karol KokoszkaDelphi/Pascal
.pas
.pas
***** / 3
Karol KokoszkaDelphi/Pascal
.pas
.pas
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 27 maja 2011 08:47
Komentarze
photo
-1 # chicken 2014-01-15 09:24
super wytłumaczone! dzięki!
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-1 # konofał master 2014-02-05 11:30
supcio programik, niestety ja z C++ nadaje
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+1 # qq 2014-05-18 12:18
o ile pamiętam standard pascala, to można sięgnąć do pierwszego elementu pliku nie czytając go. robiło się to bodaj tak:
f - zmienna plikowa
f^ - pierwszy element pliku (jest on po prostu buforowany i mamy dostęp do tego bufora; co więcej (o ile pamięć nie myli), to nawet przy pliku otwartym do odczytu, możemy do tego bufora zapisać - choć to może jest już herezja)
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz