مرتب سازی در مدل بیتی

روش اول: 

 هر پردازنده یک عدد 4 بیتی را می تواند ذخیره کند و یک عدد 4 بیتی دریافت می کند و بیت به بیت از پر ارزش ترین بیت این دو عدد را مقایسه می کند. هر گاه اولین بار به بیت هایی برسد که مساوی نباشند تصمیم برای جایگزینی یا عبور عدد دریافت شده گرفته می شود و این سیگنال به بیت های کم ارزش تر هم منتقل میشود. در این مثال چون عدد 4 بیتی است 4 کلاک برای این مقایسه زمان صرف می شود.

در این روش مرتب سازی N عدد K بیتی از مرتبه O( K * N)  می باشد. که مرتبه قابل قبولی برای حل این مسئله نیست! تعداد دقیق گام ها K*(2N-1) hsj.

روش دوم : این روش، روش درختی است که بیت ها در برگ ها قرار دارند و اما بیت های پر ارزش تر اولویت بالاتری دارند. به اینصورت که اگر بیت پر ارزش تر مساوی باشد نتیجه مقایسه بیت کم ارزش تر به خروجی منتقل میشود. در غیر اینصورت بدون در نظر گرفتن نتیجه مقایسه بیت کم ارزش تر به خروجی منتقل می شود. در این روش نسبت به روش اول که برای مقایسه دو عدد K بیتی، K گام زمان می برد، lg K +1 زمان می برد. برای برگشت نتیجه از ریشه به برگ ها نیز می بایست ارتفاع درخت طی شود. در نتیجه هر پردازنده بعد از (2 تا lg K) گام می داند که عدد بزرگتر کدام است.  در این روش تعداد گام ها با مرتبه lg K بهتر از روش اول است.

 تعداد کل گام ها در این روش برابر است با :

T = (2N - 1) * 2 lg K bit steps

P = (2K - 1) * N  bit processors

   روش سوم: برای بهتر شدن مرتبه الگوریتم به جای مقایسه باینری میتوانیم به صورت خطی مقایسه کنیم! این روش روش پایپلاین است و مانند روش درختی نیست که فقط روش مقایسه در هر ستون از پردازنده ها را عوض می کرد و می توانست در روش مرتب سازی با آرایه خطی مورد استفاده قرار گیرد. این روش بدون استفاده از پردازنده های بیشتر ( مانند روش درختی ) مرتبه الگوریتم مرتب سازی را بهتر می کند. در مثالی که در شکل زیر آورده شده است از آرایه 3-سلولی برای مرتب سازی 5 عدد داده شده استفاده می کند. همانطور که در شکل مشخص است اعداد به صورت باینری ( 3 بیتی) و شیفت داده شده ( به صورتیکه اگر بیت iام عدد k در زمان t وارد آرایه شود بیت i+1ام در زمان t+1 وارد خواهد شد.) شیفت ورودی ها باعث می شود که در زمان مقایسه دو بیت در یک پردازنده در آرایه بیت پر ارزش تر همین اعداد در کلاک قبلی مقایسه و نتیجه اش آماده باشد. تعداد دقیق گام ها برای فاز اول ( مرتب سازی) در این الگوریتم برابر :

2N+K-2

و برای فاز دوم و چاپ خروجی تعداد گام ها برابر است با:

N -2

and the overall time to sort N K-bit numbers is just 3N+K-4

همین! :)