از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
مرتب سازی ادغام در جاوا اسکریپت مرتب سازی به ترتیب آیتم های یک لیست در یک ترتیب خاص (عددی یا الفبایی) اشاره دارد. مرتب‌سازی معمولاً همراه با جستجو استفاده می‌شود. اگر فهرست به صورت بصری و الگوریتمی مرتب شده باشد، به طور کلی جستجو برای یک عنصر (به نام کلید) در یک لیست داده شده آسان تر است. وجود دارد…
سرفصلهای مطلب
معرفی
مرتب سازی به مرتب کردن آیتم های یک لیست به ترتیب خاص (عددی یا الفبایی) اشاره دارد. مرتب‌سازی معمولاً همراه با جستجو استفاده می‌شود.
اگر فهرست به صورت بصری و الگوریتمی مرتب شده باشد، به طور کلی جستجو برای یک عنصر (به نام کلید) در یک لیست داده شده آسان تر است.
راه‌های (الگوریتم‌های) زیادی برای مرتب‌سازی فهرست معینی از عناصر وجود دارد. ادغام مرتب سازی یکی از روش های محبوب تر و کارآمدتر برای انجام این کار است.
در این مقاله، منطق پشت Merge Sort را می بینیم، آن را در جاوا اسکریپت پیاده سازی می کنیم و آن را در عمل تجسم می کنیم. در نهایت به مقایسه Merge Sort با سایر الگوریتم ها از نظر پیچیدگی مکانی و زمانی می پردازیم.
درک منطق پشت مرتب سازی ادغام
مرتب سازی ادغام از مفهوم استفاده می کند تفرقه بینداز و حکومت کن برای مرتب کردن لیست داده شده از عناصر. این مسئله را به زیرمشکلات کوچکتر تقسیم می کند تا زمانی که به اندازه کافی ساده شوند تا مستقیماً حل شوند.
در اینجا مراحل Merge Sort انجام می شود:
- لیست داده شده را به دو نیمه تقسیم کنید (در صورت وجود لیستی با تعداد فرد عناصر تقریباً نصف مساوی).
- تقسیم زیرآرایه ها را به همین ترتیب ادامه دهید تا زمانی که فقط آرایه های تک عنصری باقی بمانید.
- شروع با آرایه های تک عنصری، ادغام زیرآرایه ها به گونه ای که هر زیرآرایه ادغام شده مرتب شود.
- مرحله 3 را تکرار کنید تا به یک آرایه مرتب شده برسید.
بیایید نگاهی به روش عملکرد Merge Sort بیندازیم روی آرایه ای مانند (4, 8, 7, 2, 11, 1, 3):
پیاده سازی Merge Sort در جاوا اسکریپت
اجازه دهید ابتدا کد بنویسیم merge() دو زیرآرایه مرتب شده در یک آرایه مرتب شده است. بسیار مهم است که به خاطر داشته باشید که هر دو زیرآرایه قبلا مرتب شده اند و ما فقط آنها را با استفاده از merge() تابع.
ما می توانیم این کار را با مرور هر دو زیرآرایه و اضافه کردن یک به یک عنصر انجام دهیم تا آرایه حاصل نیز مرتب شود:
function merge(left, right) {
let arr = ()
// Break out of loop if any one of the array becomes empty
while (left.length && right.length) {
// Pick the smaller among the smallest element of left and right sub arrays
if (left(0) < right(0)) {
arr.push(left.shift())
} else {
arr.push(right.shift())
}
}
// Concatenating the leftover elements
// (in case we didn't go through the entire left or right array)
return ( ...arr, ...left, ...right )
}
در این تابع، دو زیرآرایه مرتب شده (left، right) و آنها را ادغام کنید تا یک آرایه مرتب شده به دست آورید. ابتدا یک آرایه خالی ایجاد می کنیم. بعداً، کوچک‌ترین عنصر انتخاب نشده را انتخاب می‌کنیم left و right زیر آرایه ها و فشار دادن آنها به آرایه خالی. ما فقط باید اولین عناصر را بررسی کنیم left و right زیرآرایه ها چون هر دو مرتب شده اند.
در حین انجام این کار، عنصر انتخاب شده را از زیرآرایه حذف می کنیم (این کار با استفاده از shift() تابع). این را ادامه می دهیم process تا زمانی که یکی از زیرآرایه ها خالی شود. پس از آن، عناصر باقیمانده از زیرآرایه غیر خالی (چون از قبل مرتب شده اند) را به آرایه اصلی فشار می دهیم.
همانطور که اکنون کدی برای ادغام دو آرایه مرتب شده داریم (تسخیر قسمتی از تفرقه بینداز و حکومت کناجازه دهید کد نهایی را برای الگوریتم مرتب سازی ادغام خود بنویسیم. این به این معنی است که ما باید به تقسیم آرایه ها ادامه دهیم، تا زمانی که به آرایه هایی برسید که فقط حاوی یک عنصر هستند:
function mergeSort(array) {
const half = array.length / 2
// Base case or terminating case
if(array.length < 2){
return array
}
const left = array.splice(0, half)
return merge(mergeSort(left),mergeSort(array))
}
در اینجا، نقطه میانی را شناسایی کرده و با استفاده از آرایه را به دو زیرآرایه تقسیم می کنیم splice() تابع. اگر تعداد عناصر فرد وجود داشته باشد، عنصر سمت چپ تعداد عناصر کمتری دریافت می کند. ما در حال تقسیم هستیم تا زمانی که آرایه های تک عنصری باقی بمانند (array.length < 2). پس از آن، با استفاده از نوشته های قبلی شروع به ترکیب زیرآرایه ها می کنیم merge() تابع.
حالا که کد را در جای خود داریم، اجازه دهید خروجی اجرای تابع را ببینیم روی مثال قبلی ما:
array = (4, 8, 7, 2, 11, 1, 3);
console.log(mergeSort(array));
که خروجی مورد انتظار را به ما می دهد:
1,2,3,4,7,8,11
کارایی مرتب سازی ادغام
بدترین حالت پیچیدگی زمانی Merge Sort است O(nlogn)، مانند پیچیدگی زمانی بهترین حالت برای QuickSort. وقتی صحبت از سرعت به میان می‌آید، Merge Sort یکی از سریع‌ترین الگوریتم‌های مرتب‌سازی است.
بر خلاف مرتب‌سازی سریع، مرتب‌سازی ادغام یک برنامه نیست درجا الگوریتم مرتب سازی، به این معنی که فضای اضافی به جز آرایه ورودی می گیرد. این به این دلیل است که ما از آرایه های کمکی (کمکی) برای ذخیره آرایه های فرعی استفاده می کنیم. پیچیدگی فضایی مرتب سازی ادغام است بر).
یکی دیگر از مزایای مرتب سازی ادغام این است که به خوبی به چند رشته ای کمک می کند، زیرا هر نیمه مربوطه را می توان مرتب کرد. روی خودش یکی دیگر از روش‌های رایج کاهش زمان اجرا Merge Sort این است که وقتی به زیرآرایه‌های نسبتاً کوچک (~7) رسیدیم متوقف می‌شویم و از Insertion Sort برای مرتب‌سازی آنها استفاده می‌کنیم.
این کار به این دلیل انجام می شود که مرتب سازی درج بسیار خوب عمل می کند روی آرایه های کوچک یا تقریبا مرتب شده اند. بسیار بهتر از همتایان کارآمدتر خود در سطح جهانی.
نتیجه
در این مقاله، منطق پشت الگوریتم Merge Sort، روش پیاده سازی آن در جاوا اسکریپت را دیدیم و با عملکرد آن آشنا شدیم. این یکی از الگوریتم‌های مرتب‌سازی اولیه است و برای ارائه یک مثال واضح از آن بسیار مفید است تفرقه بینداز و حکومت کن استراتژی
منتشر شده در 1403-01-19 03:06:05
