برنامه نویسی 5 بازدید

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

برای یک لیست کوتاه، بصری‌سازی مسئله، امری ساده است. برای چیدمان مجموعه به صورت یک دنباله منظم می‌توانیم یک «ناوردا» (Invariant) پیاده‌سازی کنیم. ناورداها فرضیاتی را نمایش می‌دهند که در تمام طول اجرا بدون تغییر می‌مانند. برای این که ببینید این وضعیت چگونه کار می‌کند، الگوریتم مرتب‌سازی ادغامی را ملاحظه کنید.

مرتب‌سازی ادغامی

«مرتب‌سازی ادغامی» (INSERTION SORT) یکی از ابتدایی‌ترین الگوریتم‌ها در علوم رایانه به حساب می‌آید. این الگوریتم عناصر را از طریق تکرار یک چرخه روی یک مجموعه و تعیین موقعیت عناصر بر اساس ارزششان رتبه‌بندی می‌کند. این مجموعه به دو نیمه مرتب و نامرتب تقسیم می‌شود و این کار تا زمانی که همه عناصر مرتب‌سازی شوند تداوم می‌یابد:

مرتب‌سازی حبابی

«مرتب‌سازی حبابی» (BUBBLE SORT) یک تکنیک مرتب‌سازی رایج دیگر است. این تکنیک نیز مانند مرتب‌سازی ادغامی حاصل ترکیب یک سری مراحل با یک ناوردا است. این تابع با ارزیابی جفت مقدارها عمل می‌کند. زمانی که مقایسه صورت بگیرد، موقعیت بزرگ‌ترین مقدار با کوچک‌ترین مقدار تعویض می‌شود. هنگامی که این کار به دفعات کافی صورت بگیرد، تأثیر این «حباب سازی» خود را نشان می‌دهد و در نهایت همه عناصر در لیست مرتب‌سازی می‌شوند:

مرتب‌سازی انتخابی

«مرتب‌سازی انتخابی» (SELECTION SORT) نیز همانند مرتب‌سازی حبابی به رتبه‌بندی عناصر از طریق تعریف چرخه‌ای روی یک مجموعه و تعویض مکان عناصر بر اساس مقدارشان عمل می‌کند. مجموعه به نیمه‌های مرتب و نامرتب تقسیم می‌شود و این فرایند تا زمانی که همه عناصر مرتب‌سازی شوند ادامه می‌یابد:

علاوه بر روش‌های مرتب‌سازی درجی، انتخابی و حبابی، الگوریتم‌های مرتب‌سازی زیاد دیگری نیز وجود دارند. همان طور که می‌دانید ساختمان‌های داده درخت جستجوی دودویی و «هیپ» (Heap) نیز به فرایند مرتب‌سازی عناصر کمک می‌کنند؛ اما این کار را به عنوان بخشی از فرایند درج انجام می‌دهند.

اگر این مطلب برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

==

بر اساس رای 1 نفر

آیا این مطلب برای شما مفید بود؟

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *