سال انتشار: ۱۳۸۲

محل انتشار: نهمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۹

نویسنده(ها):

مهدی شاه آبادی – آزمایشگاه سیستمهای نرم افزاری دانشکده مهندسی کامپیوتر و فناوری اطلا
محمدرضا میبدی – آزمایشگاه سیستمهای نرم افزاری دانشکده مهندسی کامپیوتر و فناوری اطلا

چکیده:

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