Тезкор саралаш. Тезкор саралаш тавсифи. Массивлврни бўлаклаш. Тезкор саралаш самарадорлиги. Балансланган бўлаклаш. Режа

Aim.uz

Тезкор саралаш. Тезкор саралаш тавсифи. Массивлврни бўлаклаш. Тезкор саралаш самарадорлиги. Балансланган бўлаклаш. Режа:

1. 
   Тезкор саралаш. Тезкор саралаш тавсифи;
   
2. 
   Массивлврни бўлаклаш;
   
3. 
   Тезкор саралаш самарадорлиги;
   
4. 
   Балансланган бўлаклаш;
   

Тезкор саралаш алгоритми
Тезкор саралаш нафақат ўқитиш учун балки амалиётда ҳам кенг тарқалган саралаш алгоритми. Одатда, тезкор саралаш алгоритмида катта ҳажмдаги қийматларни ҳисоблаш учун мўлжалланган O (n log n) мураккаблик мавжуд. Бу саралаш алгоритми деярли оддий, агар буни англаган бўлсангиз тезкор саралашни ҳам пуфакчали саралаш каби тез ёза оласиз. Бўлиш ва таққослаш стратегияси қўлланилган. Қуйида рекурция қадами тасвирланган.

1. 
   Таянч қиймат танлаш. Биз ўрта элементни таянч қиймат сифатида оламиз, лекин у сараланган қийматларнинг ўртасидаги элементни, ҳаттоки массивда мавжуд бўлмаган сонни ҳам олиши мумкин.
   
2. 
   Бўлаклаш. Шу йўсинда элементларни қайта жойлаштиради, таянчдан кичик бўлган элементларнинг барчаси таянчдан чапга, катталари ўнгга ўтади. Таянчга тенг бўлган элементлар унинг ҳар қайси қисмига тушиши мумкин. Ёдда тутинг массив тенг бўлмаган қисмларга бўлиниши мумкин.
   
3. 
   Ҳар икки қисмни саралаш. Тезкор саралаш рекурцив ўнг ва чап қисмларнинг ҳар икки томонига қўлланиши мумкин.
   

Бўлаклаш алгоритми қисмларда
Иккита индекс бор i ва j ҳудди шу дастлабки бўлаклаш бошланишида i массивнинг биринчи элементини, j эса охирги элементини кўрсатади. Сўнгра алгоритм i ни таянчга тенг ёки ундан катта қийматли элемент топулгунча олдинга суради. j индекс эса таянчга тенг ёки кичик қийматли элемент топулгунча орқага силжийди. Агар i ≤ j бўлса кейин улар ўрин алмашишади ва i кейинги позицияга (i + 1) га j эса (j - 1) га ўтади. Алгоритм i > j шарт бажарилганда тўхтайди. Бўлаклашдан кейин i-нчи элементлар таянчдан кичик ёки тенг j-нчидан кейингилари эса таянчдан катта ёки тенг.
Мисол: {1,12,5,26,7,14,3,7,2}ни тезкор сараланг.

	Сараланмаган массив
	Танланган сон қиймати 7
	12 ≥ 7 ≥ 2, 12 билан 2 нинг ўрни алмаштирамиз.
	26 ≥ 7 ≥ 7, 26 билан 7 нинг ўрни алмаштирамиз.
	7 ≥ 7 ≥ 3, 7 билан 3 нинг ўрни алмаштирамиз.
	i > j, бўлаклаш тўхтатилади.
	Бўлакларга ажратилади ва алоҳида бўлаклар рекурцияга жўнатилади
	Сараланган массив

Ёдда тутинг биз бу ерда фақат битта рекурция қадами кўрсатдик, мисолимиз чўзилиб кетмаслиги учун. Лекин, аслида, {1,5,7,3} ва {14,7,26,12} лар кейин рекурцив сараланган.