CS50 - Week 3

Algoritm - bu muammoni hal qilish uchun aniq ketma-ketlikda berilgan ko'rsatmalar to'plami. Algoritmlar bir-biridan tezligi va qancha xotira egallashi bilan farq qiladi. Dasturlash jarayonida aksar algoritmlar ma'lumotlarni qidirish (searching) va tartiblashga (sorting) borib taqaladi. Keling, ma'lumotlarni qidirish algoritmlari bilan tanishamiz:

Chiziqli qidiruv (Linear search)

Bizga quyidagi massiv berilgan bo'lsin:

[20, 500, 10, 5, 100, 1, 50]

Massivni tasavvur qilishda uni quyidagi kabi yonma-yon turgan yettita qizil shkaf sifatida ko‘rish mumkin:

Ushbu massivdan 50 sonini topishimiz kerak. Kompyuter 50 sonini topish uchun har bir shkafni tekshirishi kerak. Ushbu jarayonni, ya’ni massiv ichida ma’lum bir raqamni, belgini yoki boshqa elementni izlashni "qidiruv" deb ataymiz.

Biz massivimizni algoritmga topshirib, algoritm orqali shkaflarni ochib, 50 raqami bor-yo‘qligini aniqlashni so‘rashimiz mumkin. Natijada, algoritm bizga “ha” yoki “yo‘q” (true yoki false) deb javob beradi.

Quyidagi kabi ko‘rsatmalar yordamida algoritmni tuzishimiz mumkin:

Chapdan o‘ngga har bir eshikni tekshirish:

    Agar 50 soni bor bo‘lsa:

        Ha deb qaytaramiz (return true)

Yo‘q deb qaytaramiz (return false)

Yuqoridagi ko‘rsatmalar inson o‘qishi uchun mo‘ljallangan pseudokod bo‘lib, kompyuterga topshiriladigan buyruqlarning oddiyroq ko‘rinishidir.

Chiziqli qidiruv algoritmini quyidagi kod yordamida C tilida amalga oshirishimiz mumkin:

#include <cs50.h>

#include <stdio.h>



int main(void)

{

    // Butun sonlardan iborat massiv berilgan

    int numbers[] = {20, 500, 10, 5, 100, 1, 50};



    // Kiritilgan sonni massivdan qidiramiz

    int n = get_int("Number: ");

    for (int i = 0; i < 7; i++)

    {

        if (numbers[i] == n)

        {

            printf("Topildi\n");

            return 0;

        }

    }

    printf("Topilmadi\n");

    return 1;

}

Bu yerda for sikli yordamida chiziqli qidiruv amalga oshirilmoqda.

return 0 - dastur muvaffaqiyatli tugaganini bildiradi va dasturdan chiqiladi.

return 1 - dasturda xatolik yuz berganligini bildiradi.

Binar qidiruv (Binary search)

Binar qidiruv – bu 50 raqamini izlashda qo‘llaniladigan yana bir algoritm.

Agar massivdagi qiymatlar o'sish tartibida saralangan bo‘lsa, binar qidiruvning pseudokodini quyidagicha keltirishimiz mumkin:

Agar tekshiriladigan element qolmagan bo‘lsa:

    Yo‘q deb qaytaramiz (return false)

Agar massivning[o‘rta elementi] 50 soniga teng bo‘lsa:

    Ha deb qaytaramiz (return true)

Agar massivning[o‘rta elementi] > 50:

    Massivning chap yarmidan qidiramiz

Agar massivning[o‘rta elementi] < 50:

    Massivning o‘ng yarmidan qidiramiz

Big O notatsiyasi

Algoritmning ishlashiga ketadigan vaqtini tahlil qilish uchun Big O notatsiyasidan foydalaniladi. Quyidagi grafikni ko‘rib chiqamiz:

"Kiritiladigan ma'lumot hajmi" – x o‘qi; "Yechim uchun vaqt" – y o‘qi;

Algoritmning samaradorligi uning egri chizig‘ining shakliga qarab aniqlanadi:

O(n²) - eng yomon ishlash vaqti hisoblanadi.

O(log n) - eng tezkor ishlash vaqtidir.

Chiziqli qidiruv algoritmi ishlalishiga ketadigan vaqt - O(n), chunki eng yomon holatda n qadam talab qilinishi mumkin.

Binar qidiruv algoritmi ishlashiga ketadigan vaqt esa O(log n), chunki eng yomon holatda qadamlar soni tobora kamayib boradi.

Dasturchilarni qiziqtiradigan ikkita holat mavjud:

• Eng yomon holat yoki yuqori chegarasi (upper bound).


• Eng yaxshi holat yoki quyi chegarasi (lower bound).

Ω belgisi algoritmning eng yaxshi holatini (quyi chegarani) belgilash uchun ishlatiladi, masalan, Ω(n).

Θ belgisi esa yuqori va quyi chegaralar bir xil bo‘lgan holatni belgilaydi, ya’ni eng yaxshi va eng yomon ishlash vaqtining bir xil bo‘lishi.

Saralash algoritmlari (Sorting)

Saralash – bu tartiblanmagan qiymatlar ro‘yxatini tartiblangan holda o‘zgartirish jarayonidir.

Massiv tartiblangan holatda bo‘lsa, undan ma'lum bir elementni qidirish kompyuter uchun ancha yengil bo‘ladi. Masalan, binar qidiruv (binary search) tartiblangan massivda ishlaydi, ammo tartiblanmagan massivda ishlamaydi.

Saralash algoritmlarining ko‘plab turlari mavjud. Ulardan biri tanlash usuli (selection sort) ni ko'rib chiqamiz. Bizga quyidagicha massiv berilgan bo'lsin:

Tanlash usuli algoritmining pseudokodi quyidagicha bo'ladi:

i = 0 dan n-1 gacha:

    numbers[i] va numbers[n-1] orasidagi eng kichik sonni topamiz

    Eng kichik sonni numbers[i] bilan almashtiramiz

Bosqichlar tahlili:

• Birinchi marta massiv elementlari bo‘ylab yurish n - 1 qadam talab qiladi.


• Ikkinchi marta esa n - 2 qadam talab qilinadi.


• Ushbu mantiq davom ettirilsa, kerakli qadamlar quyidagicha ifodalanishi mumkin:
  

(n - 1) + (n - 2) + (n - 3) + ... + 1

Bu formulani soddalashtirish orqali quyidagini olamiz: n(n-1)/2 yoki O(n²).

Demak, tanlash usuli algoritmi eng yomon holatda O(n²) tartibida saralar ekan. Hatto barcha qiymatlar tartiblangan bo‘lsa ham, qadamlar soni o‘zgarmaydi, ya’ni eng yaxshi holat ham O(n²) tartibida ishlaydi.

Pufakchali saralash algoritmi (Bubble sort)

Pufakchali saralash — yana bir saralash algoritmi bo'lib, bunda elementlarni qayta-qayta joylarini almashtirib, kattaroq qiymatlarni oxiriga “ko‘taramiz”.

Pufakchali saralash algoritmining pseudokodi quyidagicha bo'ladi:

n–1 marta takrorlaymiz:

    0 dan n–2 gacha har bir i uchun:

        Agar numbers[i] va numbers[i+1] noto‘g‘ri tartibda bo‘lsa:

            Ularni joyini almashtiramiz

    Agar almashtirishlar qolmagan bo‘lsa:

        Dasturdan chiqamiz

Massivni tartiblash davomida shuni bilamizki, uning ko‘proq qismi tartiblanib boradi, shuning uchun faqat hali tartiblanmagan juftliklarni tekshirishning o'zi kifoya qiladi.

Shuning uchun pufakchali saralash algoritmi eng yomon holatda massiv tartiblanmagan bo'lsa O(n²), eng yaxshi holatda massiv allaqachon tartiblangan bo‘lsa O(n) tartibida ishlaydi.

Saralash algoritmlari qanday holatda qanday ishlashini ushbu sahifada vizual ko'rishimiz mumkin.

Ushbu maqolada CS50x 2024 manbasidan foydalanilgan.