👈 مرتب سازی ادغام(Merge Sort) چگونه کار می کند؟
همانطور که می دانیم که مرتب‌سازی ادغام از قانون تقسیم برای شکستن مسئله به مسائل فرعی استفاده می‌کندکه می توان گفت از الگوریتم Divide-and-conquer استفاده می شود،که مشکل در این مورد مرتب کردن یک آرایه معین است.
در مرتب سازی ادغام، آرایه داده شده را در میانه راه می شکنیم، به عنوان مثال اگر آرایه اصلی 6 عنصر داشته باشد، مرتب سازی ادغامی آن را به دو زیرآرایه با 3 عنصر تقسیم می کند.
اما شکستن آرایه اصلی به 2 زیرآرایه کوچکتر به ما در مرتب سازی آرایه کمکی نمی کند.
بنابراین ما این زیرآرایه ها را به زیرآرایه های کوچکتر تقسیم می کنیم تا زمانی که چندین زیرآرایه با یک عنصر در آنها داشته باشیم. حال، ایده اینجاست که یک آرایه با یک عنصر از قبل مرتب شده است، بنابراین هنگامی که آرایه اصلی را به زیرآرایه هایی که فقط یک عنصر دارند تقسیم می کنیم، با موفقیت مشکل خود را به مسائل پایه تقسیم می کنیم.
و سپس باید تمام این زیرآرایه های مرتب شده را گام به گام با هم ادغام کنیم تا یک آرایه مرتب شده واحد تشکیل دهیم.
بیایید یک آرایه با مقادیر {14، 7، 3، 12، 9، 11، 6، 12} در نظر بگیریم.
در شکل بالا ما یک نمایش تصویری از نحوه مرتب‌سازی ادغام مرتب‌سازی آرایه داده‌شده داریم.
👈 در مرتب سازی ادغام مراحل زیر را انجام می دهیم:
یک متغیر p را می گیریم و شاخص شروع آرایه خود را در آن ذخیره می کنیم. و یک متغیر دیگر r را می گیریم و آخرین اندیس آرایه را در آن ذخیره می کنیم.
سپس وسط آرایه را با استفاده از p+rمیکنیم سپس حاصل را تقسیم بر 2 میکنیم که وسط آرایه مشخص را می کنیم و اندیس میانی را به صورت q مشخص می کنیم و آرایه را به دو زیرآرایه از p تا q و از q + 1 تا شاخص r تقسیم می کنیم.
سپس این 2 زیرآرایه را دوباره تقسیم می کنیم، همانطور که آرایه اصلی خود را تقسیم کردیم و این ادامه می یابد.
هنگامی که آرایه اصلی را به زیرآرایه هایی با عناصر تک تقسیم کردیم، سپس شروع به ادغام زیرآرایه ها می کنیم.
📣👨💻 @AlgorithmDesign_DataStructuer
همانطور که می دانیم که مرتب‌سازی ادغام از قانون تقسیم برای شکستن مسئله به مسائل فرعی استفاده می‌کندکه می توان گفت از الگوریتم Divide-and-conquer استفاده می شود،که مشکل در این مورد مرتب کردن یک آرایه معین است.
در مرتب سازی ادغام، آرایه داده شده را در میانه راه می شکنیم، به عنوان مثال اگر آرایه اصلی 6 عنصر داشته باشد، مرتب سازی ادغامی آن را به دو زیرآرایه با 3 عنصر تقسیم می کند.
اما شکستن آرایه اصلی به 2 زیرآرایه کوچکتر به ما در مرتب سازی آرایه کمکی نمی کند.
بنابراین ما این زیرآرایه ها را به زیرآرایه های کوچکتر تقسیم می کنیم تا زمانی که چندین زیرآرایه با یک عنصر در آنها داشته باشیم. حال، ایده اینجاست که یک آرایه با یک عنصر از قبل مرتب شده است، بنابراین هنگامی که آرایه اصلی را به زیرآرایه هایی که فقط یک عنصر دارند تقسیم می کنیم، با موفقیت مشکل خود را به مسائل پایه تقسیم می کنیم.
و سپس باید تمام این زیرآرایه های مرتب شده را گام به گام با هم ادغام کنیم تا یک آرایه مرتب شده واحد تشکیل دهیم.
بیایید یک آرایه با مقادیر {14، 7، 3، 12، 9، 11، 6، 12} در نظر بگیریم.
در شکل بالا ما یک نمایش تصویری از نحوه مرتب‌سازی ادغام مرتب‌سازی آرایه داده‌شده داریم.
👈 در مرتب سازی ادغام مراحل زیر را انجام می دهیم:
یک متغیر p را می گیریم و شاخص شروع آرایه خود را در آن ذخیره می کنیم. و یک متغیر دیگر r را می گیریم و آخرین اندیس آرایه را در آن ذخیره می کنیم.
سپس وسط آرایه را با استفاده از p+rمیکنیم سپس حاصل را تقسیم بر 2 میکنیم که وسط آرایه مشخص را می کنیم و اندیس میانی را به صورت q مشخص می کنیم و آرایه را به دو زیرآرایه از p تا q و از q + 1 تا شاخص r تقسیم می کنیم.
سپس این 2 زیرآرایه را دوباره تقسیم می کنیم، همانطور که آرایه اصلی خود را تقسیم کردیم و این ادامه می یابد.
هنگامی که آرایه اصلی را به زیرآرایه هایی با عناصر تک تقسیم کردیم، سپس شروع به ادغام زیرآرایه ها می کنیم.
📣👨💻 @AlgorithmDesign_DataStructuer
🙏7👨💻1
👍7👨💻1
الگوریتم کروسکال چگونه کار می کند؟
در الگوریتم کروسکال از لبه هایی با کمترین وزن شروع می کنیم و لبه ها را تا رسیدن به هدف ادامه می دهیم. مراحل پیاده سازی الگوریتم کروسکال به شرح زیر است:
ابتدا تمام لبه ها را از وزن کم تا زیاد مرتب کنید.
حالا لبه را با کمترین وزن بردارید و به درخت پوشا اضافه کنید. اگر لبه ای که باید اضافه شود چرخه ایجاد می کند، لبه را رد کنید.
به اضافه کردن لبه ها ادامه دهید تا به همه رئوس برسیم و یک درخت پوشا حداقل ایجاد شود.
توجه: باید توجه داشته باشد که با اضافه کردن لبه ها باعث ایجاد دور نشود که در این صورت اشتباه به دست خواهد امد.
کاربردهای الگوریتم کروسکال عبارتند از:
از الگوریتم کروسکال می توان برای چیدمان سیم کشی برق در بین شهرها استفاده کرد.
می توان از آن برای برقراری اتصالات LAN استفاده کرد.
به مثاال بالا توجه کنید.
📣👨💻 @AlgorithmDesign_DataStructuer
در الگوریتم کروسکال از لبه هایی با کمترین وزن شروع می کنیم و لبه ها را تا رسیدن به هدف ادامه می دهیم. مراحل پیاده سازی الگوریتم کروسکال به شرح زیر است:
ابتدا تمام لبه ها را از وزن کم تا زیاد مرتب کنید.
حالا لبه را با کمترین وزن بردارید و به درخت پوشا اضافه کنید. اگر لبه ای که باید اضافه شود چرخه ایجاد می کند، لبه را رد کنید.
به اضافه کردن لبه ها ادامه دهید تا به همه رئوس برسیم و یک درخت پوشا حداقل ایجاد شود.
توجه: باید توجه داشته باشد که با اضافه کردن لبه ها باعث ایجاد دور نشود که در این صورت اشتباه به دست خواهد امد.
کاربردهای الگوریتم کروسکال عبارتند از:
از الگوریتم کروسکال می توان برای چیدمان سیم کشی برق در بین شهرها استفاده کرد.
می توان از آن برای برقراری اتصالات LAN استفاده کرد.
به مثاال بالا توجه کنید.
📣👨💻 @AlgorithmDesign_DataStructuer
👨💻4👍2🙏2
👨💻6👌2
👍3👨💻1
👍6🤔2👨💻1
الگوریتم بازگشتی برای یافتن بیشترین مقدار در یک آرایه از اعداد صحیح.
📣👨💻 @AlgorithmDesign_DataStructuer
📣👨💻 @AlgorithmDesign_DataStructuer
👍4👌2👨💻1
👍5👨💻2🎉1
👨💻3👍2
درخت به دو صورت قابل پیاده سازی است که یکی از آن ها آرایه می باشد.
برای درخت هایی که دارای گره زیاد پر یا کامل هستند ، آرایه مناسب خواهد
بود.چرا که تعداد خانه های خالی موجود درآرایه کمتر است.
فلذا ایجاد یک درخت کامل با استفاده از آرایه اگر درخت پر یا کامل باشد مناسب
است. اما اگر از نوع دیگر درخت مثال : اوریب به راست باشد مقرون و به صرفه
نخواهد بود.زیرا بییشتر خانه های آرایه خالی می شود و این برای ما به صرفه نیست.
📣👨💻 @AlgorithmDesign_DataStructuer
برای درخت هایی که دارای گره زیاد پر یا کامل هستند ، آرایه مناسب خواهد
بود.چرا که تعداد خانه های خالی موجود درآرایه کمتر است.
فلذا ایجاد یک درخت کامل با استفاده از آرایه اگر درخت پر یا کامل باشد مناسب
است. اما اگر از نوع دیگر درخت مثال : اوریب به راست باشد مقرون و به صرفه
نخواهد بود.زیرا بییشتر خانه های آرایه خالی می شود و این برای ما به صرفه نیست.
📣👨💻 @AlgorithmDesign_DataStructuer
👨💻4👍2
الگوریتم فلوید
در این الگوریتم از روش Dynamic Programming استفاده شده است که این روش از مرتبه n^3 می باشد که از هزینه بسیار کمتری نسبت به الگوریتم عادی آن دارد که اگر به صورت عادی بخواهیم کوتاه ترین مسیر رو پیدا کنیم فاکتوریلی خواهد شد و این اصلا مناسب نخواهد بود.
📣👨💻 @AlgorithmDesign_DataStructuer
در این الگوریتم از روش Dynamic Programming استفاده شده است که این روش از مرتبه n^3 می باشد که از هزینه بسیار کمتری نسبت به الگوریتم عادی آن دارد که اگر به صورت عادی بخواهیم کوتاه ترین مسیر رو پیدا کنیم فاکتوریلی خواهد شد و این اصلا مناسب نخواهد بود.
📣👨💻 @AlgorithmDesign_DataStructuer
👨💻5
👨💻2