3,716 matches
-
BITONIC-SORTER[n] constă în SEMICLEANER[n], care, conform lemei 3, furnizează două secvențe bitonice având dimensiunea pe jumătate astfel că fiecare element din jumătatea de sus este cel puțin la fel de mic decât orice element din jumătatea inferioară. Astfel putem completa sortarea folosind două copii ale BITONIC- SORTER[n/2] pentru a sorta cele două jumătăți recursiv. În figura 12 (aă, recursia este arătată explicit iar în figura 12 (bă, recursia a fost utilizată pentru a arăta micile semi-cleaner-uri care compun progresiv
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
dacă valoarea minimă din cea de-a doua secvență este 1 atunci toate elementele din ce- a de-a doua secvență sunt 1, deci ce-a de-a doua secvență este curată. Secțiunea 4 Rețeaua de interclasare Rețeaua noastră de sortare va fi construită din rețele de interclasare, care sunt rețele care pot asambla două secvențe sortate de intrare într-o singură secvență sortată de ieșire. Vom modifica BITONIC-SORTER[n] pentru a crea o rețea cu interclasare MERGER[n]. Ca și
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
zero-unu sortată X = 00000111 și Y = 00001111, inversăm Y și obținem YR = 11110000. Concatenând X și YR obținem 0000011111110000, care este bitonică. Astfel pentru a asambla cele două secvențe de intrare X și Y, este suficient pentru a face o sortare bitonică asupra lui X concatenat cu YR. Putem construi MERGER[n] modificând primul semi-cleaner al BITONIC-SORTER[n]. Ideea este să efectuăm o inversare implicită a celei de-a doua jumătate de intrări. Fiind date două secvențe sortate {a1, a2, . . . , an
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
Ideea este să efectuăm o inversare implicită a celei de-a doua jumătate de intrări. Fiind date două secvențe sortate {a1, a2, . . . , an/2} și {an/2+1, an/2+2, . . . , an} pentru a fi interclasate, dorim să obținem efectul sortării bitonice a secvenței {a1, a2, . . . , an/2, an, an-1, . . . , an/2+1}. De vreme ce semi-cleaner-ul sortatorului BITONIC-SORTER[n] compară intrările i și n/2 + i, pentru i = 1, 2, . . . , n/2, noi facem ca primul etaj al rețelei cu interclasare să
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
prin interclasare rezultată este prezentata în figura 14. Doar primul etaj al lui MERGER[n] este diferit de BITONICSORTER[n]. Corespunzător adâncimea lui MERGER[n] este lg n, aceeași ca cea a lui BITONIC-SORTER[n]. Secțiunea 5 O rețea de sortare Acum avem elementele necesare pentru a construi o rețea care poate sorta orice secvență de intrare. Rețeaua de sortare SORTER[n] folosește rețeaua cu interclasare pentru a implementa o versiune paralelă a algoritmului de sortare cu interclasare (merge sortă . Modul
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
n]. Corespunzător adâncimea lui MERGER[n] este lg n, aceeași ca cea a lui BITONIC-SORTER[n]. Secțiunea 5 O rețea de sortare Acum avem elementele necesare pentru a construi o rețea care poate sorta orice secvență de intrare. Rețeaua de sortare SORTER[n] folosește rețeaua cu interclasare pentru a implementa o versiune paralelă a algoritmului de sortare cu interclasare (merge sortă . Modul de construcție și operațiile de pe o rețea de sortare sunt ilustrate in figura 15. Figura 15 (a) arată construirea
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
Secțiunea 5 O rețea de sortare Acum avem elementele necesare pentru a construi o rețea care poate sorta orice secvență de intrare. Rețeaua de sortare SORTER[n] folosește rețeaua cu interclasare pentru a implementa o versiune paralelă a algoritmului de sortare cu interclasare (merge sortă . Modul de construcție și operațiile de pe o rețea de sortare sunt ilustrate in figura 15. Figura 15 (a) arată construirea recursivă a lui SORTER[n]. Cele n elemente de intrare sunt sortate folosind recursiv două copii
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
rețea care poate sorta orice secvență de intrare. Rețeaua de sortare SORTER[n] folosește rețeaua cu interclasare pentru a implementa o versiune paralelă a algoritmului de sortare cu interclasare (merge sortă . Modul de construcție și operațiile de pe o rețea de sortare sunt ilustrate in figura 15. Figura 15 (a) arată construirea recursivă a lui SORTER[n]. Cele n elemente de intrare sunt sortate folosind recursiv două copii ale lui SORTER[n/2] pentru a sorta (în paralel) două subsecvențe de lungime
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
care asamblează perechi de secvențe de 2k-1elemente sortate pentru a produce secvențe sortate de lungime 2k. La nivelul etajului final este produsă o secvență sortată constând din toate valorile de intrare. Poate fi arătat prin inducție că această rețea de sortare sortează secvențe zero-unu , și în consecință, conform principiului zero-unu (Teorema 2), poate sorta valori arbitrare. Putem analiza adâncimea unei rețele de sortare recursiv. Adâncimea D(n) a lui SORTER[n] este adâncimea D(n/2) a SORTER[n/2] (sunt
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
o secvență sortată constând din toate valorile de intrare. Poate fi arătat prin inducție că această rețea de sortare sortează secvențe zero-unu , și în consecință, conform principiului zero-unu (Teorema 2), poate sorta valori arbitrare. Putem analiza adâncimea unei rețele de sortare recursiv. Adâncimea D(n) a lui SORTER[n] este adâncimea D(n/2) a SORTER[n/2] (sunt două copii ale lui SORTER[n/2], dar ele operează în paralel) plus adâncimea lgn a lui MERGER[n]. Ca urmare, adâncimea
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
n/2k copii de rețele MERGER[2k] modificând adâncimea rețelei SORTER[n] cu lg2k, adică cu k. Deci adâncimea totală a rețelei SORTER[n] este 1+2+...+lgn = (lgn)(lgn + 1)/2. Este bine de reținut că o rețea de sortare este considerată și o rețea de transpoziții dacă fiecare comparator conectează linii adiacente așa cum se observă în figura 16 pentru rețeaua de sortare bazată pe metode de sortare prin inserare: Un alt tip de rețea de sortare pară-impară cu n
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
n] este 1+2+...+lgn = (lgn)(lgn + 1)/2. Este bine de reținut că o rețea de sortare este considerată și o rețea de transpoziții dacă fiecare comparator conectează linii adiacente așa cum se observă în figura 16 pentru rețeaua de sortare bazată pe metode de sortare prin inserare: Un alt tip de rețea de sortare pară-impară cu n intrări {a1, a2, a3,..., an} și n niveluri de comparatori este considerată tot o rețea de transpoziții. Figura 17 ilustrează o rețea de
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
lgn)(lgn + 1)/2. Este bine de reținut că o rețea de sortare este considerată și o rețea de transpoziții dacă fiecare comparator conectează linii adiacente așa cum se observă în figura 16 pentru rețeaua de sortare bazată pe metode de sortare prin inserare: Un alt tip de rețea de sortare pară-impară cu n intrări {a1, a2, a3,..., an} și n niveluri de comparatori este considerată tot o rețea de transpoziții. Figura 17 ilustrează o rețea de transpoziții pară-impară cu 8 intrări
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
o rețea de sortare este considerată și o rețea de transpoziții dacă fiecare comparator conectează linii adiacente așa cum se observă în figura 16 pentru rețeaua de sortare bazată pe metode de sortare prin inserare: Un alt tip de rețea de sortare pară-impară cu n intrări {a1, a2, a3,..., an} și n niveluri de comparatori este considerată tot o rețea de transpoziții. Figura 17 ilustrează o rețea de transpoziții pară-impară cu 8 intrări: 39 După cum se poate vedea în figura 17, pentru
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
Construcția recursivă a rețelei P8 formată din 8 comutatori și două rețele P4. Comutatorii lui P4 sunt setați pentru a realiza permutarea pi= {4, 7, 3, 5, 1, 6, 8, 2}. Note bibliografice Knuth conține o discuție despre rețele de sortare și trasează istoria lor. Aparent ele au fost prima dată explorate în 1954 de P. N. Armstrong, R. J. Nelson, si D. J. O'Connor. În primii ani ai lui 60, K. E. Batcher a descoperit prima rețea capabilă să
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
un sortator bitonic de adâncime O(lgn)similar cu cel prezentat în secțiunea 3 Knuth atribuie principiul zerounu lui W. G. Bouricius (1954), care l-a demonstrat în cazul arborilor de decizie. Pentru mult timp întrebarea dacă o rețea de sortare cu adâncimea O(lgn) exista a rămas deschisă. În 1983, răspunsul a fost arătat ca fiind încă nesatisfăcător. Rețele de sortare de tip AKS (numite după Ajtai, Komlós, and Szemerédi care le-au descoperit) pot sorta n numere pe adâncimea
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
Bouricius (1954), care l-a demonstrat în cazul arborilor de decizie. Pentru mult timp întrebarea dacă o rețea de sortare cu adâncimea O(lgn) exista a rămas deschisă. În 1983, răspunsul a fost arătat ca fiind încă nesatisfăcător. Rețele de sortare de tip AKS (numite după Ajtai, Komlós, and Szemerédi care le-au descoperit) pot sorta n numere pe adâncimea O(lgn) folosind O(nlgn) comparatoare. Din păcate numărul de constante ( ascunse în notația O) este foarte mare (multe, multe mii
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
AKS (numite după Ajtai, Komlós, and Szemerédi care le-au descoperit) pot sorta n numere pe adâncimea O(lgn) folosind O(nlgn) comparatoare. Din păcate numărul de constante ( ascunse în notația O) este foarte mare (multe, multe mii) și această sortare nu poate fi considerată practică. Secțiunea 6 Reprezentarea grafică a rețelelor de sortare În sens aplicativ mi-am propus să realizez un program care să deseneze astfel de tipuri de rețele prezentate în partea teoretică. Programul în cauză este realizat
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
n numere pe adâncimea O(lgn) folosind O(nlgn) comparatoare. Din păcate numărul de constante ( ascunse în notația O) este foarte mare (multe, multe mii) și această sortare nu poate fi considerată practică. Secțiunea 6 Reprezentarea grafică a rețelelor de sortare În sens aplicativ mi-am propus să realizez un program care să deseneze astfel de tipuri de rețele prezentate în partea teoretică. Programul în cauză este realizat în Delphi deoarece prezintă multiple avantaje în abordarea aspectelor de grafică, cu antetul
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de grafică, cu antetul "Sorting Network" conținând subprogramele 'main.pas' și 'view.pas' care pun în evidență cele două tipuri de ferestre respectiv de control și vizualizare a rețelelor precum și un subprogram intitulat 'utils.pas' ce atestă implementarea funcțiilor de sortare și a funcțiilor de calcul, necesare programului principal: program Sorting Network; În partea de program 'main.pas' pentru început am definit tipul de fereastră de control cu tot cu obiectele de pe ea, meniul principal cu butoanele aferente acestuia. În vederea desenării
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
design în care unele butoane pot fi funcționabile iar altele devin funcționabile după ce a fost încărcat un fișier de valori sau o rețea. Procedura care se apelează la apăsarea butonului “Sorting network” va permite realizarea de fapt a rețelei de sortare finală. În cadrul acestei proceduri există condiția de verificare cu privire la încărcarea unui fișier de valori, care în caz afirmativ reface toate firele cu valorile de rezervă și șterge toate comparatoarele, prin secvența: De fapt toate acestea se regăsesc în
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
comparatoarele, prin secvența: De fapt toate acestea se regăsesc în toate procedurile din care se apelează un tip de rețea, drept pentru care le-am prezentat numai pentru procedura redată anterior. După această parte urmează apelul procedurilor specifice, ce fac sortarea și desenarea rețelei în cauză: Sorter(1,nrin); DrawNet; end În cazul în care condiția de verificare cu privire la încărcarea unui fișier de valori nu este satisfăcută atunci sunt avertizat de faptul că nu am introdus datele necesare: else
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
toți comparatorii care au adâncimea dată ca parametru apare în modul următor: Pe lângă funcțiile ce sunt implementate în cadrul programului și care au fost prezentate anterior, în continuare vom pune în discuție procedurile utilizate dintre care, pentru început, cea de sortare a comparatorilor: O altă procedură ce poate fi apelată și care a putut fi observată în prezentările anterioare se referă la posibilitatea adăugării unui comparator între conductoarele a și b, calculului adâncimii la care se află comparatorul precum și a valorilor
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
b, calculului adâncimii la care se află comparatorul precum și a valorilor noi pe care acesta le induce conductoarelor: Modul de implementare a semi-cleanerului poate fi remarcată prin utilizarea procedurii următoare, în care își fac apariția și procedurile de adăugare și sortare a comparatorilor: Algoritmul de sortare bitonică poate fi de asemenea pus în evidență prin secvența: Algoritmul de sortare prin interclasare în care este prezentă adăugarea, sortarea comparatorilor precum și sortarea bitonică, se poate evidenția în cele ce urmează: Modul de implementare
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
se află comparatorul precum și a valorilor noi pe care acesta le induce conductoarelor: Modul de implementare a semi-cleanerului poate fi remarcată prin utilizarea procedurii următoare, în care își fac apariția și procedurile de adăugare și sortare a comparatorilor: Algoritmul de sortare bitonică poate fi de asemenea pus în evidență prin secvența: Algoritmul de sortare prin interclasare în care este prezentă adăugarea, sortarea comparatorilor precum și sortarea bitonică, se poate evidenția în cele ce urmează: Modul de implementare a algoritmului de sortare ce
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]