مرتب سازی ادغامی و مرتب سازی سریع

روش مرتب سازی ادغامی از الگوریتم تقسیم و حل (divide-and-conquer) و همچنین ادغام برای مرتب کردن داده‌ها استفاده می‌کند. در این الگوریتم مساله به چند جزء کوچک‌تر تقسیم می‌شود. هر کدوم از این قسمت‌ها رو به طور مجزا حل کرده، و با ترکیب اونها به مساله اصلی می‌رسیم. و اما طرح کلی مرتب سازی ادغام:

در این روش داده‌ها به دو قسمت مساوی تقسیم می‌شوند. و هر کدوم از این قسمت‌ها - به صورت بازگشتی - مرتب، و با ادغام آنها دادها بصورت کامل مرتب می‌شوند.اما توجه به این نکته ضروری است که اگر پس از یک بار تقسیم باز هم لیستهای ایجاد شده بزرگ باشند ، می توانیم برای هر زیر لیست مراحل بالا را دوباره انجام دهیم تا به زیر لیستهایی با تنها 1 عضو برسیم و واضح است که لیست تک عنصری خود مرتب است.

مرتب سازی سریع (Quick Sort) از جمله روشهای محبوب و با سرعت بالا برای مرتب کردن داده‌ها محسوب می‌شه. این روش هم مثل روش ادغام از تقسیم و حل (Divide and Conqure) برای مرتب کردن داده‌ها استفاده می‌کنه. به این ترتیب که داده‌ها رو به دو قسمت مجزا تقسیم، و با مرتب کردن اونها کل داده‌ها رو مرتب می‌کنه. برای اینکار یکی از داده‌ها (مثلاً داده اول) به عنوان محور انتخاب می‌شه. داده‌ها بر اساس محور طوری چینش می‌شن که همه داده‌های کوچک‌تر از محور سمت چپ و داده‌های بزرگ‌تر یا مساوی اون سمت راستش قرار می‌گیرن. با مرتب کردن دو قسمت به دست اومده کل داده‌ها مرتب می‌شن. در این حالت مثل روش ادغام نیازی به ادغام کردن داده‌ها نیست. چرا که قسمت سمت راست همگی از قسمت سمت چپ کوچک‌تر هستن و بالعکس. 

منبع اصلی درس الگوریتم ها

کتاب آشنایی با الگوریتم ها که توسط چهار نفر (  CLRS ) نوشته شده:

ویرایش سوم کتاب

ویرایش دوم کتاب

جستجو ها و مرتب سازی های تدریس شده:

جستجوی خطی، جستجوی دودویی، مرتب سازی انتخابی، مرتب سازی درجی، مرتب سازی حبابی

جزوه

جدول مستطیلی

در هر خانه از یک جدول مستطیلی یک عدد طبیعی نوشته شده است. در هر مرحله می توان یک واحد از تمامی اعداد یک ستون کم کرده و یا تمام اعداد یک سطر را دو برابر کنیم. آیا همواره می توان تمام اعداد درون جدول را صفر کرد؟

موسیقی یا پیام جاسوسی

یک شبکه بزرگ جاسوسی از روش خاصی برای فرستادن پیام به ماموران و جاسوسان خود در فاصله های دور استفاده می کند؛ به این ترتیب که پیام های مورد نظر خود را به صورت دنباله هایی از ارقام صفر و یک رمزگذاری می کند و این دنباله ها را در قالب نت های موسیقی که صدای آن ها کم و زیاد می شود از طریق امواج معمولی رادیویی ارسال می کند. ماموران می دانند که کاهش طنین در موسیقی حاوی پیام به معنی صفر و افزایش آن نشانه ی یک است. در این جا حالت خاصی را در نظر می گیریم که در آن هر پیام یک دنباله ی چهارتایی از صفر و یک هاست (یک دنباله چهاربیتی).

این شبکه می خواهد برای 9 نفر از مامورانش پیام بفرستد، ولی از آنجا که زیاد شدن طول پیام احتمال شناسایی و کشف آن را زیاد می کند سعی می کند طول کل پیام ارسالی تا حد ممکن کوتاه باشد. به این دلیل، در صورت امکان پیام های مورد نظر خود را با هم ترکیب و یک جا ارسال می کند. مثلا هر گام بخواهد پیام 0110 را به یکی از ماموران و پیام 1011 را مامور دیگر بفرستد، می تواند آن ها را به صورت 011011 ترکیب و یک جا ارسال کند. البته در این حالت باید قبل از ارسال این پیام ترکیبی، به مامور اول اطلاع دهد که از رقم اول شروع به خواندن کند و به مامور دوم بگوید که از رقم سوم شروع به خواندن کند. برای اطلاع دادن محل شروع پیام هر مامور (شماره رقم آن) هم از نت موسیقی خاصی برای آن مامور استفاده می شود.

1- این شبکه می خواهد پیام های 0000 ، 0011 ، 0100 ، 0110 ، 0111 ، 1011 ، 1100 ، 1101 و 1110را به مامورانش بفرستد. متخصصی کد گذاری شبکه موفق به یافتن دنباله ای به طول 15 بیت برای ترکیب این 9 پیام شده اند. آیا شما می توانید دنباله ای به طول 14 یا کمتر بیابید که شامل همه این 9 پیام باشد؟

2- فرض کنید تعداد ماموران این شبکه از 9 نفر به 14 نفر افزایش پیدا کرده است. آیا می توانید دنباله ای 19 بیتی پیدا کنید که شامل هر مجموعه 14 تایی دلخواه از پیام های 4 بیتی باشد؟

3- آیا می توان یک دنباله 18 بیتی که 14 دنباله 4 بیتی مشخص که از قبل به شما داده شده اند، زیر دنباله های آن باشند؟ (به تفاوت این سوال و سوال قبل دقت کنید. در سوال قبل دنباله 19 بیتی باید شامل هر مجموعه دلخواه از مجموعه 4 بیتی باشد، ولی در این سوال 14 دنباله داده شده است که دنباله 18 بیتی باید شامل هر یک از آن ها باشد. نشان دهید که بدون توجه به این که 14 دنباله انتخاب شده، چه دنباله هایی هستند؛ می توانید دنباله 18 بیتی مورد نظر را تشکیل دهید.)

4- نشان دهید مجموعه هایی از 14 دنباله 4 بیتی وجود دارند که هیچ دنباله ای به طول 18 بیت یا کمتر شامل همه آن ها نیست.

منبع: معماهای الگوریتمی، دکتر قدسی و یاشار گنجعلی، انتشارات فاطمی

کوتاه ترین مسیر با دایسترای دوطرفه

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

دایسترای دو طرفه در واقع با ساختن دو تا گراف از مبدا و مقصد (رو به جلو و رو به عقب) به دست می آید.

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

این تغییر عبارت است از چک کردن یال های بین مسیر اول و مسیر دوم.

فایل پاور پوینت زیر که توسط خودم درست شده این مطلب را نشان می دهد.

فایل پاورپوینت

فایل پی دی اف مقاله مربوطه