مقایسه تصویری انواع الگوریتم های مرتب‌سازی

مقدمه

به نظرم اولین و مهمترین چیزی که باید بفهمیم اینه که اصلا الگوریتم های مرتب سازی چه هستند. بر اساس ویکی‌پدیا، الگوریتم مرتب سازی، الگوریتمی است که عناصر یک لیست را به ترتیب خاصی در می‌آورد. کاربردی‌ترین ترتیب ها، ترتیب‌های عددی و ترتیب‌های وابسه به حروف هستند. بعضی از الگوریتم‌ها (از جمله الگوریتم‌های جستجو و ادغام) برای اینکه بدرستی کار کنند، نیازمند لیست‌های مرتب شده می باشند؛ مرتب‌سازی مؤثر و کارآمد، برای بهینه سازی کارائی چنین الگوریتم‌هایی، مهم هستند. این اگوریتم‌ها، اغلب اوقات، برای به نظم در آوردن داده‌ها و تولید خروجی قابل خواندن برای انسان، مفید هستند.

من، در این مقاله، برخی از الگوریتم‌های مرتب‌سازی را شرح خواهم داد. همه الگوریتم هایی که در اینجا مورد بحث قرار گرفته اند، در زبان برنامه نویسی #C نوشته شده‌اند و بسیاری از ایده‌ها، بر اساس الگوریتم‌هایی است که شما می‌توانید در ویکی‌پدیا پیدا کنید.

الگوریتم‌هایی که در این مقاله با آنها آشنا خواهید شد:

• مرتب سازی حبابی دوطرفه (Bidirectional Bubble Sort)
• مرتب سازی حبابی (Bubble Sort)
• مرتب سازی سطلی (Bucket Sort)
• مرتب سازی شانه ای (Comb Sort)
• مرتب سازی چرخه‌ای (Cycle Sort)
• مرتب سازی گورزاد (Gnome Sort)
• مرتب سازی هرمی (Heap Sort)
• مرتب سازی درجی (Insertion Sort)
• مرتب سازی ادغامی (Merge Sort)
• مرتب سازی زوج-فرد (Odd-Even Sort)
• مرتب سازی لانه کبوتری (Pigeonhole Sort)
• مرتب سازی سریع (Quick Sort)
• مرتب سازی سریع با استفاده از مرتب سازی حبابی (Quick Sort with Bubble Sort)
• مرتب سازی انتخابی (Selection Sort)
• مرتب سازی شل یا پوسته ای (Shell Sort)

قصد دارم طرز کار این الگوریتم ها رو بصورت دیداری به شما نشان بدهم. کاربر می تواند، خروجی این پروژه را بصورت تصاویر متحرک GIF، با سرعت دلخواه، ذخیره کند.

کلیدواژه stackalloc

در زمینه کدنویسی ناامن (unsafe code context) ، کلمه کلیدی stackalloc برای تخصیص یک بلوک حافظه در پشته (stack) بکار می رود.

int* fib = stackalloc int[100];

ملاحظات

مثال زیر سری فیبوناچی را که هر عدد حاصل جمع دو عدد قبل از خود در سری می باشد را تا 100 عدد ، تولید می کند . در کد زیر ، بلوکی از حافظه که اندازه آن برای نگهداری 100 عنصر از نوع int کافی است، در stack تخصیص داده شده نه در حافظه heap. آدرس این بلوک حافظه در اشاره گر fib ذخیره شده است (البته مثال زیر این کار را برای 20 عدد انجام می دهد که برای حفظ امانت عدد 100 را تغییر ندادم). این حافظه تحت تاثیر زباله جمع کن (Garbage Collector) قرار نمی گیرد و بنابراین مجبور نیستیم که با استفاده از کلمه کلیدی fixed ثابت شود. عمر این بلوک حافظه بستگی به عمر متدی دارد که این بلوک را تعریف کرده است. شما نمی توانید قبل از پایان متد این حافظه را آزاد کنید.

استفاده از stackalloc فقط در اعلان های متغیرهای محلی معتبر است.

امنیت

کد unsafe از امنیت کمتری نسبت به کد safe برخوردار است. هرچند استفاده از stackalloc بصورت اتوماتیک امکانات تشخیص تجاوز از بافر (buffer overrun detection) زبان زمان اجرای عمومی (CLR) را فعال می کند. اگر یک تجاوز بافر تشخیص داده شود، با بیشترین سرعت ممکن پردازش خاتمه پیدا می کند تا شانس اجرای کدهای مخرب به حداقل برسد.

مثال

عملگر new

برای ساختن شیئ ها و احضار متدهای سازنده مورد استفاده قرار می گیرد. برای مثال:

Class1 obj  = new Class1();

همچنین برای ساختن نمونه هایی از نوع های بی نام ، کاربرد دارد:

var query = from cust in customers
            select new {Name = cust.Name, Address = cust.PrimaryAddress};

عملگر new همچنین برای احضار (invoke) کردن متد سازنده پیش فرض نوع های مقداری مورد استفاده دارد. مثلا":

int i = new int();

در بیان قبل، i با صفر مقداردهی اولیه می شود، که مقدار پیش فرض برای نوع int می باشد. تاثیر این بیان مشابه بیان زیر است:

int i = 0;

به خاطر داشته باشید که اعلان یک متد سازنده پیش فرض برای یک struct (ساختار) یک خطا محسوب می شود، زیرا همه نوع های مقداری بصورت پیش فرض دارای یک متد سازنده public (عمومی) هستند. برای تنظیم مقدار اولیه نوع struct ، امکان اعلان متدهای سازنده دارای پارامتر بر روی نوع struct وجود دارد، اما این کار فقط زمانی انجام می شود که مقداری به غیر از مقدار پیش فرض مورد نیاز باشد.