Izlew hám xeshlaw algoritmler. Izlew algoritmler: Sızıqlı algoritm, ta’rtiplengen nawbetler, binar izlew. Xesh tablica hám xesh funksiyalar. Xesh funksiyalarg’a misal. Reje

5. Izlewdi quramalastırıw usılları

Izlew kestesin qayta tártiplewdi eń kóp istetiletúǵin eki usıli bar.Olardı bir baylamlı dizimler mısalında kórip shiǵamiz.

5.1 Tabılǵan elementti dizim basına qoyiw arqalı kesteni qayta tártiplew
Bul usıldıń mazmuni sodan ibarat, berilgen giltke teń gitli element dizimde birinshi element dep ózlestiriledi, qalǵanlari jılıstırıladı.

Keltirilgen algaritm dizim ushın hám massiv ushın da orınlı.Bıraq bul algaritm massiv ushın usinis etilmeydi,sebebi elementlerdi ornalastırıwǵa kórsetkishlerdi ornalastırıwdan kóre kóp waqıt talap qıladı.

Dizimdi qayta tártiplew algaritmi:


5.2 Transpoziciya usulı
Bul usılda tabılǵan element dizimde aldindaǵı bir element penen orın almastiriladı.Egerde bul elementke kóp múrajjat qılınsa, bir elementten aldiǵa qaray jılıstırıladı nátiyjede dizim basında boladı.

Sizilma. Qońsı elementlerdiń ornın almastiriw
r – jumısshi kórsetkish
q – járdemshi kórsetkish, r den bir adım izde boladı
s - járdemshi kórsetkish, q dan eki adım izde boladı
Transpozisiya usuli algoritmi:

Bul usıl dizimde emes, bálkim massivde de qolaylı (sebebi tek ǵana eki jaqın turǵan element orın almastiriladı).

6. Quramalı izlew teregi
Eger ajıratıp alınǵan elementler qandayda bir όzgermes kόplikti payda etse, kelesi izlewler nátiyjelirek bolıwı ushın olardı binar terek kόrinisinde ańlatıw maqsetke muwapıq bolıwı múmkin.
Tόmendegi keltirilgen tereklerde binary izlew kόrip shıǵayıq ( a) hám b)sızılma).
Eki terek de úshewden elementke iye - k1, k2, k3 bolıp bul jerde k1. k3 elementti izlew a) sızılmada eki salıstırıwdı talap etse, b) sızılmada bolsa birew.
Qandayda bir jazıwdı ajıratıp alıw ushın zárúr bolǵan giltlerdi salıstırıwlar sanı binar izlew teregindegi usı jazıw basqısına birdi qosqanǵa teń.
Meyli:
izlew argumenti key = k1 bolıwı itimallıǵı - p1,
izlew argumenti key = k2 bolıwı itimallıǵı – p3,
izlew argumenti key = k3 bolıwı itimallıǵı – p3,
key < k1 bolıwı itimallıǵı – q0,
k2 > key > k1 bolıwı itimallıǵı – q1,
k3 > key > k2 bolıwı itimallıǵı – q2,
key > k3 bolıwı itimallıǵı – q3,
C1 - a) sızılmadaǵı salıstırıwlar sanı,
C2 - b) sızılmadaǵı salıstırıwlar sanı.
sızılma a) sızılma b)

Ol jaǵdayda r1+×r2+×r3+×q0+×q1+×q2+×q3 = 1

Qandayda bir izlewda kútilip atırǵan salıstırıwlar sanı tόmendegishe boladı.
C1 = 2×r1+1×r2+2×r3+2×q0+2×q1+2×q2+2×q3
C2 = 2×r1+3×r2+1×r3+2×q0+3×q1+3×q2+1×q3
Qandayda bir berilgen giltler hám itimallıqlar kόpliginde kútilip atırǵan salıstırıwlar sanın minimallastırıwshı binar izlew terekti quramalı delinedi.
Egerde terek jaratıw algoritmi ádewir mashaqatlı jumıs bolsada, bıraq ol jaratqan terekte izlewdı ámelge asırıwádewir nátiyjeli boladı.Tilekke qarsı, izlew argument itimalıǵı aldınnan belgili bolmaydı.