tgoop.com/Fara_Java/94
Last Update:
✳️ مرتب سازی ادغامی (Merge Sort) در جاوا — به زبان ساده
در این راهنما نگاهی به الگوریتم مرتب سازی ادغامی و پیاده‌سازی آن در جاوا خواهیم داشت. مرتب‌سازی ادغامی یکی از مؤثرترین تکنیک‌های مرتب‌سازی بر مبنای پارادایم «تقسیم و حل» (divide and conquer) است.
══ فهرست مطالب ══
○ الگوریتم مرتب سازی ادغامی
○ پیاده‌سازی
○ پیچیدگی
○ سخن پایانی
🔸 الگوریتم مرتب سازی ادغامی
مرتب‌سازی ادغامی یک الگوریتم «تقسیم و حل» است که در آن ابتدا مسئله به مسائل فرعی تقسیم می‌شود. زمانی که راه‌حل‌ها برای مسائل فرعی آماده شد، مجدداً آن‌ها را با هم ترکیب می‌کنیم تا راه‌حل نهایی برای مسئله اصلی به دست آید.
این یکی از الگوریتم‌هایی است که با استفاده از «بازگشت» (recursion) به سادگی پیاده‌سازی می‌شود، چون به جای مسئله اصلی با مسائل فرعی سر و کار داریم.
الگوریتم آن را می‌توان به صورت فرایند ۲ مرحله‌ای زیر توصیف کرد:
▫️ تقسیم: در این مرحله آرایه ورودی به دو نیمه تقسیم می‌شود. محور تقسیم نقطه میانی آرایه است. این مرحله به صورت بازگشتی روی همه آرایه‌های نیمه انجام می‌یابد تا این که دیگر نیمه آرایه‌ای برای تقسیم وجود نداشته باشد.
▫️ حل: در این مرحله باید آرایه‌های تقسیم‌شده را مرتب‌سازی و ادغام کنیم و این کار از بخش زیرین به سمت بالا برای به دست آوردن آرایه مرتب انجام می‌یابد.
🔸 پیاده‌سازی
برای پیاده‌سازی الگوریتم فوق، یک تابع مرتب‌سازی ادغامی می‌نویسیم که یک آرایه ورودی و طولانی را به عنوان پارامتر می‌گیرد. این یک تابع بازگشتی خواهد بود، بنابراین به یک شرایط پایه و بازگشت نیاز داریم.
شرایط پایه در صورتی بررسی می‌شوند که طول آرایه برابر با ۱ باشد، و فقط در این حالت بازگشت می‌یابد. در بقیه موارد فراخوانی بازگشتی اجرا خواهد شد.
برای حالت بازگشتی اندیس میانه را پیدا کرده و دو آرایه موقت l و r را ایجاد می‌کنیم. سپس تابع mergeSort به صورت بازگشتی برای هر دو آرایه فرعی فراخوانی می‌شود:
public static void mergeSort(int[] a, int n) {
if (n < 2) {
return;
}
int mid = n / 2;
int[] l = new int[mid];
int[] r = new int[n - mid];
for (int i = 0; i < mid; i++) {
l[i] = a[i];
}
for (int i = mid; i < n; i++) {
r[i - mid] = a[i];
}
mergeSort(l, mid);
mergeSort(r, n - mid);
merge(a, l, r, mid, n - mid);
}
مطالعه ادامه مطلب 👇👇
🔗 مرتب سازی ادغامی (Merge Sort) در جاوا — به زبان ساده — کلیک کنید (+)
📌 کانال اختصاصی آموزشی برنامه‌نویسی جاوا
آخرین مطالب علمی، مقالات رایگان و ویدئوهای آموزشی برنامه‌نویسی جاوا را در کانال اختصاصی [@Fara_Java] دنبال کنید. 👇
@Fara_Java — مطالب و آموزش‌های برنامه‌نویسی جاوا فرادرس
BY Fara_Java | فرا جاوا: آموزش برنامه‌نویسی جاوا
Share with your friend now:
tgoop.com/Fara_Java/94