PDA

View Full Version : سوال: اصل صفر و یک



قله بلند
یک شنبه 14 آذر 1389, 14:12 عصر
سلام دوستان

اصل صفر و یک می گه اگر یک شبکه مقایسه بتواند 2 به قوه n دنباله ای ممکن از ورودی های 0 و 1 را مرتب کند می تواند هر دنباله دلخواه از اعداد را به درستی مرتب کند.

حالا فرض کنید که یک شبکه مقایسه گر دارید که متشکل از 4 سیم، 4 ورودی و 6 مقایسه گر است به قسمی که:

به تصویر نگاه کنید.(هر چی تلاش می کنم نمی تونم تصویر رو ضمیمه کنم و علت عمده اون به خاطر کندی زیاده سایت هست)

فقط یه توضیحی بدم که این شبکه مقایسه گر ، دارای 4 عمق هست.
در عمق اول: 1 و 2 با هم و 3 و 4 با هم مقایسه می شوند.(منظور ورودی است)
در عمق دوم: 1 و 3 با هم و 2 و 4 با هم مقایسه می شوند.
در عمق سوم: 2 و 3 با هم مقایسه می شوند.
در عمق چهارم: 1 و 2 با هم و 3 و 4 با هم مقایسه می شوند.

و در نهایت این 4 ورودی، مرتب می شوند.

حالا چگونه می توان با اصل صفر و یک ثابت کرد که این شبکه مقایسه گر، یک شبکه مرتب سازی است؟ :متفکر: