Qidiruv, ma'lumotlarni to'plamdan topish va mos keluvchi ma'lumotlarga murojaat qilish jarayonida kritik muhimiyatga ega bo'lgan amaldir. Bu, ma'lumotlar bazalarini effektiv va samarador ishlatishning

Qidiruv, ma'lumotlarni to'plamdan topish va mos keluvchi ma'lumotlarga murojaat qilish jarayonida kritik muhimiyatga ega bo'lgan amaldir. Bu, ma'lumotlar bazalarini effektiv va samarador ishlatishning asosiy qismidir.

Ma'lumotlarni saralash algoritmlari, bir to'plamda (massivda) o'rganilgan ma'lumotlar ketma-ketligini tartiblab berish uchun ishlatiladigan algoritmlardir. Quyidagi saralash algoritmlari ko'plikda ishlatiladi:

• Tanlangan saralash (Selection sort): Bu algoritm har bir tartiblash qadamida eng kichik yoki eng katta elementni topib, o'rnini o'zgartiradi. Bunda unsorted qismning eng kichik (yoki eng katta) elementi sorted qismning ohangida joylashadi. Bu jarayon o'zgarmas qilib davom etadi, to'plam to'liq tartiblangan bo'lishi bilan tugaydi. Selection sort O(n^2) muammo vaqti bilan ishlaydi.
• Qo'shish bilan saralash (Insertion sort): Bu algoritm to'plamni ixtiyoriy tartibda bo'lib, unsorted qismning bir elementini o'lib, sorted qismning mos joyiga joylashtiradi. Bunda sorted qism har bir qadamda boshidan o'sib-chiqadi va yangi elementni joylashtiradi. Insertion sort ham O(n^2) vaqtda ishlaydi, lekin kichik tartiblash uchun qo'shimcha to'plam saralash jarayonida samarali bo'lishi mumkin.

Ayirish bilan saralash (Merge sort): Bu algoritm rekursiv tarzda ishlaydi. To'plamni ikki yarimka bo'lib bo'linadi, har bir yarimka rekursiv ravishda tartiblanadi va keyinchalik birlashtiriladi. Birlashtirish jarayonida ikki yarimka mos elementlari taqqoslanadi va saralandi. Merge sort O(n log n) vaqtda ishlaydi, shuning uchun katta to'plamlar uchun samarali bo'ladi.

• Ayirish bilan saralash (Merge sort): Bu algoritm rekursiv tarzda ishlaydi. To'plamni ikki yarimka bo'lib bo'linadi, har bir yarimka rekursiv ravishda tartiblanadi va keyinchalik birlashtiriladi. Birlashtirish jarayonida ikki yarimka mos elementlari taqqoslanadi va saralandi. Merge sort O(n log n) vaqtda ishlaydi, shuning uchun katta to'plamlar uchun samarali bo'ladi.
• Baholash bilan saralash (Quick sort): Bu algoritm ham rekursiv tarzda ishlaydi. To'plamdan bir element tanlanadi (pivot element). Keyinchalik pivot element bo'yicha to'plam qismlarga bo'linadi: pivotdan kichik elementlar va pivotdan katta elementlar. Har bir qisim rekursiv ravishda tartiblanadi. Quick sort ham O(n log n) vaqtda ishlaydi, ammo eng yaxshi vaqtda O(n^2) bo'lishi mumkin.
• Tartiblash vaqti asosida saralash (Heap sort): Bu algoritm ma'lumotlarni tartiblash bo'yicha max-heap (yoki min-heap) nomlanadigan strukturaga o'rganadi. Keyinchalik, max (yoki min) elementni topib olib, unsorted qismning oxiriga joylashtiradi. Saralishni davom ettirish uchun heap ni qayta tiklash va sorted qismni kengaytirish jarayonlari amalga oshiriladi. Heap sort O(n log n) vaqtda ishlaydi

• Tartiblash tizim bilan saralash (Counting sort): Bu algoritm katta ma'lumotlar to'plamida o'zaro bog'liqlik bo'lmagan, chegaralangan katta manbalardan iborat bo'lgan holatlarda foydalaniladi. Counting sort ma'lumotlarni sanash jarayoniga asoslangan va ma'lumotlarni tartiblab beradi. Shu sababli, qo'shimcha xotiraga ehtiyoj qilmaydi. Counting sort O(n + k) vaqtda ishlaydi, bu yerda n to'plam elementlar soni, k esa sanash uchun kerak bo'lgan manbalar sonini ifodalaydi.


Download 91,26 Kb.