|
Oʻzbekiston respublikasi oliy va o‘rta maxsusta’lim vazirligi
|
| bet | 6/16 | | Sana | 15.11.2023 | | Hajmi | 29,81 Mb. | | #99092 |
Bog'liq Dilshoda Algoritm mustaqil Tanlov saralash sxemasi:
Selection sort qanday ishlaydi?
Misol sifatida quyidagi massivni ko'rib chiqamiz: arr[] = {64, 25, 12, 22, 11}
Birinchi o'tish:
Saralangan massivdagi birinchi o'rin uchun butun massiv 0 dan 4 gacha bo'lgan indeksdan ketma-ket o'tkaziladi. Hozirda 64 saqlanadigan birinchi pozitsiya , butun massivni aylanib o'tgandan so'ng, 11 eng past qiymat ekanligi ayon bo'ladi .
Shunday qilib, 64 ni 11 bilan almashtiring. Bir iteratsiyadan so'ng massivdagi eng kam qiymat bo'lgan 11 , tartiblangan ro'yxatning birinchi pozitsiyasida paydo bo'ladi.
Ikkinchi o'tish:
25 mavjud bo'lgan ikkinchi pozitsiya uchun massivning qolgan qismini yana ketma-ketlikda aylantiring.
Ketishdan so'ng, biz 12 massivdagi ikkinchi eng past qiymat ekanligini va u massivda ikkinchi o'rinda paydo bo'lishi kerakligini aniqladik , shuning uchun bu qiymatlarni almashtiring.
Uchinchi o'tish:
Endi, uchinchi o'rin uchun, 25 mavjud bo'lgan joyda, yana massivning qolgan qismini kesib o'ting va massivdagi uchinchi eng kam qiymatni toping.
Ketish paytida 22 uchinchi eng kam qiymat bo'lib chiqdi va u massivda uchinchi o'rinda paydo bo'lishi kerak, shuning uchun 22 ni uchinchi o'rindagi element bilan almashtiring.
To'rtinchi o'tish:
Xuddi shunday, to'rtinchi pozitsiya uchun massivning qolgan qismini kesib o'ting va massivdagi to'rtinchi eng kichik elementni toping.
25 4-eng past qiymat bo'lgani uchun u to'rtinchi o'rinni egallaydi.
Beshinchi o'tish:
Nihoyat, massivda mavjud bo'lgan eng katta qiymat avtomatik ravishda massivning oxirgi pozitsiyasiga joylashtiriladi
Olingan massiv tartiblangan massivdir.
Muammoni hal qilish uchun quyidagi amallarni bajaring:
Minimal qiymatni ( min_idx ) 0 manziliga ishga tushiring.
Massivdagi minimal elementni topish uchun massivni aylanib o'ting.
Ketish paytida min_idx dan kichikroq element topilsa, ikkala qiymatni almashtiring.
Keyin keyingi elementga ishora qilish uchun min_idx ni oshiring.
Massiv tartiblashtirilguncha takrorlang.
Quyida yuqoridagi yondashuvni amalga oshirish ko'rsatilgan:
// C# program for implementation
// of Selection Sort
using System;
class GFG
{
static void sort(int []arr)
{
int n = arr.Length;
// One by one move boundary of unsorted subarray
for (int i = 0; i < n - 1; i++)
{
// Find the minimum element in unsorted array
int min_idx = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// Swap the found minimum element with the first
// element
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
// Prints the array
static void printArray(int []arr)
{
int n = arr.Length;
for (int i=0; i
Console.Write(arr[i]+" ");
Console.WriteLine();
}
// Driver code
public static void Main()
{
int []arr = {64,25,12,22,11};
sort(arr);
Console.WriteLine("Sorted array");
printArray(arr);
}
}
Chiqishi
Saralangan massiv: 11 12 22 25 64
Saralashning murakkablik tahlili:
Vaqt murakkabligi: Selection sortning vaqt murakkabligi O(N 2 ) ga teng, chunki ikkita ichki oʻrnatilgan tsikl mavjud:
Massiv elementini birma-bir tanlash uchun bitta tsikl = O(N)
Ushbu elementni boshqa massiv elementi bilan solishtirish uchun yana bir tsikl = O (N)
Shuning uchun umumiy murakkablik = O(N) * O(N) = O(N*N) = O(N 2 )
Yordamchi bo'shliq: O (1) qo'shimcha xotira sifatida faqat massivdagi ikkita qiymatni almashtirishda vaqtinchalik o'zgaruvchilar uchun ishlatiladi. Selection sort hech qachon O(N) almashinuvidan ko'proq narsani qilmaydi va xotirani yozish qimmat operatsiya bo'lganda foydali bo'lishi mumkin.
Selection sort algoritmining afzalliklari:
Oddiy va tushunish oson.
Teng kalitlarga ega elementlarning nisbiy tartibini saqlaydi, bu uning barqarorligini bildiradi.
Kichik ma'lumotlar to'plamlari bilan yaxshi ishlaydi.
U har xil turdagi ma'lumotlarga moslashadi.
Tanlovni saralash joyida tartiblash algoritmidir, ya'ni ro'yxatni saralash uchun qo'shimcha xotira talab qilinmaydi.
U O(n^2) ning eng yaxshi va oʻrtacha vaqt murakkabligiga ega boʻlib, uni kichik maʼlumotlar toʻplamlari uchun samarali qiladi.
O'sish yoki kamayish tartibida saralash uchun o'zgartirish oson.
U apparatda osonlik bilan amalga oshirilishi mumkin, bu uni real vaqtda ilovalar uchun mos qiladi.
Bundan samaraliroq saralash algoritmlarida pastki dastur sifatida ham foydalanish mumkin.
Bu hech qanday maxsus xotira yoki yordamchi ma'lumotlar tuzilmalarini talab qilmaydi, bu uni engil yechimga aylantiradi.
Algoritm osongina parallel bo'lishi mumkin, bu ko'p yadroli protsessorlarda samarali saralash imkonini beradi.
U cheklangan xotira muhitlarida ishlatilishi mumkin, chunki u minimal qo'shimcha xotirani talab qiladi.
U bir nechta noyob kalitlar bilan ma'lumotlarni saralash uchun javob beradi, chunki u bunday stsenariylarda yaxshi ishlaydi.
|
| |
