الگوریتمهای مرتب سازی جدید برای اتوماتای سلولی دو بعدی

اگر چه الگوریتم های متعددی برای مرتب سازی در کامپیوتر های ترتیبی و موازی ارائه شده است ولی هنوزکار زیادی بر روی مرتب سازی برای اتوماتای سلولی انجام نگرفته است . دو الگوریتم یکی منصوب به گوردیلو ١ و لونا ٢ و دیگری منصوب به شاه آبادی و میبدی برای اتوماتای سلولی یک بعدی ارایه شده است . الگوریتم گوردیلو و لونا، n عنصر را با استفاده ازnسلول در 2n-3 مرحله و الگوریتم شاه آبادی و میبدی n عنصر را با استفاده از n سلول در n-1 مرحله مر تب می نماید . تنها الکوریتم مرتب سازی برای اتوماتای سلولی دو بعدی nxn توسط گلزاری و میبدی ارایه شده است که دارای پیچیدگی زمانی ) O(n 2 میباشد . در این مقاله دو الگوریتم مرتب سازی موازی جدید برای اتوماتای سلولی دو بعدی ارائه شده است . الگوریتمهای ارائه شده دارای پیچیدگی متوسط O( n) می باشند که نسبت به الگوریتم گلزاری و میبدی دارای مرتبه بزرگی بمراتب کمتری میباشد

کلیدواژه ها:

آتوماتای سلولی ، مرتب سازی ، پردازش موازی