از طریق منوی جستجو مطلب مورد نظر خود در وبلاگ را به سرعت پیدا کنید
Selection Sort در JavaScriptSelection Sort یکی از الگوریتم‌های مرتب‌سازی ساده‌تر و بصری‌تر است. این یک الگوریتم مقایسه در محل، ناپایدار است. این بدان معنی است که مجموعه ورودی را بدون استفاده از ساختارهای داده کمکی تبدیل می کند و ورودی توسط خروجی (الگوریتم در محل) لغو می شود. ضمناً در حین اجرای آن فقط می خواند …
سرفصلهای مطلب
معرفی
Selection Sort یکی از الگوریتم‌های مرتب‌سازی ساده‌تر و بصری‌تر است. یک است الگوریتم مقایسه در محل، ناپایدار.
این بدان معنی است که مجموعه ورودی را بدون استفاده از ساختارهای داده کمکی تبدیل می کند و ورودی توسط خروجی (الگوریتم در محل) لغو می شود.
علاوه بر این، در طول اجرای خود، فقط عناصر لیست را از طریق یک عملیات مقایسه انتزاعی، معمولاً یک عملگر “کمتر یا مساوی” (الگوریتم مقایسه) می خواند.
در نهایت، ترتیب عناصر تکراری پس از مرتب‌سازی حفظ نمی‌شود (الگوریتم ناپایدار).
معمولا زود آموزش داده می شود روی در اکثر دروس علوم کامپیوتر، با توجه به اینکه درک و تبدیل آن به کد بسیار آسان است. با وجود پیچیدگی زمانی درجه دوم، مزایای عملکردی نسبت به برخی از الگوریتم های مرتب سازی پیچیده تر، مانند مرتب سازی سریع یا ادغام مرتب سازی، در برخی موارد خاص
در این مقاله، ایده انتخاب مرتب سازی و پیاده سازی آن در جاوا اسکریپت را توضیح خواهیم داد.
پس از آن، پیچیدگی زمانی آن را تحلیل کرده و آن را با سایر الگوریتم‌های مرتب‌سازی مقایسه می‌کنیم. در نهایت، ما در مورد اینکه چه زمانی می توان از آن استفاده کرد، و همچنین زمانی که باید از آن اجتناب کرد، بحث خواهیم کرد.
انتخاب مرتب سازی
این الگوریتم آرایه ورودی را به دو زیر لیست تقسیم می کند – a مرتب شده است و طبقه بندی نشده فهرست فرعی لیست مرتب شده در ابتدای مجموعه قرار دارد و تمام عناصر سمت راست عنصر مرتب شده نهایی مرتب نشده در نظر گرفته می شوند.
در ابتدا، لیست مرتب شده خالی است، در حالی که بقیه مجموعه مرتب نشده است. Selection Sort از فهرست فرعی مرتب نشده می گذرد و کوچکترین یا بزرگترین عنصر را پیدا می کند.
سپس عنصر با سمت چپ ترین عنصر فهرست فرعی مرتب نشده تعویض می شود. سپس، فهرست فرعی مرتب شده گسترش می یابد تا آن عنصر را در بر گیرد.
این کار تکرار می شود، عنصر برازش را پیدا می کند، آن را با سمت چپ ترین عنصر لیست مرتب نشده عوض می کند، و لیست مرتب شده را برای احاطه کردن آن گسترش می دهد.
پس از هر تکرار، یک عنصر کمتر باید بررسی شود، تا زمانی که کل آرایه یا لیست مرتب شود. به عبارت دیگر، پس از k-th تکرار، اولین ک دسته بندی عناصر آرایه یا لیست تضمین شده است.
بیایید به این نمایش بصری روش عملکرد Selection Sort نگاه کنیم روی آرایه از:
5, 2, 4, 6, 1, 3
اجرای مرتب سازی انتخاب
اکنون که ایده انتخاب مرتب سازی و نمایش بصری آن را فراموش کرده ایم، می توانیم حرکت کنیم روی به پیاده سازی الگوریتم در جاوا اسکریپت:
function selectionSort(inputArr) {
let n = inputArr.length;
for(let i = 0; i < n; i++) {
// Finding the smallest number in the subarray
let min = i;
for(let j = i+1; j < n; j++){
if(inputArr(j) < inputArr(min)) {
min=j;
}
}
if (min != i) {
// Swapping the elements
let tmp = inputArr(i);
inputArr(i) = inputArr(min);
inputArr(min) = tmp;
}
}
return inputArr;
}
ما در حال تکرار در کل آرایه ورودی هستیم و برای هر عنصر آرایه – کوچکترین عدد را در زیرآرایه مرتب نشده پیدا می کنیم. اگر کوچکترین عدد اولین عدد در زیرآرایه مرتب نشده نباشد (در حال حاضر در جای خود نیست)، ما swap آن را با اولین عنصر از زیرآرایه مرتب نشده است.
بدون بررسی اینکه آیا کوچکترین عنصر از قبل اولین عنصر زیرآرایه مرتب نشده است یا خیر، ما مبادله های غیر ضروری را انجام می دهیم.
حالا بیایید آرایه ورودی را اضافه کنیم و تابع خود را فراخوانی کنیم:
let inputArr = (5, 2, 4, 6, 1, 3);
selectionSort(inputArr);
console.log(inputArr);
خروجی این کد به صورت زیر خواهد بود:
(6) (1, 2, 3, 4, 5, 6)
پیچیدگی زمانی
تحلیل پیچیدگی زمانی Selection Sort دشوار نیست.
در اولین تکرار، در سراسر آرایه از n عناصر، ما می سازیم n-1 مقایسه و به طور بالقوه یکی swap. در تکرار دوم خواهیم ساخت n-2 مقایسه ها و غیره روی.
بنابراین، تعداد کل مقایسه ها خواهد بود (n-2) + (n-1) + …+ 1، که جمع می شود n(n-1)/2 = (n2-n)/2. این ما را به یک زمان در حال اجرا هدایت می کند بر2).
بر2) پیچیدگی زمانی بسیار بدی برای الگوریتم مرتب سازی است. هنگام مرتب‌سازی یک مجموعه، از الگوریتم‌های مرتب‌سازی سریعتر استفاده می‌کنید مرتب سازی سریع یا ادغام مرتب سازی با پیچیدگی زمانی O(nlogn).
بهترین عملکرد Selection Sort نیز می باشد بر2)، بنابراین بررسی اینکه آیا آرایه یا لیست مرتب شده است یا خیر نیز واقعاً ناکارآمد است.
از سوی دیگر، در مقایسه با سایر الگوریتم‌های پیچیدگی زمانی درجه دوم مانند مرتب‌سازی حباب‌ها، مرتب‌سازی انتخابی به خوبی خود را حفظ می‌کند و از مرتب‌سازی حبابی و انواع آن و همچنین عملکرد بهتری دارد. مرتب سازی گنوم.
مرتب سازی درجبا این حال، در صورتی که مجموعه تقریبا مرتب شده باشد، می تواند سریعتر از Selection Sort باشد. و Insertion Sort با مجموعه های کوتاه تقریباً بی نظیر است.
انواع مرتب سازی انتخابی
حتی اگر بهترین، بدترین و متوسط عملکرد این الگوریتم باشد بر2)انتخاب مرتب‌سازی برای توسعه کلی الگوریتم‌های مرتب‌سازی بسیار مهم است. این در واقع پایه ای برای برخی از الگوریتم های مرتب سازی بسیار پرکاربرد و کارآمد بود!
شاید معروف ترین نوع آن باشد مرتب سازی پشته، که در داخل از a استفاده می کند پشته ساختار داده برای ذخیره عناصر استفاده از پشته ها می تواند سرعت یافتن و حذف عناصر را افزایش دهد O(logn) زمان.
این یک بهینه سازی بسیار سودمند است که کل زمان اجرا را کاهش می دهد O(n^2) به O(nlogn)، که برای مرتب سازی الگوریتم ها خوب در نظر گرفته می شود.
نوع دیگر آن است مرتب سازی انتخاب دو جهته، شبیه به اینکه Bubble Sort یک همتای دو طرفه دارد. گاهی اوقات به عنوان شناخته شده است مرتب سازی کوکتل (باز هم مشابه Bubble کوکتل شیکر مرتب سازی) و همین کار را با 25٪ مقایسه کمتر انجام می دهد.
نتیجه
Selection Sort یک الگوریتم مرتب‌سازی اساسی و ساده است، بنابراین ناکارآمد است. این به‌عنوان پایه‌ای برای برخی از الگوریتم‌های پرکاربرد و پذیرفته شده عمل کرد و خود اغلب در صنعت توسعه استفاده نمی‌شود.
با این حال، اگر مجموعه ورودی کوچک باشد، Selection Sort گزینه بهتری نسبت به Quicksort یا Merge Sort است. اما باز هم، Insertion Sort در این موارد مؤثرتر از Selection Sort است.
در این مقاله، ایده انتخاب مرتب‌سازی را مرور کرده‌ایم، آن را در جاوا اسکریپت پیاده‌سازی کردیم، پیچیدگی زمانی آن را بررسی کردیم و به طور خلاصه به برخی از انواع آن اشاره کردیم.
منتشر شده در 1403-01-20 21:41:09
