Fuzionare Sortare

Titlu:

Merge Sort

Language:

C

Autor:

Philip J. Erdelsky

• [email protected]
• http://www.alumni.caltech.edu/~pje/

Data:

Julie 31, 1998

Utilizare:

Domeniul public; nu exista restrictii privind utilizarea

Portabilitate:

Any compilator C 

Cuvinte cheie:

Sortare

Rezumat:

O functie C pentru a sorta un fisier, folosind functii arbitrare de citire, scriere si comparare si un algoritm de imbinare a benzii, care este O (n log n) in toate cazurile. Functia este non-recursiva si reintroducatoare.

Functia merge_sort () va sorta practic orice tip de fisier, utilizand functiile de citire, scriere si comparatie furnizate de programul de asteptare.

1. Se sorteaza inregistrari de marime variabila.
2. Acesta necesita O (n log n), comparatii unde n este numarul de inregistrari, indiferent de ordinul initial. Timpul de sortare a unui fisier este previzibil si consecvent. Aceasta performanta este cunoscuta ca fiind optima pentru tipurile generale.
3. De cate ori o inregistrare trebuie citita sau scrisa intr-un fisier de disc este O (n log n).de asemenea.
4. Algoritmul este iterativ, nu recursiv, deci nu exista nicio problema de depasire a stivei. Cerinta stivei este previzibila, consistenta si mica.
5. Acesta necesita spatiu suficient de spatiu pentru a tine doua copii ale fisierului. Fisierul sortat este lasat in acest spatiu.
6. Aceasta necesita cel putin suficienta memorie pentru a tine trei inregistrari, dar va functiona mai rapid daca este prevazuta cu mai multa memorie.
7. A apelat tmpfile () pentru a crea cate patru fisiere temporare la un moment dat.
8. Fisierul nesortat este citit secvential, iar fisierul sortat este scris secvential. Prin urmare, acestea pot fi casete, fluxuri de I / O sau alte dispozitive strict secventiale.

Apelul pentru functii este dupa cum urmeaza:

result = merge_sort(unsorted_file, sorted_file, read, write, compare,
       pointer, max_record_size, block_size, pcount);

Programul apelant trebuie sa furnizeze urmatorii parametri:

FILE *unsorted_file;

Un pointer de fisier pentru a fi sortat fisierul. Fisierul trebuie sa fi fost deschis cu succes pentru citire, iar pointerul fisierului trebuie pozitionat la inceputul fisierului.

FILE *sorted_file;

Un pointer de fisier pentru fisierul sortat. Fisierul trebuie sa fi fost deschis cu succes pentru scriere, iar pointerul fisierului trebuie sa fie pozitionat la inceputul fisierului.

int (*read)();

O functie care citeste o singura inregistrare.

int (*write)();

O functie care scrie o singura inregistrare.

int (*compare)();

O functie care compara doua inregistrari.

void *pointer;

Un pointer definit de utilizator care va fi trecut la functiile (* citire) (), (* write) () si (* compare) () functioneaza atunci cand sunt apelate.

unsigned max_record_size;

Numarul maxim de octeti dintr-o inregistrare, atunci cand este citit in memorie. Acest lucru nu trebuie sa fie acelasi cu dimensiunea inregistrarii cand se afla intr-un fisier.

unsigned long block_size;

Numarul de inregistrari care vor fi sortate in memorie sau 1L daca nu se utilizeaza sortarea de memorie.

unsigned long *pcount;

Un pointer la o variabila pentru a primi numarul de inregistrare (daca sortarea are succes) sau NULL daca aceasta informatie nu trebuie returnata.

Functia returneaza urmatoarele valori:

int result;

Result code:

0 pentru o sortare reusita

1 pentru memorie insuficienta

2 pentru o eroare de creeare a fisierului

3 pentru o eroare de scriere a fisierului

Fisierele nesortate si sortate nu vor fi derulate sau inchise. Fiecare fisier va fi lasat deschis, cu pointerul fisierului pozitionat la sfarsitul fisierului. Cu toate acestea, daca cei doi indicatori de fisiere sunt identici, fisierul va fi reincarcat si inregistrarile sortate vor fi scrise peste el.

Functia (* citi) () este apelata de merge_sort () dupa cum urmeaza si trebuie sa citeasca o inregistrare de fiecare data cand este apelata (cu exceptia cazului in care se detecteaza sfarsitul fisierului nesortat):

n = (*read)(fp, buffer, pointer);
	

FILE *fp;

Un pointer de fisier pentru fisierul nesortat sau un fisier temporar creat prin apelarea tmpfile ().

void *buffer;

Un pointer la un buffer pentru a primi o inregistrare. Acest tampon poate detine cel mult max_record_size octeti.

void *pointer;

O copie a indicatorului a trecut ca argument la merge_sort ().

int n;

Numarul de octeti din inregistrare sau zero in cazul in care sa incercat citirea dupa sfarsitul fisierului nesortat.

Cand aceasta functie revine la zero, nu va mai fi chemata pentru acelasi fisier. Nu se va face nici o incercare de a citi trecutul la sfarsitul unui fisier temporar.

O inregistrare mai mare decat dimensiunea maxima specificata trebuie sa fie trunchiata sau tratata intr-un alt mod adecvat. Functia va esua catastrofic daca tamponul este permis sa depaseasca sau daca valoarea returnata de (* read) ()
este mai mare decat dimensiunea maxima a inregistrarii.

Formatul inregistrarii poate fi modificat atunci cand este citit in memorie, cu conditia ca:

1. modificarile sunt compatibile cu functiile (* write) () si (* compare) (), si

2. valoarea returnata de functia (* read) () trebuie sa fie numarul de octeti din inregistrare in timp ce se afla in memoria tampon.

De exemplu, terminatorul de linie \ r \ n in DOS / Windows poate fi convertit in \ n atunci cand este citit in memorie.

Functia (* write) () este chemata dupa cum urmeaza si trebuie sa scrie o inregistrare de fiecare data cand se numeste:

n = (*write)(fp, buffer, pointer);

FILE *fp;

Un pointer de fisier pentru fisierul nesortat sau un fisier temporar creat prin apelarea tmpfile().

void *buffer;

Un pointer la un buffer pentru a primi o inregistrare. Acest tampon poate detine cel mult max_record_size octeti(*read)().

void *pointer;

O copie a indicatorului a trecut ca argument la merge_sort  ().

int n;

Numarul de octeti din inregistrare sau zero in cazul in care sa incercat citirea dupa sfarsitul fisierului nesortat.

Observati ca lungimea inregistrarii nu este trecuta ca parametru. Trebuie sa fie continuta, explicit sau implicit, in inregistrarea insasi sau intr-un alt loc accesibil functiei (* write) ().

Functia (* compare) () este apelata pentru a compara doua inregistrari, dupa cum urmeaza:

n = (*compare)(p, q, pointer);
			

void *p;

Un pointer la un tampon care contine prima inregistrare, citit in memorie de (* read) ().

void *q;

Un pointer catre un buffer care contine cea de-a doua inregistrare, citit in memorie de (* read) ().

void *pointer;

O copie a indicatorului a trecut ca argument la merge_sort ().

int n;

Rezultatul compararii, dupa cum urmeaza:

• >0 daca * p urmeaza sa fie dupa * q in ordinea sortata
• <0 daca * p trebuie sa fie inainte de * q in ordinea sortata
• 0 daca ordinea * p si * q este irelevanta

Tipul se desfasoara dupa cum urmeaza:

1. Inregistrarile sunt citite din fisierul nesortat si scrise in doua fisiere temporare in blocuri. Fiecare bloc contine numarul de inregistrari specificate de argumentul block_size (cu exceptia ultimului bloc, care poate contine mai putine inregistrari) si este sortat in memorie apeland link_list_sort () inainte de a fi scris intr-un fisier temporar.
2. Fisierele temporare sunt apoi sortate prin fuziunea blocurilor intr-un numar de pasi. In fiecare pas, blocurile din doua fisiere sursa sunt fuzionate in blocuri care contin doua ori mai multe inregistrari si sunt scrise in doua fisiere de iesire. Procesul se termina atunci cand dimensiunea blocului este egala cu sau depaseste dimensiunea fisierului si toate inregistrarile sunt intr-un singur fisier, care este fisierul sortat.

Tipul poate esua daca

1. un apel la malloc () returneaza NULL deoarece nu exista suficienta memorie, sau
2. un apel la tmpfile () returneaza NULL deoarece exista prea multe fisiere deschise, sau
3. un apela pe (* write) () intoarce zero pentru ca nu exista spatiu suficient pe disc.

Indiferent daca sortarea are succes sau nu, toate blocurile de memorie alocate vor fi dezalocate si toate fisierele temporare vor fi inchise si sterse. Daca sortarea nu reuseste, indicatorii de fisiere pentru fisierele nesortate si sortate vor fi lasate oriunde s-ar intampla.

Functia merge_sort () este reintrodusa in cazul in care functiile pe care aceasta le solicita sunt reintroduse:

• (*compare)()
• fclose()
• free()
• malloc()
• memcpy()
• (*read)()
• rewind()
• tmpfile()
• (*write)()

Sub DOS / Windows, tmpfile () creeaza un fisier BINARY. Cu toate acestea, aceasta nu creeaza probleme, desi fisierele nesortate si sortate sunt fisiere text, deoarece DOS / Windows gestioneaza conversiile intr-o maniera consecventa.

Daca spatiul de pe disc este extrem de strans, sortarea poate fi modificata pentru a utiliza spatiul ocupat de fisierul nesortat. Fisierul nesortat, fisierele temporare si fisierul sortat pot apoi sa se potriveasca intr-un spatiu de aproximativ doua ori mai mare decat fisierul nesortat. Pentru a face aceasta modificare, introduceti doar codul pentru a sterge fisierul nesortat dupa ce a fost citit. Retineti ca daca aceasta tehnica este utilizata, fisierele sortate si nesortate trebuie sa fie diferite si structura de trecere a argumentului poate deveni putin mai eleganta, deoarece apelul pentru stergerea unui fisier necesita de obicei caietul de sarcini, nu doar un indicator al fisierului.

Functia merge_sort () nu este stabila; Adica nu pastreaza pozitiile relative ale doua inregistrari pentru care functia (* compare) () revine la zero. Functia stable_merge_sort () are aceasta proprietate. Cu toate acestea, caracteristica suplimentara are un pret: un numar de inregistrare de patru octeti este adaugat fiecarei inregistrari in timp ce se afla in memorie sau intr-un fisier temporar. Acest lucru creste cerintele de disc si de memorie, cu o valoare substantiala daca inregistrarile sunt mici.

Utilitarul SORT ilustreaza folosirea lui stable_merge_sort (). Este un filtru DOS sau UNIX care sorteaza liniile unui fisier text. Lungimea maxima a liniei este MAX_LINE caractere, fara a include returul de carucior si feedul de linie la sfarsitul fiecarei linii. Utilitarul va intrerupe sortarea si va afisa un mesaj de eroare daca citeste o linie care contine mai mult de MAX_LINE caractere. Valoarea MAX_LINE este setata la 255, dar poate fi modificata prin recompilarea utilitarului.

Utilitatea este chemata dupa cum urmeaza:

SORT  <unsorted_file  >sorted_file  M  N
				

Sortarea include coloanele numarul M pana la N, inclusiv, unde coloana din stanga este numarul zero. Daca N este omisa, sortarea include coloana M si toate coloanele din partea dreapta a acesteia. Daca sunt omise atat M, cat si N, toate coloanele sunt folosite in sortare.

O linie care contine mai putine coloane decat N + 1 este sortata ca si cum ar fi captusita cu nuluri la capatul drept.

Caracterele sunt clasificate dupa codurile lor ASCII, considerate octeti UNSIGNED.

Acest pachet solicita un alt pachet:

• Linked-List Memory Sort

Cod sursa in format text:

• mergesor.c
• smergeso.c
• sort.c