Мундарижа Кириш

Блокларни ўқишдаги амаллар сони

Маълумотларни катта блоклаб ўқилиши элементлаб ўқишдан сезиларли тез бажарилади. Шунинг учун самарадор кўп фазали саралаш катта блокли ёзувларни ўқиш билан ишлайди. Лекин исталган ҳолда ўқишнинг амаллари сони самарадорликка сезиларли таъсир кўрсатади.

Бўлакларни қуриш босқичида биз бўлакдаги битта маълумот блоки бўйича ўқиймиз ва блокларни ўқиш R амалларни беради. Мадомики хотирага фақат S ёзувлар сиғади ва бирлаштириш босқичида бизга иккала бўлакдан ҳам ёзувлар керак ҳамда бизга бу боқичда S/2 ўлчамдаги блокларни ўқишга тўғри келади. Бирлаштириш алгоритмининг ҳар бир босқичида биз барча маълумотларни ўқиймиз. Бу шуни билдирадики, ҳар бир ўтишда N/(S/2)– 2R блоклар ўқилади. Ўтишлар сони га тенг, шунинг учун бирлаштиришдаги ўқиш амаллари умумий сони га тенг.

Шундай қилиб, алгоритмдаги умумий ўқиш амаллари сони

га тенг.

2.2.8. Саралаш алгоритмларининг қиёсий ҳарактеристикалари

Саралаш алгоритмларининг асосий хусусиятлари билан қуйидаги жадвал орқали танишамиз:

№	Алгоритм номи	Қийинлик баҳоси	Афзаллиги	Камчилиги
1	Танлаш йўли билан саралаш	O(n^2)	Жуда оддий, кичик рўйхатларни тез саралайди	Катта рўйхатларда секин ишлайди
2	Ўрнига қўйиш усули билан саралаш	O(n^2)	Жуда оддий, кичик рўйхатларни тез саралайди	Катта рўйхат-ларда секин ишлайди
3	Алмаштириш “пуфакча” усули	O(n^2)	Айримлари сараланган рўйхатларда тез ишлайди	Бошка барча ҳолларда секин ишлайди
4	Массивни бўлиш усули (“тез” саралаш )	O(n log n) дан ~ O(n^2) гача	Ката рўйхатларни тез саралайди	Кўп миқдордаги бир хил қиймат-ларда муаммоли ишлайди
5	Бирлаштириш усули билан саралаш	O(n log n)	Ката рўйхатларни тез саралайди	Вақтинчалик қийматлар учун қўшимча жой талаб қилади
6	“Пирамида” усули	O(n log n)	Ката рўйхатларни тез саралайди, вақтин-чалик қийматлар учун қўшимча жой талаб қилмайди	Бирлаштириш усулига қараганда секин ишлайди
7	Шелл усули	O(n log n)	Нуқтали сонларни саралайди	Вақтинчалик қийматлар учун қўшимча жой талаб қилади
8	Санаш усули билан саралаш	O(n+k)	Агар кирувчи тарқалган қийматлар катта бўлмаса жуда тез ишлайди	Агар қийматлар >log n бўлса секин ишлайди, вақтинчалик қийматлар учун қўшимча жой талаб қилади, фақат бутун турли маълумотлар билан ишлайди
9	Блокли саралаш	O(n)	Агар маълумотлар тенг тақсимланса жуда тез ишлайди, исталган турдаги маълумотлар билан ишлайди	Санаш усули билан саралаш усулига қараганда секин ишлайди