Farg‘ona davlat universiteti

Merge sort algoritmi qadamlari

1. 
   Merge Sort funksiyasiga array va uning boshlang’ich (left) va oxirgi nuqtalari (right) beriladi.
   
2. 
   Arraynining o’rtasi hisoblanadi: mid = (left + right)/2. Bu narsa uni teng ikkiga bo’lish uchun kerak bo’ladi.
   
3. 
   Merge sortni rekursiv holda birinchi va ikkinchi qismlar uchun chaqiriladi.
   
4. 
   2- va 3-qismlarda hosil bo’lgan arraylar birlashtirib chiqiladi. (Array mavzusidagi ikkita arrayni birlashtirish masalasini ko’rib chiqing)
   

Algoritm ishlash tezligi O(nlogn) bo’lib tezligi O(n²) bo’lgan oddiy Bubble, Insertion, Selection Sortlardan ancha tez ishlaydi. O’zi umuman olganda, taqqoslash asosida ishlaydigan algortmlarning eng tez ishlash holati O(nlogn) bo’lishi isbotlangan.
Merge sort turg’un saralash hisoblanadi, ya’ni saralamagan arrayda bir nechta bir xil elementlar kelgan bo’lsa, ularning tartibi saralangan massivda ham o’zgarib ketib qolmaydi.
Algoritm ishlashi uchun xotiradan qo’shimcha O(n) joy talab qiladi.

Chiziqli qidirishalgoritmi

Chiziqli qidirish algoritmi juda oddiy algoritm bo'lib, u massivdagi har bir elementni qidirilayotgan element bilan birma-bir solishtirib chiqadi. Algoritm murakkabligi O(n) bo'lib, bu real hayotda juda ham sekin bo'lishi mumkin.Tasavvur qilaylik Facebookning 1 mlrd foydalanuvchisi bor va foydalanuvchi o'z profiliga kirmoqchi. Bunda Facebook foydalanuvchi loginini chiziqli qidirishdan foydalanib tekshiradigan bo'lsa va bunda kompyuter sekundiga 10⁶ ta loginni tekshirgan taqdirda ham, o'sha foydalanuvchi profiliga kirishi uchun 1000 soniya (16.6 daqiqa) kutishi kerak bo'lardi. Shu sababli ham bunday holatlar uchun bizga samaraliroq algoritmlar kerak bo'ladi.

Chiziqli qidirish ( Massiv A, Qiymat x)


Qadam 1: Set i to 1
Step 2: if i > n then go to Qadam 7
Qadam 3: if A[i] = x then go to step 6
Qadam 4: Set i to i + 1
Qadam 5: Go to Step 2
Qadam 6: Print Element x Found at index i and go to step 8
Qadam 7: Print element not found
Qadam 8: Chiqish