Referati toshkent 2023 saralash algoritmlari mohiyati va ularning samaradorligini baholash. Reja

Birinchi qism

pivot = 0, ya’ni arr[pivot] = 2. Yuqoridagi kabi katta (O) va kichik (a) (b) sikllarni ishga tushiramiz. Kichik sikllar i = 2, j = 3 holatda to‘xtaydi. arr[i] va arr[j] elementlarning o‘rnini almashtiramiz.

Keyingi kichik sikllarda i = 3, j = 2 holatda to‘xtaydi. i > j, demak katta siklni to‘xtatamiz va arr[pivot] hamda arr[j] o‘rnini almashtiramiz.

pivot elementning chap tarafida o‘zidan kichkina, o‘ng tarafida o‘zidan katta elementlar joylashdi. arrayning birinchi qismini pivot bo‘yicha yana ikki ajratamiz va ularni alohida-alohida tartiblaymiz:


Shunda birinchi qism tartiblanib bo‘lgach, array’ning birinchi pivotdan chap qismi tartiblandi:

Ikkinchi qism

pivot = 0, ya’ni arr[pivot] = 12. Yuqoridagi kabi katta (O) va kichik (a) (b) sikllarni ishga tushiramiz. Bunda i = 6, j = 14 dan boshlanadi. Kichik sikllar i = 10, j = 13 holatda to‘xtaydi. arr[i] va arr[j] elementlarning o‘rnini almashtiramiz.

(O) katta sikl ishlashda davom etadi. Biz (a) va (b) sikllarni qayta ishga tushiramiz. Kichkina sikllar i = 13 va j = 12 holatda to‘xtaydi. i > j bo‘lgani uchun katta sikl ham to‘xtaydi. arr[pivot] va arr[j] o‘rnini almashtiramiz.

pivot element (12) ning chap tarafida o‘zidan kichik elementlar, o‘ng tarafida o‘zidan katta elementlar joylashdi. Endi pivot bo‘yicha yana kichkina qismlarga ajratib, ularni alohida-alohida tartiblaymiz.
2.1 qism

2.2 qism

2.1 qismni tartiblashni davom ettiramiz.
2.1 qismda pivot = 6, ya’ni array’ning 6-elementi. Yuqoridagi kabi katta (O) va kichik (a) (b) sikllarni ishga tushiramiz. Bunda i = 7, j = 11 dan boshlanadi. Kichik sikllar i = 7, j = 6 holatda to‘xtaydi. i > j, katta (O) sikl ham to‘xtaydi. arr[pivot] va arr[j] teng. Bu 2.1 qismda pivot eng kichkina son bo‘lgani uchun bu qismda o‘zgarish bo‘lmadi. 2.1 qismni pivot bo‘yicha ikkiga ajratamiz. Aniqrog‘i birinchi qismi bo‘lmaydi, faqat ikkinchi qismi (2.1.2) bo‘ladi xolos:

2.1.2 qismni tartiblashni davom ettiramiz.
2.1.2 qismda pivot = 7, ya’ni array’ning 7-elementi. Yuqoridagi kabi katta (O) va kichik (a) (b) sikllarni ishga tushiramiz. Bunda i = 8, j = 11 dan boshlanadi. Kichik sikllar i = 11, j = 11 holatda to‘xtaydi. i = j, katta (O) sikl ham to‘xtaydi. arr[pivot] va arr[j] o‘rnini almashtiramiz:

2.1.2 qismni pivot bo‘yicha ikkiga ajratamiz. Aniqrog‘i ikkinchi qismi bo‘lmaydi, faqat birinchi qismi (2.1.2.1) bo‘ladi xolos:

2.1.2.1 qismni tartiblashni davom ettiramiz.
2.1.2.1 qismda pivot = 7, ya’ni array’ning 7-elementi. Yuqoridagi kabi katta (O) va kichik (a) (b) sikllarni ishga tushiramiz. Bunda i = 8, j = 10 dan boshlanadi. Kichik sikllar i = 10, j = 10 holatda to‘xtaydi. i = j, katta (O) sikl ham to‘xtaydi. arr[pivot] va arr[j] o‘rnini almashtiramiz:

2.1.2.1 qismni pivot bo‘yicha ikkiga ajratamiz. Aniqrog‘i ikkinchi qismi bo‘lmaydi, faqat birinchi qismi (2.1.2.1.1) bo‘ladi xolos:

2.1.2.1.1 qismni tartiblashni davom ettiramiz.
2.1.2.1.1 qismda pivot = 7, ya’ni array’ning 7-elementi. Yuqoridagi kabi katta (O) va kichik (a) (b) sikllarni ishga tushiramiz. Bunda i = 8, j = 9 dan boshlanadi. Kichik sikllar i = 9, j = 8 holatda to‘xtaydi. i > j, katta (O) sikl ham to‘xtaydi. arr[pivot] va arr[j] o‘rnini almashtiramiz:

Biz 2.1 qismni tartiblashni tugatdik

2.2. qismi da ikkita element bor, ular tartiblangach:

Biz arrayning ikkinchi qismini ham tartiblashni tugatdik.

Shunda tartiblash yakunlangach, array

tartiblandi.
QuickSortning kodda ifodalanishi:

#include using namespace std; function quickSort(arr) {