Texnologiyalari universiteti Farg’ona filiali 730-20 guruh talabasi Mamajonov Raximberdining Ma'lumotlar tuzilmasi va

3.3. Tanlash orqali saralash algoritmi

Mazkur usul quyidagi tamoyillarga asoslangan:

1. 
   Eng kichik kalitga ega element tanlanadi.
   

2. 
   Ushbu element a0 birinchi element bilan o’rin almashinadi.
   

3. 
   Keyin mazkur jarayon qolgan n-1, n-2 elementlar bilan takrorlanib, to bitta eng “katta” element qolguncha davom ettiriladi.
   

for(int i=0;i<="" p="">

for(int j=i+1;j if (a[i] > a[j]){

int k = a[j]; a[j]= a[i];
a[i]= k;

12. 
    Hesh so’zi ingliz tilidagi hash so’zidan olingan bo’lib, chalkash ( putanisa) yoki aralashma (meshanina) ma’nosini anglatadi
    

• 
  Hesh so’zi ingliz tilidagi hash so’zidan olingan bo’lib, chalkash ( putanisa) yoki aralashma (meshanina) ma’nosini anglatadi
  
• 
  Ta’rif . Hesh-funksiya – bu kiruvchi ma’lumotlarning ixtiyoriy uzunlikdagi massivini belgilangan aniq uzunlikdagi bitlar qatoriga biror bir algoritm orqali akslantiruvchi bir tomonlama funksiyadir (funksiya svyortki).
  

Bunday amal -heshlash(+tirish) deyiladi.
Amalning natijasi (bitlar qatori)ga hesh yoki hesh kod yoki hesh-summa yoki ma’lumotlar yig’mi(cvodkasi ) deyiladi.


Bunday funksiyalar kriptografiya va axborot xavfsizlik masalalarida keng qo’llaniladi.


Hesh funksiya hossalari :

1. 
   Teskari funksiyaning mavjud emasligi;
   

2. 
   Kollizia holatining yo’qligi ;
   

3. 
   DeterminanlanganIik
   

4. 
   Natijaning tasodifligi.
   

Joylashtirish usuli (xeshlashtirish) ma’lumotlar tuzilmasida element joylashgan o‘rinni tez aniqlashga yo‘naltirilgan usuldir. Joylashtirish usulida ma’lumotlar oddiy massiv sifatida ifodalangan bo‘ladi.

• 
  Joylashtirish usuli (xeshlashtirish) ma’lumotlar tuzilmasida element joylashgan o‘rinni tez aniqlashga yo‘naltirilgan usuldir. Joylashtirish usulida ma’lumotlar oddiy massiv sifatida ifodalangan bo‘ladi.
  
• 
  Elementni jadvalga qo‘shishdan oldin uning adresi xesh-funksiya orqali aniqlanadi: A = h(K), bu erda K – kalit, A – jadvaldagi element adresi bo‘lib, 0  A  N-1, shart o‘rinli bo‘ladi.
  

F xesh-funksiya deb R kiruvchi elementlar to‘plamini manfiy bo‘lmagan butun sonlar to‘plami Z ga akslantirishga aytiladi:

• 
  F xesh-funksiya deb R kiruvchi elementlar to‘plamini manfiy bo‘lmagan butun sonlar to‘plami Z ga akslantirishga aytiladi:
  

F(r)=n, rϵR, nϵZ.

• 
  Xesh-adreslash bu xesh-funksiya qiymatlar sohasini qandaydir bir ma’lumotlar massivining yacheykasi, adresi sifatida foydalanishdan iborat.
  
• 
  U holda ma’lumotlar massivi o‘lchami foydalanilayotgan xesh- funksiyaning qiymatlar sohasiga mos kelishi kerak.
  

Turli A1, A2, A3 identifikatorlar uchun mos ravishda n1, n2, n3 xesh-funksiya qiymatlari to‘g‘ri kelsin. n1, n2, n3 adreslarga mos yacheykalarda A1, A2, A3 identifikatorlar haqida ma’lumot joylanadi. A3 identifikatorni qidirishda n3 adres qiymati hisoblanadi va tegishli jadval yacheykasidan ma’lumotlar tanlanadi.

• 
  Turli A1, A2, A3 identifikatorlar uchun mos ravishda n1, n2, n3 xesh- funksiya qiymatlari to‘g‘ri kelsin. n1, n2, n3 adreslarga mos yacheykalarda A1, A2, A3 identifikatorlar haqida ma’lumot joylanadi. A3 identifikatorni qidirishda n3 adres qiymati hisoblanadi va tegishli jadval yacheykasidan ma’lumotlar tanlanadi.
  

Bu metod juda effektiv, elementlarni jadvalga joylash vaqti ham, qidiruv vaqti ham faqat xesh-funksiyani hisoblashga ketadi.

• 
  Bu metod juda effektiv, elementlarni jadvalga joylash vaqti ham, qidiruv vaqti ham faqat xesh-funksiyani hisoblashga ketadi.
  
• 
  Bu usulning 2 ta yaqqol kamchiligi bor:
  
• 
  1) identifikatorlar jadvalining xotira hajmidan unumsiz foydalanilishi. Massiv o‘lchami xesh-funksiya qiymatlar sohasiga mos kelishi kerak, ayni vaqtda real holatda jadvalda saqlanayotgan identifikatorlar ancha kam bo‘lishi mumkin.
  
• 
  2) mos keluvchi xesh-funksiyani tanlay bilish.
  

Xesh-funksiyadan natija olish - “xeshlash” simvollar zanjiri ustida oddiy arifmetik va mantiqiy amallarni bajarish hisobiga erishiladi.

• 
  Xesh-funksiyadan natija olish - “xeshlash” simvollar zanjiri ustida oddiy arifmetik va mantiqiy amallarni bajarish hisobiga erishiladi.
  
• 
  Xesh-adreslashda identifikatorlar jadvalining bir yacheykasiga 2 ta turli xil bo‘lgan identifikatorlar joylashishi mumkin emas. Bu vaziyat, ya’ni 2 yoki undan ortiq identifikatorlar xesh funksiyaning bir xil qiymatiga ega bo‘lish xodisasi kolliziya deb nomlanadi.
  
• 
  Demak, kolliziyaning yuzaga kelishi 2 ta har xil identifikator A1 va A2larning xesh-funksiya qiymatlari n1 va n2 bir xil (n1=n2) bo‘lishi hisoblanadi.
  

Kolliziya xolati


Kolliziya ro‘y berishini butunlay oldini oladigan, yaxshi xesh-funksiyani qurish mumkinmi?

• 
  Kolliziya ro‘y berishini butunlay oldini oladigan, yaxshi xesh-funksiyani qurish mumkinmi?
  
• 
  Aniqki, butunlay kolliziyaga uchramasligi uchun xesh-funksiyaning har bir natijaviy qiymati unikal bo‘lishi kerak.
  
• 
  Kolliziya muammosini echish uchun turli usullarni qo‘llash mumkin. Ulardan biri “rexeshlash” metodi hisoblanadi.
  

Bu metodga ko‘ra, A element uchun xesh-funksiya orqali hisoblangan h(A) adresi band bo‘lgan yacheykani ko‘rsatsa, unda n1=h1(A) funksiya qiymatini hisoblash zarur va n1 adresga tegishli yacheykani bandligini tekshirish kerak. Agar n1 ham band bo‘lsa, unda h2(A) qiymat hisoblanadi, shu tariqa bo‘sh yacheyka to’lguncha yoki hi(A) navbatdagi qiymat h(A) bilan mos kelgunga qadar davom etadi. Oxirgi holatda identifikatorlar jadvali to‘lgan va bo‘sh joy boshqa yo‘q, degan xatolik to‘g‘risida ma’lumot beradi.

• 
  Bu metodga ko‘ra, A element uchun xesh-funksiya orqali hisoblangan h(A) adresi band bo‘lgan yacheykani ko‘rsatsa, unda n1=h1(A) funksiya qiymatini hisoblash zarur va n1 adresga tegishli yacheykani bandligini tekshirish kerak. Agar n1 ham band bo‘lsa, unda h2(A) qiymat hisoblanadi,
  

shu tariqa bo‘sh yacheyka to’lguncha yoki hi(A) navbatdagi qiymat h(A) bilan mos kelgunga qadar davom etadi. Oxirgi holatda identifikatorlar jadvali to‘lgan va bo‘sh joy boshqa yo‘q, degan xatolik to‘g‘risida ma’lumot beradi.


hi(A) funksiyani hisoblashning eng oddiy metodi, uni hi(A)=(h(A)+pi)modNm asosida qurishdir, bu erda pi qandaydir bir hisoblangan butun son, Nm – identifikatorlar jadvalidagi elementlarning maksimal soni. O‘z o‘rnida eng oddiy usul pi ni o‘rniga i ni qo‘yish bo‘ladi. Unda quyidagi formulani olamiz hi(A)=(h(A)+i)modNm. Bu holda xesh-funksiyaning bir xil qiymatlariga mos kelgan identifikatorlarni joylash uchun bo‘sh yacheykani qidirish mantiqan xesh- funksiya h(A) ko‘rsatgan joydan boshlanadi.

• 
  hi(A) funksiyani hisoblashning eng oddiy metodi, uni hi(A)=(h(A)+pi)modNm asosida qurishdir, bu erda pi qandaydir bir hisoblangan butun son, Nm –identifikatorlar jadvalidagi elementlarning maksimal soni. O‘z o‘rnida eng oddiy usul pi ni o‘rniga i ni qo‘yish bo‘ladi. Unda quyidagi formulani olamiz hi(A)=(h(A)+i)modNm. Bu holda xesh- funksiyaning bir xil qiymatlariga mos kelgan identifikatorlarni joylash uchun bo‘sh yacheykani qidirish mantiqan xesh-funksiya h(A) ko‘rsatgan joydan boshlanadi.
  

12. 
    Xesh-jadvallar quyidagi xossalarga mos kelishi shart:
    

• 
  Xesh-jadvalida amallarni bajarishdan oldin, kalitning xesh-funksiyasi hisoblanadi, natijada kirish massivdagi indeks hosil bo’ladi.
  

• 
  Xesh jadvalini to'ldirish koeffitsienti - bu saqlanadigan massiv elementlari soni, xesh funksiyasining mumkin bo'lgan qiymatlari soniga bo'linadi. Bu operatsiyalarning o'rtacha bajarilish vaqti bog'liq bo'lgan muhim parametr hisoblanadi.
  
• 
  Odatda yaxshi xesh-funksiya quyidagi shartlarni qonatlantiradigan funksiya ekanligi qabul qilinadi. Funktsiya: hisoblash nuqtai nazaridan sodda bo'lishi kerak (bu kompyuterning xususiyatlariga bog'liq), xesh jadvalga kalitlar iloji boricha teng taqsimlanishi (ma'lumotlar qiymatiga qarab), kolliziyalar sonini kamaytirishga harakat qilishi kerak. Funksiya asosiy kalitlar qiymatlari orasidagi bog'liqlikni manzil qiymatlari o'rtasidagi munosabat bilan taqqoslamasligi kerak.