در این جلسه تیم کدگیت را با آموزش مرتب سازی ادغامی در c++ همراهی کنید.. پیش نیاز این جلسه آشنایی با روش بازگشتی، آرایه و متد است.
مرتب سازی ادغامی
مرتبسازی ادغامی یک الگوریتم مرتبسازی تطبیقی با زمان اجرای nlogn میباشد. در اکثر پیادهسازیها این الگوریتم پایدار میباشد. بدین معنی که این الگوریتم ترتیب ورودیهای مساوی را در خروجی مرتب شده حفظ میکند. این یک مثال از الگوریتم تقسیم و تسخیر میباشد. این الگوریتم در سال ۱۹۴۵ توسط جان فون نویمان اختراع شدهاست.
از نظر مفهومی یک الگوریتم مرتبسازی ادغام بدین صورت کار میکند:
- اگر طول لسیت ۰ یا ۱ باشد آن پیش از این مرتب شدهاست در غیر این صورت
- لیست نامرتب را به دو زیرلیست که اندازه آنها در حدود نصف سایز لیست اولیهاست تقسیم میکند.
- هر زیرلیست را به طور بازگشتی با صدا کردن merge sort مرتب میکند.
- دو تا دوتا زیر لیستها را از آخر ادغام میکند تا به یک لیست برسد
مرتبسازی ادغام ۲ تا ایده اصلی را با هم ترکیب میکند تا زمان اجرایش تقویت شود
- یک لیست کوچک از گامهای کمتری برای مرتبکردن نسبت به یک لیست بزرگ استفاده میکند.
- یرای مرتب کردن دو لیست مرتبشده نسبت به دو لیست نامرتب گامهای کمتری نیاز میباشد به عنوان مثال اگر این لیستها مرتب باشند شما مجبور هستید تا هر لیست را فقط یکبارپیمایش کنید(ویکیپدیا)
پیاده سازی مرتب سازی ادغامی در c++
در توضیحات بالا درباره نحوه کاره مرتب سازی ادغامی صحبت شد. قبل از پیاده سازی در مورد نحوه merge کردن دو آرایه مرتب صحبت میکنیم سپس به پیاده سازی آن خواهیم پرداخت.
ما وقتی دو آرایه مرتب داریم و میخواهیم آنها را با هم ادغام(merge) کنیم باید دو اندیس به ابتدای هر دو آرایه اشاره کند. ما این اندیس ها را i و j مینامیم. سپس کوچکترین مقداری که در اندیس های i و j قرار دارد را برمیداریم و اندیس مورد نظر را یکی به جلو حرکت میدهیم. با این کار ما بین دو آرایه کوچکترین مقدار را برمیداریم و در آرایه کمکی میریزیم.

حال نوبت به پیاده سازی رسیده است. ما برای پیاده سازی متدی به نام sort مینویسیم که یک آرایه ورودی بگیرد و آن را به روش ادغامی مرتب کند.ما در تمامی کد از آرایه ای به نام aux استفاده کردیم که آن را آرایه کمکی مینامند.
void merge(int * a, int * aux, int lo, int mid, int hi) {
for (int k = lo; k <= hi; k++) {
aux[k] = a[k];
}
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid)
a[k] = aux[j++];
else if (j > hi)
a[k] = aux[i++];
else if (aux[j] < aux[i])
a[k] = aux[j++];
else
a[k] = aux[i++];
}
}
void sort(int * a, int *aux, int lo, int hi) {
if (hi <= lo)
return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid + 1, hi);
merge(a, aux, lo, mid, hi);
}
void sort(int *a, int arrsize) {
int aux[arrsize];
sort(a, aux, 0, arrsize - 1);
}
کد مرتب سازی ادغامی در c++ شامل متد های زیر است:
- Merge: این متد دو آرایه را ادغام میکند. دو آرایه ما یکی از اندیس low تا mid آرایه اصلی هستند و دیگری از mid تا high آرایه اصلی هستند(متغیر low و mid و high ورودی های ما هستند) سپس نتیجه را در آرایه کمکی به نام aux میریزد.
- Sort: کد بالا دو متد sort دارد یکی فقط آرایه میگیرد و کل آن را مرتب میکند و دیگری آرایه و اندیس های ابتدا و انتهایی را ورودی میگیرد تا فقط بین این اندیس ها آرایه را مرتب کند. متد که یک ورودی دارد کار با آن راحت تر است.
تست مرتب سازی ادغامی در c++
برای تست کد مرتب سازی ادغامی در c++ کافیست کد main زیر را بزنید.
int main() {
int size = 8;
int a[] = { 1, 5, 3, 7, 2, 6, 4, 8};
sort(a,size);
for (int i = 0; i < size; ++i) {
cout << a[i]<< endl;
}
return 0;
}
خروجی مرتب سازی ادغامی در c++ به صورت زیر است:
1
2
3
4
5
6
7
8