Bajardi: boynazarov a qabul qildi: begulov o

Sarlash algoritmlarining samaradorligi uchun masofaviy vaqtlar, to'plamning o'lchami, tartiblashningturlari va boshqa omil-lar hisobga olinganida foydalanuvchiga bog'liq bo'ladi. Har bir saralash algoritmi o'ziga xos muammolarni hal qilish uchun qulayliklarga ega bo'lishi mumkin

Foydalanuvchi ma'lumotlarining turi va to'plamning o'lchami, saralash operatsiyalarining tezligi va xotirasini hisobga olgan holda, mos keluvchi saralash algoritmini tanlash kerak.

Saralashning qat'iy usullari, qidiruv algoritmlari bilan birga ishlatiladigan oddiy va to'g'ridan-to'g'ri muhim algoritmlardir. Ularning samaradorligi vaqti va resurslarni miqdori bilan bog'liq bo'ladi, ammo ulardan foydalanish odatda kichik ma'lumotlar to'plamlariga (massivlarga) mos keladi. Quyidagi qat'iy saralash usullari katta ma'lumotlar uchun samaradorliga ega bo'lmaydigan usullar hisoblanadi:

• Bubble sort: Bu usulda o'zgaruvchilar ketma-ketligi yoki massivning elementlari qarshiligida taqqoslanadi va ularni tartiblangan tartibda joylashtirish imkoniyatini beradi. Bubble sort O(n^2) vaqtda ishlaydi, shuning uchun katta ma'lumotlar uchun samarali emas.
• Shartlash usuli (Shaker sort): Bu usulda elementlar ketma-ketligi qaytib ketadi va tartiblangan tartibda joylashtiriladi. Shartlash usuli ham O(n^2) vaqtda ishlaydi, shuning uchun katta ma'lumotlar uchun samarali emas.
• Tartiblash bilan saralash (Insertion sort): Bu usul yuqoridagi qat'iy usullardan biri hisoblanadi, lekin unsorted qismning bir elementini sorted qismga joylashtirish jarayonini o'zgartirganiga qarab yaxshilanadi. Yana ham O(n^2) vaqtda ishlaydi.

Samarali saralash usullari esa katta ma'lumotlar uchun foydalanishga qulay bo'ladi, chunki ularning vaqti O(n log n) yoki undan kamroq bo'ladi. Quyidagi samarali saralash usullari o'rniga keltiriladi:

• Ayirish bilan saralash (Merge sort): Bu usul rekursiv tarzda ishlaydi va O(n log n) vaqtda ishlaydi. Katta ma'lumotlar uchun samarali bo'lib, qisqa tartiblashlar uchun ham yaxshilangan usul hisoblanadi. Shuningdek, Merge sort stabil hisoblanadi, ya'ni bir hil elementlar teng bo'lganda o'zgarishsiz qoladi.
• Baholash bilan saralash (Quick sort): Bu usul ham rekursiv tarzda ishlaydi va O(n log n) vaqtda ishlaydi. Sifatli va samarali hisoblanadi, ammo eng yomon holatda O(n^2) vaqtda ham ishlayishi mumkin. Quick sort asosan random pivot elementlarni tanlash bilan yaxshilanadi.
• Tartiblash tizim bilan saralash (Heap sort): Bu usul O(n log n) vaqtda ishlaydi. Tizim strukturasida ishlatiladigan max-heap (yoki min-heap) nomlanadigan strukturaga asoslangan. Katta ma'lumotlar uchun samarali bo'lib, ammo implementatsiya ko'p joy talab qilishi mumkin.

• Tartiblash tizimi bilan saralash (Radix sort): Bu usul katta sonlar to'plamida ishlatiladi. Sonlarni butun sonlar tizimida tartiblab chiqish imkonini beradi. Radix sort O(nk) vaqtda ishlaydi, bu yerda n to'plam elementlar soni va k esa sonlar uchun kerak bo'lgan tartiblashlar soni bo'ladi.


Download 91,26 Kb.