|
[[پرونده:SimpleSortingNetwork2.svg|بندانگشتی|250px|یک شبکه مرتب‌سازی ساده شامل چهار سیم و پنج اتصال دهنده]]
شبکه [[مرتب‌سازی]] یک مدل انتزاعی ریاضی شامل شبکه‌ای از سیم‌ها و واحدهای [[مقایسه کنندهمقایسه‌کننده]] است که برای [[مرتب‌سازی رشته‌ای]] از اعداد از آن استفاده می‌شود. هر مقایسه کنندهمقایسه‌کننده دو سیم را به هم متصل می‌کند و مقادیر را با قرار دادن مقدار کوچکتر به یکی از سیم‌ها و مقدار بزرگتر به سیم دیگر، مرتب می‌کند. اصلی‌ترین تفاوت میان شبکه مرتب‌سازی و [[الگوریتم مرتب‌سازی]] این است که ترتیب مقایسه‌ها بدون در نظر گرفتن نتیجه مقایسه‌های قبلی، از قبل مشخص شده استشده‌است. استقلال میان ترتیب مقایسه‌ها برای اجرای موازی الگوریتم‌ها مفید خواهد بود. علی‌رغم سادگی مدل آن، تئوری مرتب‌سازی شبکه‌ای بسیار پیچیده و دارای مفاهیم عمیقی است.
== آشنایی مقدماتی ==
یک شبکه مرتب‌سازی شامل دو عنصر است، مقایسه کننده‌هامقایسه‌کننده‌ها و سیم‌ها. هر سیم دارای یک مقدار می‌باشد، و هر مقایسه کنندهمقایسه‌کننده دو سیم را به عنوان ورودی و خروجی می‌گیرد. زمانی که دو مقدار وارد مقایسه کنندهمقایسه‌کننده می‌شود، مقایسه کنندهمقایسه‌کننده مقدار کوچکتر را در سیم بالاتر، و مقدار بزرگتر را در سیم پایین قرار می‌دهد. به شبکه‌ای از سیم‌ها و مقایسه کننده‌هامقایسه‌کننده‌ها که به طوربه‌طور صحیح تمام مقادیر ورودی را به صورت صعودی مرتب کنند یک شبکه مرتب‌سازی گفته می‌شود.
مراحل انجام یک مرتب‌سازی شبکه‌ای ساده در شکل زیر نشان داده شده استشده‌است. فهم چگونگی صحیح عمل نمودن این شبکه مرتب‌سازی آسان است، این را مدنظر داشته باشید که مقایسه کننده‌هامقایسه‌کننده‌ها مقدار بزرگ را به سیم پایین و مقدار کوچک را به سیم بالا منتقل می‌کنند؛ و در نهایت آخرین مقایسه کنندهمقایسه‌کننده دو سیم میانی را مرتب می‌کند.
[[پرونده:SimpleSortingNetworkFullOperation.svg|650px]]
|}
ساختار این دو مرتب‌سازی شبکه‌ای بسیار شبیه یکدیگر است، با نمایش همزمانهم‌زمان روند انجام مقایسه‌ها توسط مقایسه کننده‌هامقایسه‌کننده‌ها عملاً می‌توان گفت که این دو یکی هستند.
{|
| [[پرونده:Six-wire-bubble-sorting-network.svg|200px|بندانگشتی|شبکه مرتب‌سازی حبابی]]
| [[پرونده:Six-wire-insertion-sorting-network.svg|200px|بندانگشتی|شبکه مرتب‌سازی درجی]]
| [[پرونده:Six-wire-pyramid-sorting-network.svg|200px|بندانگشتی|با مقایسه کننده‌هایمقایسه‌کننده‌های موازی، مرتب‌سازی درجی و حبابی مثل هم خواهند بود]]
|}
=== اصل صفر و یک ===
اثبات صحیح بودن بعضی از شبکه‌های مرتب‌سازی مثل شبکه مرتب‌سازی درجی و حبابی آسان است، اما همیشه اینگونهاین‌گونه نیست. برای یک شبکه n سیمه،n جایگشت از اعداد خواهیم داشت، و امتحان کردن تمام آنهاآن‌ها نیاز به زمان بسیار زیادی دارد، به خصوص در شبکه‌های بزرگتر. اما با استقاده از اصل صفر و یک تعداد دفعات امتحان به طوربه‌طور چشمگیری کاهش پیدا می‌کند.
اصل صفر و یک بیان می‌کند که یک شبکه مرتب‌سازی زمانی صحیح عمل کرده اگر بتواند رشته‌ای از صفرها و یک‌ها که تعدادشان <math>2^n</math> است مرتب کند. با استفاده از این اصل می‌توان تعداد تست‌های لازم برای مشخص کردن صحیح بودن شبکه را به طوربه‌طور چشمگیری کاهش داد، و هم چنین در ساختن شبکه‌های مرتب‌سازی مختلف مؤثر خواهد بود.
[[روش اثبات]] آن یک حالت خاص از نظریه بوریسیوس است که در سال ۱۹۴۵ توسط بوریسیوس اثبات شد.
== مرتب‌سازی بهینه ==
کارایی یک شبکه مرتب‌سازی را می‌توان با استفاده از اندازه کل آن (تعداد مقایسه کننده‌هایمقایسه‌کننده‌های استفاده شده)، یا با استفاده از عمقش (حداکثر تعداد مقایسه کننده‌هاییمقایسه‌کننده‌هایی که در مسیر یک ورودی به خروجی قرار دارند)، [[اندازه‌گیری]] کرد. بهترین شبکه مرتب‌سازی شناخته شده، شبکه AKS است که از حروف اول کاشفان آن، اجتا، کاملوس، و سمیردای گرفته شده استشده‌است. این شبکه دارای عمق {{math|O(log n)}} و اندازه O(n log n) برای n ورودی است، که بهینه می‌باشد. نسخه ساده شده شبکه AKS توسط پترسن توصیف شده استشده‌است. کشف این شبکه پیشرفت نظری بزرگی بود، اما در عمل نمی‌توان از آن استفاده کرد زیرا در O ضرایب خطی بزرگی پنهان هستند. این‌ها همه به خاطر ساخت یک گراف بسط دهنده است. یافتن شبکه مرتب‌سازی با اندازه cn log n برای cهای کوچک کماکان یکی از مسائل حل نشده و در حال بررسی است.
برای تعداد ورودی‌های بین ۱ و ۸، شبکه‌های مرتب‌سازی بهینه پیدا شده‌اند. هر کدام به ترتیب ۰،۱،۳،۵،۹،۱۲،۱۶، و ۱۹ مقایسه کنندهمقایسه‌کننده دارند (نوث، سال ۱۹۹۷). عمق بهینه برای ده ورودی نیز محاسبه شده که به ترتیب ۰،۱،۳،۳،۵،۵،۶،۶،۷،۷ می‌باشند.
== منابع ==
| 