Urganch Davlat Universiteti Fizika-matematika fakulteti

Transpozitsiya usuli

Ushbu usulda topilgan element ro’yhatda bitta oldingi element bilan o’rin almashtiriladi. Agarda mazkur elementga ko„p murojaat qilinsa, bittadan oldinga surilib borib natijada ro’yhat boshiga kelib qoladi. Ushbu usulning afzalligi shundaki, tuzilmada ko„p murojaat qilinadigan elementlar ro’yhat boshiga bitta qadam bilan intiladi.

Ushbu usulning qulayligi u nafaqat ro’yhatda, balki tartiblanmagan massivda ham samarali ishlaydi (sababi faqatgina ikkita yonma-yon turgan element o’rin almashtiriladi).
Bu usulda uchta Ko’rsatkichdan foydalanamiz (rasm):
p – ishchi Ko’rsatkich
q – yordamchi Ko’rsatkich, p dan bitta qadam orqada bo’ladi
s – yordamchi Ko’rsatkich, p dan ikkita qadam orqada bo’ladi

Transpozitsiya usuli bilan ro’yhatni qayta tartibga keltirish . Biz tomonimizdan topilgan uchinchi element ro’yhat boshiga bir qadam suriladi (ya’ni ikkinchi bo’lib qoladi). Birinchi element Ko’rsatkichi uchinchi elementga joylashtiriladi, ikkinchi element Ko’rsatkichi to’rtinchi, shunday qilib uchinchi element ikkinchi joyga joylashib qoladi. Agar mazkur elementga yana bir bor murojaat qilinsa, u holda u ro’yhat boshida bo’lib qoladi.

node *s=NULL; node *q=NULL; node *p=table; while (p != NULL){
if (key == p->k){ //transponerlaymiz
if( q ==NULL){//o‘rinlashtirish shart emas search=p;
exit(0);
}
q->nxt=p->nxt; p->nxt=q;
if (s == NULL) table = p; else
search=p; exit(0);
}


S=q; q=p; p=p-nxt; }
Search=Null;
exit(0);
Aytaylik bizga massiv berilgan:
a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Ushbu masalani yechishda eng birinchi xayolga keladigan usul - bu massivni ketma-ket har bir elementini solishtirib chiqish va bu usul:
Chiziqli qidiruv - Linear Search deb ataladi, va bu usul kodi quyidagi ko'rinishda:
func linearSearch(a []int, condidate int) int {
for i := 0; i < len(a); i++ {
if a[i] == condidate {
return i
}
}
return -1 }
Ko'rib turganingizdek, funksiyamiz 2 ta parametr qabul qiladi, birinchisi massivni o'zi, ikkinchisi esa biz qidirayotgan element. Agar uni topa olmasak, "-1" qiymatni qaytaramiz.
Endi bundan optimal bo'lgan usul - binar(ikkilik) qidiruvni ko'rib chiqsak.
Bu usulda ham funksiyaga 2 ta parametr, birinchisi massiv o'zi keyin esa biz qidirayotgan elementni parametr sifatida beriladi. Qidiruv esa quyidagicha:
Dastlab biz massiv boshi va oxirini o'zimiz uchun o'zgaruvchilarda belgilab olamiz, mening kodimda bu left va right o'zgaruvchilaridur:
left := 0 right := len(a)

so'ngra quyidagi shart bajarilgan holda

leftquyidagi ketma-ket operatsiyalarni amalga oshiramiz

1. 
   left va right index lari markazidagi elementni topamiz (left + right) / 2
   
2. 
   topilgan elementimiz biz qidirayotgan elementga teng bo'lsa unda mid elementni javob sifatida qaytaramiz
   
3. 
   agar a[mid] elementimiz biz qidirayotgan elementdan kichkina bo'lsa biz left = mid deb belgilaymiz va shunda a[mid:right] bo'lagida qidiruv davom etadi.
   
4. 
   agar a[mid] elementimiz biz qidirayotgan elementdan katta bo'lsa demak right = mid deb belgilaymiz shunda qidiruv a[left:mid] bo'lagida qidiruv davom etadi.
   

Shu zaylda qidiruv left < right shart bajarilmagunicha davom etadi, agar bu jarayonda biz qidirgan element topilmasa u xolda -1 javob qaytariladi, quyida dastur kodi keltirilgan:
func binarySearch(a []int, condidate int) int {
left := 0 right := len(a)
for left < right {
mid := (left + right) / 2
if a[mid] == condidate {
return mid ; }
if a[mid] < condidate {
left = mid
} else {
right = mid
} }
return -1 }
Bu usul binar qidiruvni iterativ usuli deyiladi, shuningdek bu algoritmni rekursiya usulida ham yozish mumkin, rekursiv usulni erinmasangiz o'zingiz yozib ko'ring. Bitta urinishda ko'pchilik dasturchilar bu narsani to'g'ri yoza olishmaydi va bu normal holat, chunki xato bor joyda o'z ustida ishlash uchun imkoniyat bo'ladi.
Endi bu qidiruv usullarini ayrim jihatlarini keltirib o'tamiz:

• 
  funksiyaga berilayotgan massiv Binar qidiruv uchun albatta o'sish tartibida bo'lishi talab qilinadi, chiziqli qidiruv uchun esa berilayotgan massiv qay tartibda bo'lishini ahamiyati yo'q
  
• 
  chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi, binarda esa algoritmidan kelib chiqib chiziqliga nisbatan ancha kam solishtirish amali bajariladi, chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar qidiruvniki ko'pi bilan O(log n)