مرتب کردن اعداد در برنامه نویسی میکروکنترلر با الگوریتم shell sort

این بحث شاید خیلی عمومیت نداشته باشد. واسه همین، تعجب نمی‌کنم که بگویید: “آخه کی در برنامه نویسی میکروکنترلر نیاز به این کار داره؟!” اما اگر به هر دلیلی به دنبال راهکاری برای مرتب یا sort کردن تعداد زیادی از اعداد در برنامه میکروکنترلر خود می‌گردید، شاید shell sort همان چیزی باشد که به دنبالش هستید. این پست حاصل تحقیقات چند روزه‌ی من پیرامون این موضوع بوده.

برای پروژه‌ای لازم بود تا آرایه‌ای از اعداد را با تعداد حداکثر 400 عضو مرتب کنم. یکی از نیازهای مسئله در اینجا، این بود که این کار بایست با حداکثر سرعت انجام می‌شد. اما خب این چالش تنها یکی از ابعاد مسئله بود. قسمت دیگر کار این بود که بتوان الگوریتم سورت کردن را با محدودیت‌های میکروکنترلر اجرا کرد. برای مثال بعضی از الگوریتم‌های مرتب سازی هستند که نیاز به فضای RAM زیادی دارند و در نتیجه اگرچه سرعت اجرایشان بالاست، اما بدرد استفاده در برنامه میکروکنترلر نمی‌خورند.

با همه‌ی این اوصاف و امتحان کردن چند الگوریتم، نهایتا تصمیم به این گرفتم که از الگوریتم shell sort استفاده کنم.

مزایایی که از shell sort دیدم:

• سرعت اجرای خیلی خوبی دارد و نیاز من رو تامین می‌کرد.
• برای اجرا نیاز به حافظه زیادی ندارد و مرتب سازی را به صورت درجا انجام می‌دهد. یعنی اگر یک آرایه به عنوان ورودی بهش میدیم. روی همان فضای آرایه کار می‌کند و مرتب سازی را انجام می‌دهد. در حالی که بعضی از الگوریتم‌ها نیاز دارند که به اندازه حجم ورودی یا حتی بیشتر، باز حافظه بگیرند.
• پیاده سازی این الگوریتم نسبتاً ساده است و نیاز به کد خیلی زیادی برای اجراش نداریم.

اگر کمی جستجو کنید اطلاعات زیادی از نحوه اجرای این الگوریتم می‌توانید به دست آورید. اما هدف من از این پست این نبود که تکرار مکررات کنم. فقط خواستم ایده‌ای بدهم از اینکه این الگوریتم میتواند گزینه‌ی مناسبی برای سورت کردن داده‌هاتون در برنامه نویسی میکروکنترلر باشد. این گزینه‌ی مناسب بودن هم کاملاً به شرایط مسئله بر می‌گردد. پس الزاماً shell sort همیشه اون گزینه‌ی خوب نیست. اصلاً به همین دلیل هم هست که انواع مختلفی از الگوریتم‌های sorting رو داریم.

تکه کد زیر، پیاده سازی این الگوریتم در زبان C است. امیدوارم که برایتان مفید واقع شود. راستی اگر الگوریتم بهتری سراغ داشتید و فکر می‌کنید میتواند مناسب‌تر از shell sort باشد، خوشحال میشم زیر همین پست معرفیش کنید.

void shellSort(uint32_t arr[], uint32_t n) 
{ 
    for (uint32_t gap = n/2; gap > 0; gap /= 2) { 
        
        for (uint32_t i = gap; i < n; i += 1) { 
            uint32_t temp = arr[i]; 
            uint32_t j;          
            
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap]; 
            }
              
            arr[j] = temp; 
        } 
    }  
}