از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
مرتب‌سازی درج در جاوا اسکریپت در این مقاله توضیح خواهیم داد که در پس مرتب‌سازی درج چیست و آن را در جاوا اسکریپت پیاده‌سازی می‌کنیم. Insertion Sort یکی از ساده‌ترین الگوریتم‌های مرتب‌سازی است. این بسیار شهودی، پایدار، در محل، و از نوع مقایسه است. الگوریتم مرتب‌سازی پایدار الگوریتمی است که در آن دو شی با کلیدهای مساوی ظاهر می‌شوند…
سرفصلهای مطلب
معرفی
در این مقاله، ایده Insertion Sort چیست و آن را در جاوا اسکریپت پیاده سازی می کنیم.
Insertion Sort یکی از ساده‌ترین الگوریتم‌های مرتب‌سازی است. بسیار شهودی است، پایدار، در محل، و از نوع مقایسه.
آ پایدار الگوریتم مرتب‌سازی الگوریتمی است که در آن دو شی با کلیدهای مساوی به ترتیبی که در آرایه ورودی برای مرتب‌سازی ظاهر می‌شوند، در خروجی مرتب‌شده ظاهر می‌شوند.
به عبارت دیگر، اگر یک الگوریتم مرتب‌سازی پایدار باشد، عناصر معادل پس از انجام الگوریتم مرتب‌سازی موقعیت نسبی خود را حفظ می‌کنند.
یک درجا الگوریتم الگوریتمی است که از هیچ حافظه اضافی یا ساختار داده ای استفاده نمی کند و مکان های حافظه اصلی عناصر موجود در آرایه یا لیست ورودی را بازنویسی می کند.
در نهایت، الف الگوریتم مقایسه یکی است که در طول اجرای آن، فقط عناصر لیست را از طریق یک عملیات مقایسه انتزاعی می خواند. بسته به روی نوع داده و هدف شما، مقایسه را می توان از طریق یک عملگر رابطه ای یا از طریق یک تابع مقایسه سفارشی انجام داد.
با وجود پیچیدگی زمانی بسیار زیاد برای یک الگوریتم مرتب‌سازی، مرتب‌سازی درج می‌تواند بسیار مفید باشد، حتی گاهی اوقات می‌تواند از برخی از کارآمدترین الگوریتم‌های مرتب‌سازی، مانند مرتب سازی سریع یا ادغام مرتب سازی، روی مجموعه های کوچک
این به ندرت به عنوان یک الگوریتم مستقل استفاده می شود – شما معمولاً از یک الگوریتم مرتب سازی سریع مانند Quicksort استفاده می کنید و آخرین “پایان های سست” را با Insertion Sort به پایان می رسانید زیرا برای آن کار بسیار کارآمد است.
مرتب سازی درج
ایده پشت مرتب سازی درج اغلب با روشی که مردم هنگام بازی رامی دسته کارت ها را مرتب می کنند مقایسه می شود.
در این بازی با ورق، فروشنده به هر بازیکن کارت می دهد. سپس، بازیکنان کارت هایی را که به آنها داده می شود، یکی یکی می گیرند و با قرار دادن هر کارت در جای خود، آنها را به ترتیب صعودی مرتب می کنند.
در طول این کل process، بازیکنان یک انبوه کارت مرتب شده را در دست دارند، در حالی که توده مرتب نشده ای که از آن کارت های جدید می گیرند جلوی آنها است.
یکی از ویژگی های بسیار مفید Insertion Sort این است که نیازی به دانستن کل آرایه از قبل برای مرتب شدن ندارد – فقط عناصر داده شده را یکی یکی وارد می کند.
وقتی می‌خواهیم عناصر بیشتری را در یک آرایه مرتب‌سازی‌شده اضافه کنیم، واقعاً مفید است، زیرا Insertion Sort عناصر جدید را در مکان‌های مناسب‌شان بدون متوسل شدن به کل مجموعه اضافه می‌کند.
در اینجا یک نمایش بصری از روش عملکرد Insertion Sort آورده شده است:
پیاده سازی مرتب سازی درج
اکنون که ایده پشت Insertion Sort را فهمیدیم، می‌توانیم حرکت کنیم روی به اجرا:
function insertionSort(inputArr) {
let n = inputArr.length;
for (let i = 1; i < n; i++) {
// Choosing the first element in our unsorted subarray
let current = inputArr(i);
// The last element of our sorted subarray
let j = i-1;
while ((j > -1) && (current < inputArr(j))) {
inputArr(j+1) = inputArr(j);
j--;
}
inputArr(j+1) = current;
}
return inputArr;
}
تکرار از عنصر دوم شروع می شود. اولین عنصر را به صورت پیش فرض مرتب شده در نظر می گیریم. برای هر تکرار، ما آن را پیگیری می کنیم current عنصر هر یک current عنصر اولین عنصر آرایه مرتب نشده خواهد بود – و هر عنصر قبل از آن به آرایه مرتب شده تعلق دارد.
از طریق الف while حلقه، از میان آرایه مرتب شده می گذریم و عناصر را به سمت راست منتقل می کنیم و فضایی برای آن باز می کنیم current عنصری که باید درج شود
هنگامی که مکان مناسبی برای آن پیدا کردیم، current عنصر در شکاف تازه باز شده وارد می شود. این process برای هر تکرار تکرار می شود تا آرایه مرتب شود.
حال، بیایید یک آرایه را پر کنیم و الگوریتم مرتب سازی خود را فراخوانی کنیم:
let inputArr = (5, 2, 4, 6, 1, 3);
insertionSort(inputArr);
console.log(inputArr);
خروجی این آرایه به صورت زیر خواهد بود:
(6) (1, 2, 3, 4, 5, 6)
بیایید این مثال را مرحله به مرحله مرور کنیم:
تکرار اول:
آرایه مرتب شده: 5
آرایه مرتب نشده: 2، 4، 6، 1، 3
- اولین عنصر در آرایه مرتب نشده ما 2 است.
- 2 < 5، بنابراین ما 5 را یک مکان به سمت راست حرکت می دهیم.
آرایه مرتب شده: _، 5
- 2 در نقطه سمت راست خود قرار می گیرد.
تکرار دوم:
آرایه مرتب شده: 2، 5
آرایه مرتب نشده: 4، 6، 1، 3
- اولین عنصر در آرایه مرتب نشده ما 4 است.
- 4 < 5، بنابراین ما 5 را یک مکان به سمت راست حرکت می دهیم.
آرایه مرتب شده: 2، _، 5
- 4 !< 2، بنابراین ما 2 را جابجا نمی کنیم.
- 4 در نقطه سمت راست خود قرار می گیرد.
تکرار سوم:
آرایه مرتب شده: 2، 4، 5
آرایه مرتب نشده: 6، 1، 3
- اولین عنصر در آرایه مرتب نشده ما 6 است.
- 6 !< 5، بنابراین ما 5 را جابه جا نمی کنیم.
آرایه مرتب شده: 2، 4، 5
- 6 در نقطه سمت راست خود قرار می گیرد.
این کار تا زمانی تکرار می شود که با یک آرایه مرتب شده مواجه شویم: 1, 2, 3, 4, 5, 6.
ما می توانیم در هر یک از این تکرارها متوجه یک تغییر ناپذیر شویم. برای k-th تکرار حلقه ما، فاصله زمانی (0,k) مرتب سازی تضمین شده است.
مقایسه زمان
بهترین زمان اجرای Insertion Sort خطی است و اگر آرایه ورودی ما مرتب شده باشد، آن را دریافت می کنیم. این بدان معنی است که مرتب سازی درج در بررسی مرتب شدن یا نبودن آرایه معجزه می کند.
با این حال، بدترین و متوسط پیچیدگی زمانی O(n2) که برای یک الگوریتم مرتب سازی بسیار بد است، به خصوص زمانی که برای آرایه ها یا لیست هایی با اندازه بزرگتر اعمال می شود. در این مورد، Quicksort یا Merge Sort با پیچیدگی O(nlogn) انتخاب بسیار بهتری خواهد بود.
از طرف دیگر، به عنوان یکی از سریع ترین الگوریتم های مرتب سازی درجه دوم، مرتب سازی درج معمولاً از مرتب سازی حباب، مرتب سازی گنوم و مرتب سازی انتخاب بهتر عمل می کند. علاوه بر آن، زمانی که اندازه آرایه ورودی ما بسیار کوچک است (10-20 عنصر)، مرتب سازی درج می تواند حتی از Quicksort و Merge Sort بهتر عمل کند.
به همین دلیل است که جاوا اسکریپت، با وجود استفاده از Quicksort (در کروم) یا Merge Sort (در موزیلا) به عنوان الگوریتم مرتب‌سازی اولیه، از مرتب‌سازی درج نیز استفاده می‌کند. روی مجموعه های کوچک – و پس از مرتب سازی سریع/ادغام، بخش عمده ای از کار را انجام داد.
نتیجه
Insertion Sort یک الگوریتم مرتب سازی مقایسه ای ساده، پایدار، در محل است.
علیرغم اینکه با پیچیدگی درجه دوم بسیار وقت گیر است، زمانی که آرایه ورودی کوچک باشد بسیار مفید است. در این مورد، حتی از متداول‌ترین الگوریتم‌های تقسیم و حکومت کن نیز بهتر عمل می‌کند، به همین دلیل است که جاوا اسکریپت هنگام استفاده از توابع مرتب‌سازی داخلی، از ترکیب Insertion Sort و Merge Sort یا Quicksort استفاده می‌کند.
وقتی صحبت از آرایه‌های با اندازه بزرگتر به میان می‌آید، از سایر الگوریتم‌های مرتب‌سازی درجه دوم، از جمله مرتب‌سازی حباب، مرتب‌سازی Gnome و همچنین مرتب‌سازی انتخابی بهتر عمل می‌کند.
منتشر شده در 1403-01-20 15:11:04
