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

مقدمه

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

من، در این مقاله، برخی از الگوریتم‌های مرتب‌سازی را شرح خواهم داد. همه الگوریتم هایی که در اینجا مورد بحث قرار گرفته اند، در زبان برنامه نویسی #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، با سرعت دلخواه، ذخیره کند.

همه چیز در مورد delegate - بخش 6

متدهای بی‌نام

تا اینجا، شما دیده اید که می‌توانید از متدهای نمونه یا متدهای استاتیک برای نمونه سازی delegate استفاده کنید. در هرصورت، متد بخودی خود می‌تواند از قسمت های دیگر کد بصورت صریح فراخوانی شود و البته باید عضوی از یک کلاس یا ساختار باشد.

اگر متد تنها برای نمونه سازی delegate استفاده شده باشد چطور؟ در چنین شرایطی، بجز اینکه به نیازمندی های نحوی و املائی برای ساختن delegate احتیاج داریم، در واقع نیازی به ساختن یک متد با نام جداگانه وجود ندارد. متدهای بی نام به شما اجازه می‌دهند که از ساختن متدهای نامدار بیهوده جلوگیری کنید.

• یک متد بی نام، متدی است که در محل نمونه سازی delegate ، اعلان می‌شود.

برای نمونه، شکل زیر دو نسخه از یک کلاس یکسان را نشان می‌دهد. نسخه سمت چپ یک متد به نام Add20 را اعلان و استفاده می‌کند. نسخه سمت راست بجای آن از متد بی نام استفاده می‌کند. قسمت هایی از کد که سایه گذاری نشده، کاملا برابر هستند.

همه چیز در مورد delegate - بخش 5

احضار delegate هایی که دارای مقدار برگشتی هستند

اگر یک وکیل دارای مقدار بازگشتی باشد و در لیست احضارش بیش از یک متد موجود باشد، موارد زیر رخ خواهد داد:

• مقداری که از آخرین متد موجود در لیست احضار برگشت داده می‌شود همان مقدار برگشتی وکیل است.
• مقدار برگشتی همه متدهای دیگر نادیده گرفته می‌شود.

برای مثال کد زیر یک delegate اعلان می‌کند که دارای مقدار برگشتی از نوع int است. تابع Main یک شیئ از آن delegate ساخته، سپس 2 متد به آن اضافه می‌کند، بعد از آن delegate را در بیان WriteLine فراخوانی کرده و مقدار برگشتی آن را چاپ می‌کند. شکل زیر یک ارائه گرافیکی از کد را نشان می‌دهد.

کلاس های کلکسیونی

دات نت فریم وورک کلاس های مخصوصی را برای ذخیره و بازیابی داده ها ارائه داده است. این کلاس ها پشتیبانی از لیست ها، پشته ها، صف ها و جداول هش (جدول هایی که یک سری کلید را به مقادیر خاصی مرتبط می کند) را فراهم می کنند. اکثر کلاس های کلکسیونی رابط های مشابهی را پیاده سازی می کنند، و این رابط ها را می توان برای ساختن کلاس های کلکسیونی جدید که منطبق با نیازهای ذخیره سازی تخصصی تر هستند بکار برد.

نکته

اپلیکیشن های نوشته شده با نسخه 2.0 و بالاتر دات نت فریم وورک می بایست از کلاس های کلکسیونی جنریک موجود در فضای نام  System.Collections.Generic که امنیت-نوع و کارایی بیشتری نسبت به نسخه غیر-جنریک خود دارند، استفاده کنند.

ArrayList list = new ArrayList();
list.Add(10);
list.Add(20);

بررسی کلاس های کلکسیونی

کلاس های کلکسیونی دارای خوصوصیات زیر می باشند:

کلمه کلیدی unsafe

کلمه کلیدی unsafe یک زمینه (context) ناامن تعریف می کند که برای هر عملی که با اشاره گرها در ارتباط باشد، لازم است.

شما می توانید از اصلاحگر unsafe در اعلان یک نوع یا یک عضو استفاده کنید. حوزه همان نوع و یا عضوی که دارای اصلاحگر unsafe باشد به عنوان زمینه ناامن در نظر گرفته می شود. در مثال زیر متدی را با اصلاحگر unsafe اعلان کرده ایم:

unsafe static void FastCopy(byte[] src, byte[] dst, int count)
{
    // Unsafe context: can use pointers here.
}

حوزه (scope) زمینه ناامن از لیست پارامترها شروع شده و تا آخر حوزه متد ادامه دارد، بنابراین از اشاره گرها می توان در لیست پارامترها نیز استفاده کرد:

unsafe static void FastCopy ( byte* ps, byte* pd, int count ) {...}

شما می توانید از بلوک unsafe برای فعالسازی استفاده از کد ناامن در بلوک مربوطه استفاده کنید. برای مثال:

unsafe
{
    // Unsafe context: can use pointers here.
}

کلمه کلیدی params

کلمه کلیدی params به شما امکان مشخص کردن یک پارامتر متد که تعداد متغیری آرگومان دریافت می کند را می دهد.

شما می توانید یک لیست از آرگومان ها از همان نوعی که در اعلان پارامتر مشخص شده را که با علامت وریگول از یکدیگر جدا شده اند (comma-separated) ، یا یک آرایه آرگومان ها از همان نوع مشخص شده را به متد ارسال کنید.

در اعلان متد بعد از کلیدواژه params ، هیچ پارامتر اضافه ای مجاز نیست، و فقط یک کلمه کلیدی params در اعلان متد مجاز است.

مثال

مثال زیر راه های مختلفی که می توان آرگومان ها را به یک پارامتر params ارسال کرد را توضیح می دهد.

جدول کلمات کلیدی #C

 

کلمات کلیدی، شناسه هایی از پیش تعریف شده و رزرو شده هستند که معانی خاصی برای کامپایلر دارند. شما نمی توانید از این کلمات رزرو شده به عنوان شناسه (مثلا اسم کلاس یا متغیر) در برنامه تان استفاده کنید، مگر اینکه قبل از چنین شناسه هایی از پسوند @ استفاده کنید. برای مثال if@ یک شناسه معتبر است ولی if معتبر نیست ، زیرا if یک کلمه کلیدی است.

جدول اول در این تاپیک، لیست کلیدواژه هایی را که شناسه هایی رزرو شده در هر قسمتی از برنامه #C هستند را آورده است. جدول دوم در این مطلب شامل لیست کلیدواژه های زمینه ای (وابسته به قراین و شرایط خاصی که آن کلمه کلیدی در آن قرار گرفته است) در سی شارپ است. کلمات کلیدی زمینه ای فقط در یک زمینه (context) محدود از برنامه، معنای ویژه  ای دارند و از این کلمات می توان در بیرون از آن زمینه به عنوان شناسه استفاده کرد. بطور کلی، اگر کلمات کلیدی جدیدی به زبان #C اضافه شود، برای اجتناب از خرابی نسخه های قبلی برنامه های نوشته شده، آن کلمات جدید به لیست کلیدواژه های زمینه ای اضافه خواهد شد.

جدول در ادامه مطلب...