|
[[پرونده:SimpleSortingNetwork2.svg|بندانگشتی|250px|یک شبکه مرتب‌سازی ساده شامل چهار سیم و پنج اتصال دهنده]]
شبکه [[مرتب‌سازی]] یک مدل انتزاعی ریاضی شامل شبکه ایشبکه‌ای از سیم‌ها و واحدهای [[مقایسه کننده]] است که برای [[مرتب‌سازی رشته‌ای]] از اعداد از آن استفاده می شودمی‌شود. هر مقایسه کننده دو سیم را به هم متصل می‌کند و مقادیر را با قرار دادن مقدار کوچکتر به یکی از سیم‌ها و مقدار بزرگتر به سیم دیگر، مرتب می کندمی‌کند. اصلی‌ترین تفاوت میان شبکه مرتب‌سازی و [[الگوریتم مرتب‌سازی]] این است که ترتیب مقایسه‌ها بدون در نظر گرفتن نتیجه مقایسه‌های قبلی، از قبل مشخص شده است. استقلال میان ترتیب مقایسه‌ها برای اجرای موازی الگوریتم‌ها مفید خواهد بود. علی‌رغم سادگی مدل آن، تئوری مرتب‌سازی شبکه ایشبکه‌ای بسیار پیچیده و دارای مفاهیم عمیقی است.
== آشنایی مقدماتی ==
یک شبکه مرتب‌سازی شامل دو عنصر است، مقایسه کننده‌ها و سیم هاسیم‌ها. هر سیم دارای یک مقدار می باشد،می‌باشد، و هر مقایسه کننده دو سیم را به عنوان ورودی و خروجی می گیردمی‌گیرد. زمانی که دو مقدار وارد مقایسه کننده می شود،می‌شود، مقایسه کننده مقدار کوچکتر را در سیم بالاتر، و مقدار بزرگتر را در سیم پایین قرار می دهدمی‌دهد. به شبکه ایشبکه‌ای از سیم‌ها و مقایسه کننده‌ها که به طور صحیح تمام مقادیر ورودی را به صورت صعودی مرتب کنند یک شبکه مرتب‌سازی گفته می شودمی‌شود.
مراحل انجام یک مرتب‌سازی شبکه ایشبکه‌ای ساده در شکل زیر نشان داده شده است. فهم چگونگی صحیح عمل نمودن این شبکه مرتب‌سازی آسان است، این را مدنظر داشته باشید که مقایسه کننده‌ها مقدار بزرگ را به سیم پایین و مقدار کوچک را به سیم بالا منتقل می کنند.می‌کنند؛ و در نهایت آخرین مقایسه کننده دو سیم میانی را مرتب می کندمی‌کند.
[[پرونده:SimpleSortingNetworkFullOperation.svg|650px]]
=== شبکه‌های درجی و انتخابی ===
به راحتی می توانمی‌توان با استفاده از اصول درجی و انتخابی به صورت بازگشتی یک شبکه با اندازه دلخواه ایجاد کرد. با فرض این که یک شبکه مرتب‌سازی با اندازه n داریم، می توانیممی‌توانیم با درج یک عدد اضافی به زیر شبکه مرتب شده ( با استفاده از اصول [[مرتب‌سازی درجی]])، یک شبکه مرتب‌سازی با اندازه n+۱ بسازیم. همین کار را می توانیممی‌توانیم به شکل دیگری انجام دهیم، ابتدا کوچکترین مقدار ورودی‌ها را انتخاب می کنیم،می‌کنیم، سپس مقادیر باقی‌مانده را به صورت بازگشتی مرتب می کنیممی‌کنیم ( با استفاده از اصول [[مرتب‌سازی حبابی]]).
{|
|}
ساختار این دو مرتب‌سازی شبکه ایشبکه‌ای بسیار شبیه یکدیگر است، با نمایش همزمان روند انجام مقایسه‌ها توسط مقایسه کننده‌ها عملاً می توانمی‌توان گفت که این دو یکی هستند.
{|
| [[پرونده:Six-wire-bubble-sorting-network.svg|200px|بندانگشتی|شبکه مرتب‌سازی حبابی]]
| [[پرونده:Six-wire-insertion-sorting-network.svg|200px|بندانگشتی|شبکه مرتب‌سازی درجی]]
| [[پرونده:Six-wire-pyramid-sorting-network.svg|200px|بندانگشتی|با مقایسه کننده هایکننده‌های موازی، مرتب‌سازی درجی و حبابی مثل هم خواهند بود]]
|}
=== شبکه‌های کارآمد ===
شبکه درجی عمقی، به اندازه (O(n دارد، بنابراین استفاده از آن در عمل به صرفه نیست. شبکه‌های ساده ایساده‌ای وجود دارند با عمق {{math|O(log n)<sup>2</sup>}} و اندازه {{math|O(n (log n)<sup>2</sup>)}}، مانند [[مرتب‌سازی ادغامی دسته‌ای فرد-زوج]]، [[مرتب‌سازی بایتونیک]]، و [[مرتب‌سازی صدفی]]. در عمل از این شبکه‌ها استفاده می شودمی‌شود.
=== اصل صفر و یک ===
اثبات صحیح بودن بعضی از شبکه‌های مرتب‌سازی مثل شبکه مرتب‌سازی درجی و حبابی آسان است، اما همیشه اینگونه نیست. برای یک شبکه n سیمه، !nسیمه،n جایگشت از اعداد خواهیم داشت، و امتحان کردن تمام آنها نیاز به زمان بسیار زیادی دارد، به خصوص در شبکه‌های بزرگتر. اما با استقاده از اصل صفر و یک تعداد دفعات امتحان به طور چشمگیری کاهش پیدا می کندمی‌کند.
اصل صفر و یک بیان می‌کند که یک شبکه مرتب‌سازی زمانی صحیح عمل کرده اگر بتواند رشته ایرشته‌ای از صفرها و یک‌ها که تعدادشان <math>2^n</math> است مرتب کند. با استفاده از این اصل می توانمی‌توان تعداد تست‌های لازم برای مشخص کردن صحیح بودن شبکه را به طور چشمگیری کاهش داد، و هم چنین در ساختن شبکه‌های مرتب‌سازی مختلف موثر خواهد بود.
[[روش اثبات]] آن یک حالت خاص از نظریه بوریسیوس است که در سال ۱۹۴۵ توسط بوریسیوس اثبات شد.
== مرتب‌سازی بهینه ==
کارایی یک شبکه مرتب‌سازی را می توانمی‌توان با استفاده از اندازه کل آن ( تعداد مقایسه کننده‌های استفاده شده)، یا با استفاده از عمقش (حداکثر تعداد مقایسه کننده هاییکننده‌هایی که در مسیر یک ورودی به خروجی قرار دارند)، [[اندازه گیریاندازه‌گیری]] کرد. بهترین شبکه مرتب‌سازی شناخته شده، شبکه AKS است که از حروف اول کاشفان آن، اجتا، کاملوس، و سمیردای گرفته شده است. این شبکه دارای عمق {{math|O(log n)}} و اندازه O(n log n) برای n ورودی است، که بهینه می باشدمی‌باشد. نسخه ساده شده شبکه AKS توسط پترسن توصیف شده است. کشف این شبکه پیشرفت نظری بزرگی بود، اما در عمل نمی تواننمی‌توان از آن استفاده کرد زیرا در O ضرایب خطی بزرگی پنهان هستند. این‌ها همه به خاطر ساخت یک گراف بسط دهنده است. یافتن شبکه مرتب‌سازی با اندازه cn log n برای cهای کوچک کماکان یکی از مسائل حل نشده و در حال بررسی است.
برای تعداد ورودی‌های بین ۱ و ۸، شبکه‌های مرتب‌سازی بهینه پیدا شده اندشده‌اند. هر کدام به ترتیب ۰،۱،۳،۵،۹،۱۲،۱۶، و ۱۹ مقایسه کننده دارند ( نوث، سال ۱۹۹۷). عمق بهینه برای ده ورودی نیز محاسبه شده که به ترتیب ۰،۱،۳،۳،۵،۵،۶،۶،۷،۷ می باشندمی‌باشند.
== منابع ==
{{پانویس}}
{{چپ‌چین}}
* O. Angel، A.E. Holroyd، D. Romik، B. Virag، ''[http://arxiv.org/abs/math/0609538 Random Sorting Networks]''، Adv. in Math. ، ۲۱۵(۲):۸۳۹–۸۶۸، ۲۰۰۷.
* K.E. Batcher، ''[http://www.cs.kent.edu/~batcher/sort.ps Sorting networks and their applications]''، Proceedings of the AFIPS Spring Joint Computer Conference ۳۲، ۳۰۷–۳۱۴ (۱۹۶۸).
* [[توماس اچ کورمن]]، [[Charles E. Leiserson]]، [[رونالد ریوست]]، and [[کلیفورد استین]]. ''[[مقدمه‌ای بر الگوریتم‌ها]]''، Second Edition. MIT Press and McGraw-Hill، ۱۹۹۰. ISBN ۰-۲۶۲-۰۳۲۹۳-۷. Chapter ۲۷: Sorting Networks، pp.۷۰۴–۷۲۴.
* [[دانلد کنوت|D.E. Knuth]]. ''[[هنر برنامه‌نویسی رایانه]]''، Volume ۳: ''Sorting and Searching''، Third Edition. Addison-Wesley، ۱۹۹۷. ISBN ۰-۲۰۱-۸۹۶۸۵-۰. Section ۵.۳.۴۵٫۳٫۴: Networks for Sorting، pp. ۲۱۹–۲۴۷.
* M. S. Paterson، ''Improved sorting networks with O''(log ''N'') ''depth''، Algorithmica ۵ (۱۹۹۰)، no. ۱، pp. ۷۵–۹۲، {{doi|10.1007/BF01840378}}.
{{پایان چپ‌چین}}
| 