644 matches
-
orice rețea de comparare este o rețea de sortare dar cea din figura 2 este. Pentru a vedea de ce, observați că după timpul 1, cea mai mică dintre cele patru valori de intrare se obține fie la ieșirea superioară a comparatorului A sau la cea superioară a comparatorului B. De aceea,după timpul 2, se va regăsi la ieșirea superioară a comparatorului C. O explicație similară dovedește că după timpul 2 valoarea maximă a celor patru valori de intrare va fi
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de sortare dar cea din figura 2 este. Pentru a vedea de ce, observați că după timpul 1, cea mai mică dintre cele patru valori de intrare se obține fie la ieșirea superioară a comparatorului A sau la cea superioară a comparatorului B. De aceea,după timpul 2, se va regăsi la ieșirea superioară a comparatorului C. O explicație similară dovedește că după timpul 2 valoarea maximă a celor patru valori de intrare va fi obținută la ieșirea inferioară a comparatorului D.
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
după timpul 1, cea mai mică dintre cele patru valori de intrare se obține fie la ieșirea superioară a comparatorului A sau la cea superioară a comparatorului B. De aceea,după timpul 2, se va regăsi la ieșirea superioară a comparatorului C. O explicație similară dovedește că după timpul 2 valoarea maximă a celor patru valori de intrare va fi obținută la ieșirea inferioară a comparatorului D. Mai rămâne ca comparatorul E să plaseze cele două valori din mijloc pe pozițiile
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
a comparatorului B. De aceea,după timpul 2, se va regăsi la ieșirea superioară a comparatorului C. O explicație similară dovedește că după timpul 2 valoarea maximă a celor patru valori de intrare va fi obținută la ieșirea inferioară a comparatorului D. Mai rămâne ca comparatorul E să plaseze cele două valori din mijloc pe pozițiile corecte, ceea ce se întâmplă în pasul 3. O rețea de comparare poate fi asemănată cu o procedură în care se specifică câte comparații trebuie să
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
după timpul 2, se va regăsi la ieșirea superioară a comparatorului C. O explicație similară dovedește că după timpul 2 valoarea maximă a celor patru valori de intrare va fi obținută la ieșirea inferioară a comparatorului D. Mai rămâne ca comparatorul E să plaseze cele două valori din mijloc pe pozițiile corecte, ceea ce se întâmplă în pasul 3. O rețea de comparare poate fi asemănată cu o procedură în care se specifică câte comparații trebuie să survină dar nu cu o
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
Spre exemplificare propun rețeaua din figura 4: Se poate observa că și rețeaua din figura 5 poate fi considerată o rețea de sortare bazată pe sortare prin inserție: Interesant de remarcat ar fi să arătăm că dacă vom insera un comparator oriunde într-o rețea de sortare, atunci rețeaua obținută nu va sorta corect orice secvență de intrare. Astfel pentru a întări această supoziție aplicăm rețelei din figura 2 la intrare secvența {9,6,5,2} și după primii doi comparatori
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
nu va sorta corect orice secvență de intrare. Astfel pentru a întări această supoziție aplicăm rețelei din figura 2 la intrare secvența {9,6,5,2} și după primii doi comparatori din rețea, respectiv (1,2) și (3,4) adăugam comparatorul (2,3Ă. Aceasta va avea ca efect aducerea valorii 2 (minimul din rețea) pe conductorul 2, iar până la finalul rețelei nu va exista nici un comparator (1,2). Astfel valoarea minimă din rețea va fi în final pe conductorul 2. În
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
2} și după primii doi comparatori din rețea, respectiv (1,2) și (3,4) adăugam comparatorul (2,3Ă. Aceasta va avea ca efect aducerea valorii 2 (minimul din rețea) pe conductorul 2, iar până la finalul rețelei nu va exista nici un comparator (1,2). Astfel valoarea minimă din rețea va fi în final pe conductorul 2. În figura 6 putem observa acest aspect: Un alt aspect de semnalat ar fi că o rețea de comparare cu n intrări și c comparatori se
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
pentru a dovedi că rețeaua sortează corespunzător secvențe de orice alte valori. Demonstrația principiului zero-unu se sprijină pe noțiunea de funcție monoton crescătoare . Demonstrație. Mai întâi vom demonstra afirmația că, dacă f este o funcție monoton crescătoare, atunci un singur comparator cu intrările f(x) si f(y) furnizează la ieșire f(min(x,y)) și f(max(x,y)). Vom folosi un raționament prin inducție pentru a demonstra această lemă. Pentru a demonstra afirmația, se consideră un comparator a cărui
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
un singur comparator cu intrările f(x) si f(y) furnizează la ieșire f(min(x,y)) și f(max(x,y)). Vom folosi un raționament prin inducție pentru a demonstra această lemă. Pentru a demonstra afirmația, se consideră un comparator a cărui valori de intrare sunt x și y, ieșirea superioară a comparatorului este min(x,y) iar ieșirea inferioară este max(x,y). Presupunând că acum aplicăm f(x) și f(y) la intrările comparatorului, după cum se arată în
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
f(min(x,y)) și f(max(x,y)). Vom folosi un raționament prin inducție pentru a demonstra această lemă. Pentru a demonstra afirmația, se consideră un comparator a cărui valori de intrare sunt x și y, ieșirea superioară a comparatorului este min(x,y) iar ieșirea inferioară este max(x,y). Presupunând că acum aplicăm f(x) și f(y) la intrările comparatorului, după cum se arată în figura 7. în urma operației de comparare la ieșirea superioară a comparatorului se obține
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
afirmația, se consideră un comparator a cărui valori de intrare sunt x și y, ieșirea superioară a comparatorului este min(x,y) iar ieșirea inferioară este max(x,y). Presupunând că acum aplicăm f(x) și f(y) la intrările comparatorului, după cum se arată în figura 7. în urma operației de comparare la ieșirea superioară a comparatorului se obține valoarea min(f(x), f(y)) iar la ieșirea inferioară valoarea max(f(x), f(y)). De vreme ce f este monoton crescătoare, x ≤ y
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
superioară a comparatorului este min(x,y) iar ieșirea inferioară este max(x,y). Presupunând că acum aplicăm f(x) și f(y) la intrările comparatorului, după cum se arată în figura 7. în urma operației de comparare la ieșirea superioară a comparatorului se obține valoarea min(f(x), f(y)) iar la ieșirea inferioară valoarea max(f(x), f(y)). De vreme ce f este monoton crescătoare, x ≤ y implică f(x) ≤ f(y). Corespunzător avem identitățile: min(f(x), f(y)) = f(min
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
valoarea max(f(x), f(y)). De vreme ce f este monoton crescătoare, x ≤ y implică f(x) ≤ f(y). Corespunzător avem identitățile: min(f(x), f(y)) = f(min(x,y)) , max(f(x), f(y)) = f(max(x,y)) . Astfel, comparatorul produce valorile f (min(x,y)) și f (max(x,y)) când f (x) și f (y) se aplică la intrările lui, ceea ce completează demonstrația. Se poate face observația că dacă se aplică o funcție monoton crescătoare unei secvențe sortate
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
de intrare ai. Rezultatul apare banal: când f(a) este aplicat rețelei firul de intrare va primi în mod automat valoarea f(aiă, pentru pasul inductiv se consideră un fir de adâncime d, unde d ≥1. Firul este ieșirea unui comparator de adâncime d, și firul de intrare în acest 18 comparator are o adâncime strict mai mică decât d. Prin inducție, de aceea, dacă firele de intrare în comparator poartă valorile ai și aj când se aplică secvența de intrare
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
rețelei firul de intrare va primi în mod automat valoarea f(aiă, pentru pasul inductiv se consideră un fir de adâncime d, unde d ≥1. Firul este ieșirea unui comparator de adâncime d, și firul de intrare în acest 18 comparator are o adâncime strict mai mică decât d. Prin inducție, de aceea, dacă firele de intrare în comparator poartă valorile ai și aj când se aplică secvența de intrare a atunci ele poartă valorile f(ai) și f(aj) când
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
fir de adâncime d, unde d ≥1. Firul este ieșirea unui comparator de adâncime d, și firul de intrare în acest 18 comparator are o adâncime strict mai mică decât d. Prin inducție, de aceea, dacă firele de intrare în comparator poartă valorile ai și aj când se aplică secvența de intrare a atunci ele poartă valorile f(ai) și f(aj) când secvența de intrare f(a) este aplicată. Conform afirmației noastre anterioare, firele de ieșire ale acestui comparator vor
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
în comparator poartă valorile ai și aj când se aplică secvența de intrare a atunci ele poartă valorile f(ai) și f(aj) când secvența de intrare f(a) este aplicată. Conform afirmației noastre anterioare, firele de ieșire ale acestui comparator vor purta f(min(ai, aj)) și f(max(ai, aj)). De vreme ce ele poartă min(ai, aj) și max(ai, aj) atunci când secvența de intrare este a, lema este dovedită. Ca un exemplu de aplicare a lemei 1, figura 8
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
n-1 secvențe nu ar fi sortate corect atunci unul din comparatori generează la ieșirea superioară numărul mai mare iar la ieșirea inferioară pe cel mic. Deci, la aplicarea secvenței {n, n-1,...,1} numere ce vor intra în acel comparator sortate descrescător, vor ieși tot sortate descrescător. Observăm că rețeaua de comparare din figura 9 poate fi considerată pe baza principiului zero- unu o rețea de sortare, deoarece toate secvențele cu patru elemente formate doar din 1 și 0 : {0
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
1,1} {0,1,1,1} {1,1,1,1}, sortate. O remarcă pe care o putem face(se poate observa și din figura 9Ă este ca o rețea de sortare cu n intrări trebuie să conțină cel puțin un comparator între liniile i și i+1 pentru orice i = 1, 2, ..., n-1. Întradevăr presupunând că între conductoarele i și j (i<jă nu există nici un comparator pe tot parcursul rețelei și aplicând la intrare o secvență în care elementul
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
o rețea de sortare cu n intrări trebuie să conțină cel puțin un comparator între liniile i și i+1 pentru orice i = 1, 2, ..., n-1. Întradevăr presupunând că între conductoarele i și j (i<jă nu există nici un comparator pe tot parcursul rețelei și aplicând la intrare o secvență în care elementul de pe poziția i este mai mare decât elementul de pe poziția j, la ieșirea din rețea vom avea pe pozițiile i și j două elemente nesortate. Deci nu
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
din rețea vom avea pe pozițiile i și j două elemente nesortate. Deci nu poate fi vorba despre o rețea de sortare. De aici, presupunerea făcută este falsă și deci întro rețea de sortare trebuie să avem cel puțin un comparator între oricare două conductoare i și j. Secțiunea 3 O rețea de sortare bitonică Primul pas în construirea unei rețele de sortare eficiente este construirea unei rețele de comparare care poate sorta orice secvență bitonică, o secvență care fie crește
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 intrări {a1, a2, a3,..., an} și n niveluri de comparatori
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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 i = 1,2, 3, . . . , n și d = 1, 2, . . . , n, linia i este conectată printr- un comparator cu adâncimea d la linia j = i + (-1Ăi+d dacă 1 ≤ j ≤ n. În figura 18 putem analiza așa numita rețea de permutări cu n intrări și n ieșiri ce are comutatori care permit conectarea intrărilor cu ieșirile după toate
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]
-
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) ș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
REŢELE DE SORTARE APLICAŢIE by ŞTEFAN OLTEAN () [Corola-publishinghouse/Science/91709_a_107360]