Merge Sort

         Merge Sort

Naslov:
Merge Sort
Jezik:
C
Avtor:
Philip J. Erdelsky

Datum:
31. julij 1998
Uporaba:
Javna domena; brez omejitev uporabe
Prenosljivost:
Vsak prevajalnik C
Ključne besede:
Razvrsti
Povzetek:
Funkcija C za razvrstitev datoteke, uporaba poljubnih funkcij za branje, pisanje in primerjavo ter algoritem združevanja trakov, ki je v vseh primerih O (n log n). Funkcija je ne-rekurzivna in ponovno udeležena.

Funkcija merge_sort () bo razvrstila skoraj vsako vrsto datoteke, z uporabo funkcij za branje, pisanje in primerjavo, ki jih priskrbi program za klicanje.

  1. Vrne zapise spremenljive velikosti.
  2. Zahteva primerjave O (n log n), kjer je n število zapisov, ne glede na začetni red. Čas za razvrstitev datoteke je predvidljiv in dosleden. Ta izvedba je znana kot optimalna za splošne vrste.
  3. Število zapisov, ki jih je treba zapisati ali zapisati v datoteko diska, je tudi O (n log n).
  4. Algoritem je iterativen, ne rekurziven, zato ni problema s prelivanjem stackov. Zahtevnost sklada je predvidljiva, dosledna in majhna.
  5. Zahteva približno dovolj prostora na disku, da ima dve kopiji datoteke. Razčlenjena datoteka je ostala v tem prostoru.
  6. Za shranjevanje treh zapisov potrebuje vsaj dovolj pomnilnika, vendar bo hitrejši, če je na voljo več pomnilnika.
  7. Kliče tmpfile (), da ustvari kar štiri začasne datoteke hkrati.
  8. Nerazvrščeno datoteko beremo zaporedno in razvrščena datoteka zapišemo zaporedoma. Zato so lahko trakovi, vhodi / izvodi ali druge strogo zaporedne naprave.

Klic funkcije je naslednji:

rezultat = merge_sort (unsorted_file, sorted_file, branje, pisanje, primerjava,
        kazalec, max_record_size, block_size, pcount);

Klicni program mora vsebovati naslednje parametre:

FILE * unsorted_file;
Kazalec datoteke za datoteko, ki jo želite razvrstiti. Datoteka mora biti uspešno odprta za branje, kazalec datoteke pa mora biti nameščen na začetku datoteke.
FILE * sorted_file;
Kazalec datoteke za razvrščeno datoteko. Datoteka mora biti uspešno odprta za pisanje, kazalec datoteke pa mora biti postavljen na začetek datoteke.
int (* prebrano) ();
Funkcija, ki bere en zapis.
int (* napisati) ();
Funkcija, ki zapisuje en zapis.
int (* primerjalno) ();
Funkcija, ki primerja dve zapisi.
void * kazalec;
Uporabniško določen kazalec, ki se prenese na funkcije (* read) (), (* write) () in (* compare) (), ko se kličejo.
unsigned max_record_size;
Največje število bajtov v zapisu, ko se bere v pomnilnik. To ne sme biti enako kot velikost zapisa, ko prebiva v datoteki.
nepodpisan dolg blok_size;
Število zapisov, ki jih je treba razvrstiti v pomnilnik, ali 1L, če ni mogoče uporabiti pomnilnika pomnilnika.
nepodpisan dolg * pcount;
Kazalec na spremenljivko za prejemanje števila zapisov (če je vrsta uspešna) ali NULL, če teh podatkov ni treba vrniti.
Funkcija vrne naslednje vrednosti:

int rezultat;
Koda rezultata:
0 za uspešno vrsto
1 za nezadosten pomnilnik
2 za napako pri ustvarjanju datoteke
3 za napako zapisovanja datoteke

Nesortirane in razvrščene datoteke ne bodo prevezane ali zaprtih. Vsaka datoteka bo ostala odprta, s kazalko datoteke, ki je nameščena na koncu datoteke. Če pa sta obe datoteki kazalci identični, bo datoteka preklicana in razvrščeni zapisi bodo napisani nad njim.

Funkcijo (* branje) () pokliče merge_sort (), kot sledi, in mora vsakič, ko se kliče, brati en zapis (razen, če je zaznan konec nesortirane datoteke):

      n = (* prebrano) (fp, pufer, kazalec);

DATOTEKA * fp;
Kazalec datoteke za nesortirano datoteko ali začasno datoteko, ki jo je ustvaril tmpfile ().
prazen * pufer;
Kazalec na pufru, ki naj prejme en zapis. Ta medpomnilnik lahko vsebuje največ max_record_size bajtov.
void * kazalec;
Kopija kazalca je bila kot argument za merge_sort ().
int n;
Število bajtov v zapisu ali nič, če je bil poskušal prebrati mimo konca nesortirane datoteke.

Ko ta funkcija vrne nič, se za isto datoteko ne bo večkrat poklical. Noben poskus ne bo prebral mimo konca začasne datoteke.

Zapis, ki je večji od določene maksimalne velikosti, je treba skrajšati ali obravnavati na drug primeren način. Funkcija bo katastrofalno propadla, če je dovoljeno prekrivanje medpomnilnika ali če je vrednost, ki jo vrne (* read) (), večja od največje velikosti zapisa.

Oblika zapisa se lahko spremeni, če jo berete v pomnilnik, če:

  1. spremembe so združljive s funkcijami (* write) () in (* compare) (), in
  2. vrednost, ki jo vrne funkcija (branje) (), mora biti število bajtov v zapisu, medtem ko je v pomnilniku.

Na primer, se vrstica terminator \ r \ n v DOS / Windows morda pretvori v \ n, ko se bere v pomnilnik.

Funkcija (* write) () se imenuje, kot sledi, in vsakič, ko se pokliče, mora zapisati en zapis:

      n = (* zapis) (fp, pufer, kazalec);

DATOTEKA * fp;
Kazalec datoteke za razvrščeno datoteko ali začasno datoteko, ki jo je ustvaril tmpfile ().
prazen * pufer;
Kazalec na pufru, ki ima en zapis, ki ga beremo v pomnilnik z (* beremo) ().
void * kazalec;
Kopija kazalca je bila kot argument za merge_sort ().
int n;
Nenamerno za uspešno pisanje; nič za nezadosten prostor na disku.

Upoštevajte, da se dolžina zapisa ne prenese kot parameter. Vsebovati mora izrecno ali implicitno v samem zapisu ali na drugem mestu, ki je dostopna funkciji (* write) ().

Funkcijo (* primerjalno) () je poklican za primerjavo dveh zapisov, in sicer:

      n = (* primerjati) (p, q, kazalec);

void * p;
Kazalec na pufru, ki vsebuje prvi zapis, ki se prebere v pomnilnik z (* branje) ().
prazen * q;
Kazalec na pufru, ki vsebuje drugi zapis, ki ga beremo v pomnilnik z (* beremo) ().
void * kazalec;
Kopija kazalca je bila kot argument za merge_sort ().
int n;
Rezultat primerjave, kot sledi:

  • > 0, če je * p treba po * q v razvrščenem vrstnem redu
  • <0, če je * p pred * q v razvrščenem vrstnem redu
  • 0, če je vrstni red * p in * q nepomemben

Sorta poteka na naslednji način:

  1. Zapise se berejo iz nesortirane datoteke in zapisane v dve začasni datoteki v blokih. Vsak blok vsebuje število zapisov, ki jih določa argument block_size (razen zadnjega bloka, ki lahko vsebuje manj zapisov), in je razvrščen v pomnilnik s klicem linked_list_sort (), preden je napisan v začasno datoteko.
  2. Začasne datoteke se nato razvrstijo z združevanjem blokov v več prelazih. V vsakem prehodu so bloki iz dveh izvornih datotek združeni v bloke, ki vsebujejo dvakrat toliko zapisov in so zapisani v dve izhodni datoteki. Postopek se zaključi, ko je velikost bloka enaka ali večja od velikosti datoteke, vsi zapisi pa so v eni datoteki, ki je razvrščena datoteka.

Razvrstitev lahko propade, če

  1. klic na malloc () vrne NULL, ker ni dovolj pomnilnika ali
  2. klic na tmpfile () vrne NULL, ker je preveč odprtih datotek ali
  3. klic na (* write) () vrne nič, ker na disku ni dovolj prostora.

Ne glede na to, ali je vrsta uspešna ali ne, bodo vsi dodeljeni pomnilniški bloki deaktivirani, vse začasne datoteke pa bodo zaprte in izbrisane. Če vrstica ne uspe, bodo kazalci datoteke za nesortirane in razvrščene datoteke zapustili kjerkoli se bodo zgodili.

Funkcija merge_sort () se ponovno vključi, če funkcije, ki jih kličete, ponovno vključujejo:

  • (* primerjava) ()
  • fclose ()
  • prost()
  • malloc ()
  • memcpy ()
  • (* prebrano) ()
  • previjanje nazaj ()
  • tmpfile ()
  • (* napisati) ()

Pod DOS / Windows, tmpfile () ustvari datoteko BINARY. Vendar to običajno ne povzroča težav, tudi če so nesortirane in razvrščene datoteke besedilne datoteke, ker DOS / Windows konstantno obdeluje konverzije.

Če je prostor na disku izredno tesen, se lahko vrsta spremeni, da uporabi prostor, ki ga zaseda nesortirana datoteka. Nerazvrščena datoteka, začasne datoteke in razvrščena datoteka se nato lahko prilegajo v prostor, ki je približno dvakrat večji od nesortirane datoteke. Če želite narediti to spremembo, preprosto vstavite kodo, da izbrišete nesortirano datoteko, ko jo berete. Če je ta tehnika uporabljena, morajo biti razvrščene in nesortirane datoteke drugačne, struktura posredovanja argumentov pa lahko postane nekoliko manj elegantna, ker klic funkcije za brisanje datoteke ponavadi zahteva specifikacije datoteke in ne le kazalec datoteke.

Funkcija merge_sort () ni stabilna; tj. ne ohranja relativnih pozicij dveh zapisov, za katere funkcija (* primerjati) () vrne nič. Funkcija stable_merge_sort () ima to lastnost. Vendar dodatna funkcija prinaša ceno: v vsak zapis je dodana štirometna zapisana številka, medtem ko je v pomnilniku ali v začasni datoteki. To poveča zahteve glede diska in pomnilnika, če je njihova velikost manjša.

Pripomoček SORT ponazarja uporabo stabilnega_merge_sort (). To je filter DOS ali UNIX, ki razvrsti vrstice besedilne datoteke. Največja dolžina črte je MAX_LINE znakov, ki ne vključujejo vračanja vozička in vrstice na koncu vsake vrstice. Pripomoček bo prekinil vrsto in prikazal sporočilo o napaki, če bere črto, ki vsebuje več kot MAX_LINE znakov. Vrednost MAX_LINE je nastavljena na 255, vendar jo je mogoče spremeniti s preoblikovanjem pripomočka.

Uporabnost se imenuje takole:

      SORT <unsorted_file> sortirano_file M N

Razred vključuje stolpce številka M do N, vključno, kjer je najsvetlejši stolpec številka nič. Če je N izpuščen, sorta vključuje stolpec M in vse stolpce desno od nje. Če sta obe M in N izpuščeni, se v stolpcu uporabljajo vsi stolpci.

Črta, ki vsebuje manj kot N + 1 stolpci, je razvrščena, kot da je bila na desni strani označena z ničlami.

Znaki so uvrščeni po svojih ASCII kodah, ki se štejejo za NISELJENI bajtov.

Ta paket zahteva drug paket:

Izvorna koda v besedilnem formatu:

Vir: http://www.efgh.com/software/mergesor.htm

 

Leave a Reply

Your email address will not be published. Required fields are marked *