شبکه مرتب‌سازی: تفاوت میان نسخه‌ها

[[Imageپرونده:SimpleSortingNetwork2.svg|thumb|250px|یک شبکه مرتب سازی ساده شامل چهار سیم و پنج اتصال دهنده]]

[[Imageپرونده:SimpleSortingNetworkFullOperation.svg|650px]]

به راحتی می توان با استفاده از اصول درجی و انتخابی به صورت بازگشتی یک شبکه با اندازه دلخواه ایجاد کرد. با فرض این که یک شبکه مرتب سازی با اندازه n داریم، می توانیم با درج یک عدد اضافی به زیر شبکه مرتب شده ( با استفاده از اصول [[مرتب سازی درجی]])، یک شبکه مرتب سازی با اندازه n+1۱ بسازیم. همین کار را می توانیم به شکل دیگری انجام دهیم، ابتدا کوچکترین مقدار ورودی‌ها را انتخاب می کنیم، سپس مقادیر باقیمانده را به صورت بازگشتی مرتب می کنیم ( با استفاده از اصول [[مرتب سازی حبابی]]).

| [[Imageپرونده:Recursive-bubble-sorting-network.svg|thumb|250px|یک شبکه مرتب سازی بازگشتی براساس [[مرتب سازی حبابی]]]]

| [[Imageپرونده:Recursive-insertion-sorting-network.svg|thumb|250px|یک شبکه مرتب سازی بازگشتی براساس [[مرتب سازی درجی]]]]

ساختار این دو مرتب سازی شبکه ای بسیار شبیه یکدیگر است، با نمایش همزمان روند انجام مقایسه‌ها توسط مقایسه کننده‌ها عملاً می توان گفت که این دو یکی هستند.

| [[Imageپرونده:Six-wire-bubble-sorting-network.svg|200px|thumb|شبکه مرتب سازی حبابی]]

| [[Imageپرونده:Six-wire-insertion-sorting-network.svg|200px|thumb|شبکه مرتب سازی درجی]]

| [[Imageپرونده:Six-wire-pyramid-sorting-network.svg|200px|thumb|با مقایسه کننده های موازی، مرتب سازی درجی و حبابی مثل هم خواهند بود]]

روش اثبات آن یک حالت خاص از نظریه بوریسیوس است که در سال 1945۱۹۴۵ توسط بوریسیوس اثبات شد.

کارایی یک شبکه مرتب سازی را می توان با استفاده از اندازه کل آن ( تعداد مقایسه کننده‌های استفاده شده)، یا با استفاده از عمقش (حداکثر تعداد مقایسه کننده هایی که در مسیر یک ورودی به خروجی قرار دارند)، اندازه گیری کرد. بهترین شبکه مرتب سازی شناخته شده، شبکه AKS است که از حروف اول کاشفان آن، اجتا، کاملوس، و سمیردای گرفته شده است. این شبکه دارای عمق O(log n) و اندازه O(n log n) برای n ورودی است، که بهینه می باشد. نسخه ساده شده شبکه AKS توسط پترسن توصیف شده است. کشف این شبکه پیشرفت نظری بزرگی بود، اما در عمل نمی توان از آن استفاده کرد زیرا در O ضرایب خطی بزرگی پنهان هستند. این‌ها همه به خاطر ساخت یک گراف بسط دهنده است. یافتن شبکه مرتب سازی با اندازه cn log n برای cهای کوچک کماکان یکی از مسائل حل نشده و در حال بررسی است.

برای تعداد ورودی‌های بین 1۱ و 8،۸، شبکه‌های مرتب سازی بهینه پیدا شده اند. هر کدام به ترتیب 0،1،3،5،9،12،16،۰،۱،۳،۵،۹،۱۲،۱۶، و 19۱۹ مقایسه کننده دارند ( نوث، سال 1997۱۹۹۷). عمق بهینه برای ده ورودی نیز محاسبه شده که به ترتیب 0،1،3،3،5،5،6،6،7،7۰،۱،۳،۳،۵،۵،۶،۶،۷،۷ می باشند.

* O. Angel,Angel، A.E. Holroyd,Holroyd، D. Romik,Romik، B. Virag,Virag، ''[http://arxiv.org/abs/math/0609538 Random Sorting Networks]'',، Adv. in Math.,، 215۲۱۵(2۲):839–868,۸۳۹–۸۶۸، 2007۲۰۰۷.

* K.E. Batcher,Batcher، ''[http://www.cs.kent.edu/~batcher/sort.ps Sorting networks and their applications]'',، Proceedings of the AFIPS Spring Joint Computer Conference 32,۳۲، 307–314۳۰۷–۳۱۴ (1968۱۹۶۸).

* [[Thomas H. Cormen]],، [[Charles E. Leiserson]],، [[Ronald L. Rivest]],، and [[Clifford Stein]]. ''[[Introduction to Algorithms]]'',، Second Edition. MIT Press and McGraw-Hill,Hill، 1990۱۹۹۰. ISBN 0۰-262۲۶۲-03293۰۳۲۹۳-7۷. Chapter 27۲۷: Sorting Networks,Networks، pp.704–724۷۰۴–۷۲۴.

* [[Donald Knuth|D.E. Knuth]]. ''[[The Art of Computer Programming]]'',، Volume 3۳: ''Sorting and Searching'',، Third Edition. Addison-Wesley,Wesley، 1997۱۹۹۷. ISBN 0۰-201۲۰۱-89685۸۹۶۸۵-0۰. Section 5۵.3۳.4۴: Networks for Sorting,Sorting، pp. 219–247۲۱۹–۲۴۷.

* M. S. Paterson,Paterson، ''Improved sorting networks with O''(log ''N'') ''depth'',، Algorithmica 5۵ (1990۱۹۹۰),، no. 1,۱، pp. 75–92,۷۵–۹۲، {{doi|10.1007/BF01840378}}.