Pr-1st-1.1-m09-Slajd06

Sortowanie rozproszone – przykład

Każdy zprocesów $P_{i+1}$ ma za zadanie uporządkować (posortować) przypisany mu na wstępie zbiór <math<\mathcal{X}_{i+1}</math> i wyznaczyć element $min_{i+1}$.

Następnie procesy wysyłają elementy $min_{i+1}$ do swoich lewych sąsiadów ioczekują na odpowiedź zawierającą $max_{i}$. Po otrzymaniu wiadomości zwartością $min_{i+1}$, a przed wysłaniem odpowiedzi, proces $P_{i}$ wyznacza nowy element $max_{i}$.

W ogólności, nowo wyznaczony $max_{i}$ może być równy otrzymanemu ostatnio $min_{i+1}$. Następnie każdy z procesów wysyła odpowiedź ze swoim elementem maksymalnym do prawego sąsiada. Po otrzymaniu odpowiedzi, procesy znów sortują zbiory <math<\mathcal{X}_{i+1}</math> i jeśli wwyniku tego sortowania wartość $min_{i+1}$ różnić się będzie od poprzednio wysłanego elementu minimalnego, to proces wysyła ten nowy element $min_{i+1}$ do lewego sąsiada.

Cel sortowania rozproszonego zostaje osiągnięty, gdy uporządkowany zostanie każdy zbiór <math<\mathcal{X}_{i}</math>, a ponadto dla każdego $i:1\leq i\leq n-1,max_{i}<min_{i+1}$.

<< Poprzedni slajd | Spis treści | Następny slajd >>