Ўзбекистон республикаси ахборот технологияларива коммуникациял арини ривожлантириш вазирлиги

Ўзбекистон республикаси ахборот технологияларива
коммуникациял арини ривожлантириш вазирлиги
Тошкент ахборот технологиялари университети Самарқанд филиали

"Компютер инжиниринг" факультети

"Компютер тизимлари" кафедраси

" Ma'lumotlar tuzilmasi va algoritmlar” фанидан

Мавзу:
«Тезкор саралаш»

Гуруҳ : ТТС-20-01 Бажарди: Отамуродов И. Т Текширди:

Самарқанд – 2022

Топшириқ

Quick sort алгоритми орқали Республикамиздаги вилоятлар майдонини ўсиш тартибида жойлаштиринг. (Фойдаланган саралаш алгоритмингиз ҳақида назарий маълумотлар беринг?)

Мундарижа

Топшириқ 2
Quick sort algoritmi 2
Mассивни бўлиш 3
Рекурсив қайта тартиблаш 4
Ўзбекистон Республикаси ҳудудлари рўйхатини уларнинг ер майдонига кўра саралаш дастури 5
Сайтлар 7

Quick sort algoritmi

Амалий мақсадлар учун саралаш алгоритмини танлаб, дастурчи " quicksort тез саралаш" деб номланган усулда тўхташи мумкин (шунингдек " quick sort " инглизча тез саралаш). У 1960 йилда инглиз олими Чарлз Хоаре томонидан ишлаб чиқилган бўлиб, у кейинчалик Москва Давлат университетида машина таржиMasи билан шуғулланган. Алгоритм, ишлаш принципига кўра, алмаштиришли саралаш синфига киради (аралаштириш саралаш, пуфакчаларни саралаш ва бошқалар), юқори иш тезлиги билан ажралиб туради.

Тез саралашнинг ўзига хос хусусияти – таянч нисбатан Mассивни икки қисмга бўлиш операциясига таянишидир. Masалан, агар кетма-кетликни ўсиш тартибида саралаш керак бўлса, унда қийматлари таянч елемент қийматидан кичик бўлган барча елементлар чап қисмга жойлаштирилади ва қийматлари таянч елементдан катта ёки тенг бўлган елементлар ўнг қисмга жойлаштирилади.

Қайси элемент таянч элемент сифатида танланишидан қатъий назар, массив сараланади, аммо барибир энг муваффақиятли ҳолат-бу маълумот елементининг ҳар икки томонида тахминан тенг миқдордаги элементлар жойлашишидир. Агар олинган қисмларнинг ҳар бирининг узунлиги битта елементдан ошса, бунинг учун саралашни рекурсив равишда бажариш керак, яъни.ҳар бир сегментда алгоритмни қайта ишга тушириш керак.
Таянч элементнинг танлови натижага таъсир қилмайди ва шуг сабабли танлов исталган елементга тушиши мумкин. Шунга қарамай, юқорида таъкидлаб ўтилганидек, алгоритмнинг энг катта самарадорлигига кетма-кетликни тенг ёки тахминан тенг қисмларга ажратилишиган мос елементини танлашда эришилади. Аммо, қоида тариқасида, маълумот етишMasлиги туфайли бундай елементни аниқ аниқлаш мумкин еMas, шу сабабли кўпинча тасодифий элемент таянч элемент сифатида қабул қилинади..Шундай қилиб, тезкор саралаш алгоритми иккита асосий босқични ўз ичига олади:

• 
  Mассивни таянч элементга нисбатан бўлиш;
  
• 
  Mассивнинг ҳар бир қисмини рекурсив саралаш.