Ma'lumotlar tuzilmasi: Saralash va qidiruv algoritmlari

Ushbu uslubiy qo'llanma kompyuter injiniringi va dasturiy injiniring bakalavr ta'lim yo'nalishlari 1-kurs talabalari uchun mo'ljallangan bo'lib, "Ma'lumotlar tuzilmasi" fanining "Saralash va qidiruv algoritmlari" bobini o'z ichiga oladi. Unda ma'lumotlar tuzilmasini shakllantirishning mantiqiy asoslari va dasturlash tillaridagi tadbiqi misollar yordamida tushuntirilgan. Qo'llanma o'rganilib chiqilgandan so'ng talabalar ma'lumotlarning tayanch va dinamik tuzilmalari ustida bajariladigan saralash va qidiruv amallarining usullarini amaliyotga tatbiq etish ko'nikmalariga ega bo'ladilar.

Asosiy mavzular

Saralash algoritmlari: asosiy tushunchalar: Bu bo'limda saralash (tartiblash) tushunchasi, uning maqsadlari va saralash algoritmlarining umumiy tasnifi (ichki va tashqi saralash) ko'rib chiqiladi. Massivda saralash usullari (qo'yish, tanlash, almashtirish) va faylda saralashning o'ziga xos jihatlari tushuntiriladi.
To'g'ridan-to'g'ri qo'yish orqali saralash: Ushbu usulning asosiy g'oyasi, ishlash mexanizmi, C++ tilidagi misoli va algoritm tahlili keltirilgan. Ya'ni, massiv elementlarini qulay joyga joylashtirish orqali saralash jarayoni bayon etilgan.
To'g'ridan-to'g'ri tanlash usuli: Bu bo'limda to'g'ridan-to'g'ri tanlash usulining ishlash prinsipi, qadamlari, C++ tilidagi dasturi va algoritm tahlili berilgan. Ushbu usulda eng kichik element topilib, massiv boshidagi element bilan almashtiriladi.
To'g'ridan-to'g'ri almashtirish usuli ("Pufakcha" usuli): Pufakcha usulining mohiyati, qadamlari, C++ tilidagi kodi va algoritm tahlili yoritilgan. Bu usulda yonma-yon elementlar saralanadi va almashtiriladi.
Sheyker saralash algoritmi: Sheyker saralash pufaksimon saralashning mukammallashgan usuli hisoblanadi. Bu bo'limda usulning ishlash prinsipi, C++ tilidagi dasturi va uning qadamlari misollar bilan ko'rsatilgan.
Shell saralash algoritmi: Shell saralash algoritmi to'g'ridan-to'g'ri qo'yish usulining mukammallashtirilgan variantidir. Unda elementlar dastlab ma'lum qadamlar bilan guruhlanib saralashadi, keyin qadamlar kamayib boradi. Algoritmning C tilidagi kodi va ishlash prinsipi tushuntirilgan.
Daraxt yordamida saralash: Bu usul binar qidiruv daraxti asosida ishlaydi. Ma'lumotlar daraxt tuzilishiga joylashtiriladi va keyin infiks ko'rinishida aylanib chiqish orqali saralanadi. C++ tilidagi dasturi bilan misollar keltirilgan.
Piramidali saralash: D. Villyams tomonidan yaratilgan usul bo'lib, daraxt yordamida saralashning yaxshilangan variantidir. Piramidali saralash ikki bosqichdan iborat: piramidani qurish va piramidada saralash. Ushbu usulning C++ tilidagi dasturi va algoritm tahlili berilgan.
Tez saralash: Bu mukammallashgan saralash usuli bo'lib, katta masofadagi elementlarni almashtirishga asoslanadi. Ruxsat beruvchi element tanlanadi va massiv ikki qismga bo'linadi. Rekursiv usulda ishlaydi. Algoritmning C tilidagi dasturi va ishlash prinsipi tushuntirilgan.
Birlashtirishli saralash: Bu usul fayllarni saralashda samarali bo'lib, ma'lumotlarga faqat ketma-ket murojaat qilinadigan tuzilmalar bilan ishlashga qulay. Ketma-ketliklar bo'linadi va keyin birlashtiriladi. Ikki yo'lli va pastga yo'naltirilgan birlashtirishli saralash usullari C tilida keltirilgan.
Qidiruv algoritmlari: Qidiruv – bu kompyuter xotirasidagi ma'lumotlarni izlash jarayoni. Qidiruv algoritmlari saralangan va saralanmagan ma'lumotlar uchun qo'llaniladigan turlarga bo'linadi.
Ketma-ket qidiruv: Bu usulda massivning barcha elementlari ketma-ket qarab chiqiladi. Misol va C tilidagi dasturi keltirilgan.
Transpozitsiya usuli: Bu usulda har bir elementga murojaat qilinganda u o'zidan oldingi element bilan joy almashadi. Natijada ko'p ishlatiladigan element jadval boshiga o'tadi. C tilidagi dasturi keltirilgan.
Boshiga ko'chirish usuli: Bu usulda elementga murojaat qilinganda, u jadvalning boshiga ko'chiriladi. Natijada tez-tez ishlatiladigan elementlar jadval boshida to'planadi. C tilidagi dasturi keltirilgan.
Indeksli ketma-ket qidiruv: Bu usulda asosiy jadvalga qo'shimcha ravishda indeks jadvali qo'llaniladi, bu qidirish vaqtini qisqartiradi. C tilidagi dasturi va tahlili berilgan.
Binar qidiruv: Binar qidiruv tartiblangan massivda amalga oshiriladi. U elementni massivning o'rta elementi bilan solishtirish orqali ishlaydi. Qidiruvni qadamlar soni kamaytirish uchun o'rtasidan bo'lish usuli qo'llaniladi. C++ tilidagi dasturi keltirilgan.