Merge Sort یکی از الگوریتم های پایه علوم کامپیوتر است که در سال 1945 توسط ریاضیدان بزرگ جان فون نویمان فرموله شد. در حین شرکت در پروژه منهتن، نیومن با نیاز به پردازش کارآمد حجم عظیمی از داده ها مواجه شد. روشی که او توسعه داد از اصل "تفرقه بینداز و حکومت کن" استفاده می کرد که زمان مورد نیاز برای کار را به میزان قابل توجهی کاهش داد.
اصل و استفاده از الگوریتم
روش مرتب‌سازی ادغام در مسائل مرتب‌سازی ساختارهایی استفاده می‌شود که به عناصری مانند آرایه‌ها، فهرست‌ها، جریان‌ها دسترسی دارند.
در طول پردازش، بلوک داده اولیه به اجزای کوچک تقسیم می شود، تا یک عنصر، که در واقع یک لیست مرتب شده است. سپس به ترتیب صحیح دوباره مونتاژ می شود.
مرتب‌سازی آرایه‌ای با طول معین به یک ناحیه حافظه اضافی با همان اندازه نیاز دارد که در آن آرایه مرتب‌سازی شده در قسمت‌هایی جمع‌آوری می‌شود.
از این روش می توان برای سفارش هر نوع داده قابل مقایسه، مانند اعداد یا رشته ها استفاده کرد.
ادغام مرتب شدنمودار
برای درک الگوریتم، بیایید تجزیه و تحلیل آن را از پایان شروع کنیم - از مکانیسم ادغام بلوک های مرتب شده.
بیایید تصور کنیم که دو آرایه از اعداد مرتب شده به هر شکلی داریم که باید با یکدیگر ترکیب شوند تا مرتب سازی شکسته نشود. برای سادگی، اعداد را به ترتیب صعودی مرتب می کنیم.
مثال ابتدایی: هر دو آرایه از یک عنصر تشکیل شده اند.
int arr1={31}; int arr2={18};
برای ادغام آنها، باید عنصر صفر آرایه اول (فراموش نکنید که شماره گذاری از صفر شروع می شود) و عنصر صفر آرایه دوم را بگیرید. اینها به ترتیب 31 و 18 هستند. با توجه به شرایط مرتب سازی، عدد 18 باید اول باشد، زیرا کمتر است. فقط اعداد را به ترتیب صحیح قرار دهید:
int نتیجه={18, 31};
بیایید به یک مثال پیچیده تر نگاه کنیم، که در آن هر آرایه از چندین عنصر تشکیل شده است:
int arr1={2، 17، 19، 45}; int arr2={5, 6, 21, 30};
الگوریتم ادغام شامل مقایسه متوالی عناصر کوچکتر و قرار دادن آنها در آرایه حاصل به ترتیب صحیح است. برای پیگیری شاخص های فعلی، اجازه دهید دو متغیر - index1 و index2 را معرفی کنیم. در ابتدا، آنها را صفر می کنیم، زیرا آرایه ها مرتب شده اند و کوچکترین عناصر در ابتدا هستند.
int index1=0; int index2=0;
بیایید کل فرآیند ادغام را مرحله به مرحله بنویسیم:
- عنصر با index1 را از آرایه arr1 و عنصر با index2 را از آرایه arr2 بگیرید.
- مقایسه کنید، کوچکترین آنها را انتخاب کنید و قرار دهیدآرایه حاصل.
- افزایش شاخص فعلی عنصر کوچکتر 1.
- از مرحله اول ادامه دهید.
در اولین مدار، وضعیت به این صورت خواهد بود:
index1=0; index2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; نتیجه[0]=arr1[0]; // نتیجه=[2]
در پیچ دوم:
index1=1; index2=0; arr1 [1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; نتیجه[1]=arr2[0]; // نتیجه=[2، 5]
سوم:
index1=1; index2=1; arr1 [1]=17; arr2 [1]=6; arr1 [1] > arr2 [1]; index2++; نتیجه[2]=arr2[1]; // نتیجه=[2، 5، 6]
و به همین ترتیب، تا زمانی که نتیجه یک آرایه کاملا مرتب شده باشد: {2، 5، 6، 17، 21، 19، 30، 45}.
اگر آرایه هایی با طول های مختلف ادغام شوند، ممکن است مشکلات خاصی ایجاد شود. اگر یکی از شاخص‌های فعلی به آخرین عنصر رسیده باشد، و هنوز اعضایی در آرایه دوم باقی مانده باشند، چه می‌شود؟
int arr1={1, 4}; int arr2={2، 5، 6، 7، 9}; // 1 مرحله index1=0, index2=0; 1 2 نتیجه={1، 2}; // 3 مرحله index1=1, index2=1; 4 < 5 نتیجه={1، 2، 4}; //4 مرحله index1=2, index2=1 ??
متغیر index1 به مقدار 2 رسیده است، اما آرایه arr1 عنصری با آن شاخص ندارد. همه چیز در اینجا ساده است: فقط عناصر باقی مانده از آرایه دوم را به آرایه حاصل منتقل کنید و ترتیب آنها را حفظ کنید.
نتیجه={1، 2، 4، 5، 6، 7، 9};
این وضعیت به ما نشان دهنده نیاز استشاخص چک فعلی را با طول آرایه در حال ادغام مطابقت دهید.
طرح ادغام برای دنباله های مرتب شده (A و B) با طول های مختلف:
- اگر طول هر دو دنباله بزرگتر از 0 است، A[0] و B[0] را مقایسه کنید و کوچکتر را به بافر منتقل کنید.
- اگر طول یکی از دنباله ها 0 است، عناصر باقیمانده دنباله دوم را بردارید و بدون تغییر ترتیب آنها، به انتهای بافر بروید.
اجرای مرحله دوم
نمونه ای از پیوستن دو آرایه مرتب شده در جاوا در زیر آورده شده است.
int a1=int جدید {21، 23، 24، 40، 75، 76، 78، 77، 900، 2100، 2200، 2300، 2400، 2500}; int a2=int جدید {10، 11، 41، 50، 65، 86، 98، 101، 190، 1100، 1200، 3000، 5000}; int a3=int[a1.length + a2.length] جدید؛ int i=0, j=0; برای (int k=0; k a1.length-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } else { int b=a2[j]; a3[k]=b; j++; } }
اینجا:
- a1 و a2 آرایه های مرتب شده اصلی هستند که باید ادغام شوند؛
- a3 - آرایه نهایی؛
- i و j اندیس های عناصر جاری برای آرایه های a1 و a2 هستند.
شرایط if اول و دوم تضمین می کند که شاخص ها از اندازه آرایه فراتر نمی روند. بلوک های شرط سوم و چهارم به ترتیب به آرایه حاصل از عنصر کوچکتر منتقل می شوند.
تفرقه و سلطه
بنابراین، ما یاد گرفته ایم که مرتب شده ها را ادغام کنیممجموعه ای از ارزش ها می توان گفت که قسمت دوم الگوریتم مرتب سازی ادغام - خود ادغام - قبلا مرتب شده است.
اما، هنوز باید بدانید که چگونه از آرایه مرتب نشده اصلی اعداد به چندین آرایه مرتب شده که می توانند ادغام شوند، برسیم.
بیایید مرحله اول الگوریتم را در نظر بگیریم و نحوه جداسازی آرایه ها را بیاموزیم.
این کار دشواری نیست - لیست اصلی مقادیر به نصف تقسیم می شود، سپس هر قسمت نیز دوشاخه می شود، و به همین ترتیب تا زمانی که بلوک های بسیار کوچک به دست آیند.
طول چنین عناصر حداقلی می تواند برابر با یک باشد، یعنی آنها خودشان می توانند یک آرایه مرتب شده باشند، اما این شرط ضروری نیست. اندازه بلوک از قبل تعیین می‌شود و هر الگوریتم مرتب‌سازی مناسبی که با آرایه‌هایی با اندازه‌های کوچک به طور موثر کار می‌کند (مثلاً مرتب‌سازی سریع یا مرتب‌سازی درج) می‌تواند برای سفارش آن استفاده شود.
به نظر می رسد.
// آرایه اصلی {34، 95، 10، 2، 102، 70}؛ // اولین تقسیم {34، 95، 10} و {2، 102، 70}؛ // تقسیم دوم {34} و {95، 10} و {2} و {102، 70}
بلوک‌های به‌دست‌آمده، متشکل از 1-2 عنصر، بسیار آسان قابل چیدمان هستند.
بعد از آن، باید آرایه های کوچک از قبل مرتب شده را به صورت جفت ادغام کنید، و ترتیب اعضا را حفظ کنید، که قبلاً این کار را یاد گرفته ایم.
اجرای مرحله اول
پارتیشن بندی بازگشتی یک آرایه در زیر نشان داده شده است.
void mergeSort(T a، شروع طولانی، پایان طولانی) { long split; اگر(شروع < پایان) { split=(شروع + پایان)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); ادغام (یک، شروع، تقسیم، پایان)؛ } }
چه اتفاقی در این کد می افتد:
-
تابع mergeSort آرایه اولیه
a
و مرزهای چپ و راست منطقه ای که باید مرتب شوند را دریافت می کند (شاخص ها شروع و
- پایان).
-
اگر طول این بخش بیشتر از یک باشد (
شروع < پایان
)، آنگاه به دو قسمت تقسیم می شود (با شاخص
- split)، و هر یک به صورت بازگشتی مرتب شده اند.
-
در فراخوانی تابع بازگشتی برای سمت چپ، شاخص شروع نمودار و شاخص
split
ارسال می شود. برای قسمت مناسب، به ترتیب، ابتدا
- (Split + 1) و پایان آخرین فهرست بخش اصلی خواهد بود.
-
عملکرد
merge
دو دنباله مرتب شده دریافت می کند (
a[شروع]…a[split]
و
- a[تقسیم +1]…a[پایان]) و آنها را به ترتیب ادغام می کند.
مکانیک تابع ادغام در بالا مورد بحث قرار گرفته است.
طرح کلی الگوریتم
روش آرایه مرتب سازی ادغام شامل دو مرحله بزرگ است:
- آرایه اصلی مرتب نشده را به قطعات کوچک تقسیم کنید.
- آنها را با پیروی از قانون مرتب سازی به صورت جفت جمع آوری کنید.
یک کار بزرگ و پیچیده به کارهای ساده زیادی تقسیم می شود که به طور متوالی حل می شوند و به نتیجه دلخواه می رسند.
ارزیابی روش
پیچیدگی زمانی مرتب‌سازی ادغام با ارتفاع درخت تقسیم شده تعیین می‌شودالگوریتم و برابر است با تعداد عناصر آرایه (n) ضربدر لگاریتم آن (log n). چنین تخمینی لگاریتمی نامیده می شود.
این هم یک مزیت و هم یک ضرر روش است. زمان اجرای آن حتی در بدترین حالت، زمانی که آرایه اصلی به ترتیب معکوس مرتب می شود، تغییر نمی کند. با این حال، هنگام پردازش داده های کاملاً مرتب شده، الگوریتم افزایش زمانی ارائه نمی دهد.
همچنین توجه به هزینه حافظه روش مرتب‌سازی ادغام مهم است. اندازه آنها برابر با مجموعه اصلی است. در این منطقه اختصاص داده شده اضافی، یک آرایه مرتب شده از قطعات مونتاژ می شود.
پیاده سازی الگوریتم
مرتب ادغام پاسکال در زیر نشان داده شده است.
رویه MergeSort(name: string; var f: text); Var a1، a2، s، i، j، kol، tmp: عدد صحیح. f1, f2: متن; ب: بولی شروع:=0; اختصاص (f, name); تنظیم مجدد (f)؛ در حالی که EOF(f) شروع به خواندن نمی کند (f, a1). inc(col); پایان؛ بستن (f); Assign(f1, '{name of 1st auxiliary file}'); Assign(f2, '{نام فایل کمکی دوم}'); s:=1; در حالی که (s<kol) شروع به تنظیم مجدد (f) می کند. بازنویسی (f1); بازنویسی (f2); برای i:=1 تا kol div 2 شروع به خواندن (f, a1) کنید. Write(f1, a1, ' '); پایان؛ اگر (kol div 2) mod s0 سپس tmp:=kol div 2 را شروع کنید. در حالی که tmp mod s0 شروع به خواندن (f, a1) می کند. Write(f1, a1, ' '); inc(tmp); پایان؛ پایان؛ در حالی که EOF(f) شروع به خواندن (f, a2) نمی کند. Write(f2, a2, ' '); پایان؛ بستن (f); بستن (f1); بستن (f2)؛ بازنویسی (f)؛ ریست (f1)؛ تنظیم مجدد (f2)؛ Read(f1, a1)؛ Read(f2, a2)؛ در حالی که (نه EOF(f1)) و (نه EOF(f2)) i:=0; j:=0; ب:=درست در حالی که (b) و (نه EOF(f1)) و (نه EOF(f2)) شروع می شوند اگر (a1<a2) سپس شروع کنیدWrite(f, a1, ' '); Read(f1, a1)؛ Inc(i)؛ End other begin Write(f, a2, ' '); Read(f2, a2)؛ inc(j); پایان؛ اگر (i=s) یا (j=s) سپس b:=false; پایان؛ اگر b نیست، هنگامی که (i<s) و (نه EOF(f1)) شروع می شود شروع کنید Write(f, a1, ''). Read(f1, a1)؛ Inc(i)؛ پایان؛ در حالی که (j<s) و (نه EOF(f2)) شروع به نوشتن می کنند (f, a2, ' '); Read(f2, a2)؛ inc(j); پایان؛ پایان؛ پایان؛ در حالی که EOF(f1) نیست، tmp:=a1; Read(f1, a1)؛ اگر EOF(f1) نیست، سپس Write(f, tmp, ' ') else Write(f, tmp); پایان؛ در حالی که EOF(f2) نیست، tmp:=a2; Read(f2, a2)؛ اگر EOF(f2) نیست، سپس Write(f, tmp, ' ') else Write(f, tmp); پایان؛ بستن (f); بستن (f1); بستن (f2)؛ s:=s2; پایان؛ پاک کردن (f1)؛ پاک کردن (f2)؛ پایان؛
از نظر بصری، عملکرد الگوریتم به این شکل است (بالا - دنباله نامرتب، پایین - مرتب شده).
مرتب‌سازی داده‌های خارجی
خیلی اوقات نیاز به مرتب سازی برخی از داده های موجود در حافظه خارجی رایانه وجود دارد. در برخی موارد، اندازه قابل توجهی دارند و نمی توان آنها را در RAM قرار داد تا دسترسی به آنها را تسهیل کند. برای چنین مواردی از روش های مرتب سازی خارجی استفاده می شود.
نیاز به دسترسی به رسانه خارجی کارایی زمان پردازش را کاهش می دهد.
پیچیدگی کار این است که الگوریتم فقط می تواند به یک عنصر از جریان داده در یک زمان دسترسی داشته باشد. و در این مورد، یکی از بهترین نتایج با روش ادغام مرتب سازی نشان داده می شود، که می تواند عناصر دو فایل را به ترتیب یکی پس از دیگری مقایسه کند.
خواندن داده ها ازمنبع خارجی، پردازش و نوشتن آنها در فایل نهایی در بلوک های مرتب شده (سری) انجام می شود. با توجه به نحوه کار با اندازه سری های سفارشی، دو نوع مرتب سازی وجود دارد: ادغام ساده و طبیعی.
ادغام ساده
با یک ادغام ساده، طول سری ثابت می شود.
بنابراین، در فایل مرتب نشده اصلی، همه سری ها از یک عنصر تشکیل شده اند. بعد از مرحله اول، اندازه به دو افزایش می یابد. بعدی - 4، 8، 16 و غیره.
اینطور عمل می کند:
- فایل منبع (f) به دو فایل کمکی تقسیم می شود - f1، f2.
- آنها دوباره در یک فایل (f) ادغام می شوند، اما در همان زمان همه عناصر به صورت جفت مقایسه می شوند و جفت تشکیل می شوند. اندازه سری در این مرحله دو می شود.
- مرحله 1 تکرار می شود.
- مرحله 2 تکرار می شود، اما 2 های از قبل مرتب شده ادغام می شوند تا 4 های مرتب شده را تشکیل دهند.
- حلقه ادامه می یابد، سری در هر تکرار افزایش می یابد، تا زمانی که کل فایل مرتب شود.
از کجا می دانید که مرتب سازی بیرونی با یک ادغام ساده کامل شده است؟
- طول سری جدید (پس از ادغام) نه کمتر از تعداد کل عناصر؛
- فقط یک قسمت باقی مانده است؛
- فایل کمکی f2 خالی ماند.
معایب ادغام ساده عبارتند از: از آنجایی که طول اجرا در هر پاس ادغام ثابت است، پردازش داده های جزئی مرتب شده به اندازه داده های کاملا تصادفی طول می کشد.
همجوشی طبیعی
این روش طول را محدود نمی کندسری، اما حداکثر ممکن را انتخاب می کند.
الگوریتم مرتب‌سازی:
- خواندن دنباله اولیه از فایل f. اولین عنصر دریافتی در فایل f1 نوشته می شود.
- اگر ورودی بعدی شرایط مرتب‌سازی را برآورده می‌کند، در آنجا نوشته می‌شود، اگر نه، در فایل کمکی دوم f2 نوشته می‌شود.
- به این ترتیب، همه رکوردهای فایل منبع توزیع می شوند و یک دنباله مرتب شده در f1 تشکیل می شود که اندازه فعلی سری را تعیین می کند.
- فایل‌های f1 و f2 ادغام شدند.
- چرخه تکرار می شود.
به دلیل ثابت نبودن سایز سریال، لازم است انتهای سکانس با کاراکتر خاصی مشخص شود. بنابراین، هنگام ادغام، تعداد مقایسه ها افزایش می یابد. علاوه بر این، اندازه یکی از فایل های کمکی ممکن است نزدیک به اندازه اصلی باشد.
به طور متوسط، ادغام طبیعی کارآمدتر از ادغام ساده با مرتب‌سازی خارجی است.
ویژگی های الگوریتم
هنگام مقایسه دو مقدار یکسان، روش ترتیب اصلی آنها را حفظ می کند، یعنی پایدار است.
فرایند مرتب سازی را می توان با موفقیت به چندین رشته تقسیم کرد.
این ویدئو به وضوح عملکرد الگوریتم مرتب سازی ادغام را نشان می دهد.
