“Маълумотлар тузилмаси ва алгоритмлар” фанига кириш

Tanlash orqali saralash algoritmi:

• For i=1 to n-1
• x=a(i)
• K=I
• For j=i+1 to n
• if a(j)< x then
• k=j
• x=a(k)
• endif
• Next j
• a(k)=a(i)
• a(i)=x
• Next i return

• Almashtirish orqali saralash (Pufaksimon)

• Algoritm g’oyasi

• n - 1 marta massivda quyidan yuqoriga qarab yurib kalitlar jufti-jufti bilan taqqoslanadi. Agar pastki kalit qiymati yuqoridagi jufti kalitidan kichik bo‘lsa, u holda ular o‘rni almashtiriladi.

• Misol:

• Almashtirish orqali saralash algoritmi tahlili

• Eng yomon, ya’ni boshlang‘ich ob’ektlar kalit qiymatlari bo‘yicha kamayish tartibida berilgan holat.

• Taqqoslashlar soni:

• O‘rinlashtirishlar soni:

• Saralashga ketgan vaqt:

Almashtirish usuli uchun psevdokod:

• For i=2 to n
• for j=n to I step -1
• if a(j)
• x=a(j-1)
• a(j-1)=a(j)
• a(j)=x
• endif
• next j
• next I
• Return
• Bu holatda bitta bo’sh o’tish bo’ladi.Elementlarni ortiqcha almashtirmaslik uchun fl o’zgaruvchi (flajok) kirinish mumkin.

Bu ozgaruvchi agar birorta ham almashtitish bolmasa, false qiymat oladi. Quyida kerakli qo’shimchalar kursiv bilan ko’rsatilgan:

• FL=TRUE
• For i=2 to n
• IF FL=FALSE THEN RETURN
• ENDIF
• FL=FALSE
• for j=n to I step -1
• if a(j)FL=TRUE
• x=a(j-1)
• a(j-1)=a(j)
• a(j)=
• endif
• next j
• next I
• Return
• i.

5-Mavzu bo‘yicha nazorat savollari

• 1. Saralash deganda nima tushiniladi?
• 2. Saralashning vazifasi nimadan iborat?
• 3. Saralashning maqsadi nimadan iborat?
• 4. Qo‘yish orqali saralashning g‘oyasini tushuntirib bering?
• 5. Tanlash orqali saralash tushunchasi?
• 6. Pufaksimon saralash nima?