یو پروګرام میتود په توګه Quicksort

په 1960، K. الف Hoar د معلوماتو د چټک تاسيساتو لپاره د میتود جوړ، شو تر ټولو مشهورې. نن دا په پراخه توګه د پروګرامونو کارول، لکه څنګه چې د مثبت مال ډېر لري: دا کولای شي د عمومي مواردو کې وکارول شي، دا په اضافي حافظه یوه کمه اندازه زیاتوالی، سره د لست په مختلفو ډولونو او د تطبيق آسانه ته اړتیا لري. خو د ضررونو په شتون لري، چې د Quicksort لري: په کارولو سره د کار د غلطيو ډک اجازه، او دا د حده بې ثباته.

خو دا د ټولو زده کړې بڼه ده. د پیسو د لومړي Hoare وروسته، ډېر څه د خپلو ګڼ مطالعه. لوی اډې د وخت مصرف پر دنده، چې د تجربوي شواهد له ځانه سره په موندلو نظري پوښتنې رامنځته شو. د اساسي الګوریتم او زيات سرعت ښه دریښتینو وړانديزونه شوي دي.

Quicksort ډېر عام دی، نو کولای شي په هرځای کې وموندل شي. د خپل بنسټ طريقه داسې ده چي پلي TList.Sort، په ټولو نسخې ددولفی، د وخت خلاصه کړی دنده دا ونيو چې په C د بشپړولو لپاره، qsort ++ (1 پرته) شتون لري.

د عملياتو د اساسي اصل کولای شي د "بېل ېې" په توګه جوړه شي. کيږی چی په دوه ډلو په لست کې د ماتولو او د خپل ځان له خوا د هرې برخې ډلبندي شوي دي. دا راغلي دي چې زيات پام بايد د جلا پروسه، هغه مهال چې د لاندې واقع ته ورکړل شي: ده ټاکل یوه اډه عنصر له خوا او په نسبي ډول د هغه د ټول لست د بياترتيبولو. جوړ شوی چې د نوماندانو د يوې ډلې د چپ، ارزښت چې تر ټولو نورو د لېږد د اصولو لږ دی. دا وګرځي چې په ولاړه لست د اصلي عنصر په کې خپل دريځ دی. د بل پړاو - د عناصر خپلوان د اډې ته په دواړو خواوو يوه ننګونه د تکرارونې د تاسيساتو د دندو. دا پای د پروسې کار کوي که په لست کې يواځې یو عنصر دی، چې ده ته ولاړه شی. په دې ډول، د دې لپاره د يو چټک ډول د يو پروګرام دنده تر تسلط، دا ضروري ته د ټیټې کچې الگوريتم د کار پوه دی: الف) د اډې غړي انتخاب؛ ب) د تر ټولو اغيزمنه permutation لست دوه سيټه سره د وړو او لويو ارزښتونو توليدوي.

لومړی په اصولو سره آشنا. غوره کله چې د اډې غړي، باید ترجيحا د اوسط له لست څخه وټاکل شي. بيا د وقفې په دوه مساوي نیمایي برخې وېشل شوی دی. يوازې محاسبه د اوسط ارزښت په لست ډېره ستونزمنه ده، نو حتی د چټک تاسيساتو bypasses دې کلکولس لوري. خو سره د اعظمي او يا لږ تر لږه د ارزښت د اساسي عنصر د انتخاب - هم نه غوره ټاکنه ده. په هغه صورت کې د یو داسې هوډ پيدا تش لستونه به تضمين شي، او د دوهم پوره. نو په پای کې چې د مرکز غړي په توګه باید غوره يو چې نژدې څو اوسط دی شي، خو په اعظمي او لږ تر لږه.

کله چې يو انتخاب ده معلومه، چې تاسو کولای شي چې د عضوي الګوریتم ته لاړ. دا تش په نامه داخلي کړۍ_ګانې چټک ننداره. هر څه پر دوه د چټک لاسرسي د شاخص په جوړ: په لومړي سر څخه د حق، د دوهم پاتې، د هغې په خلاف د عناصرو ته ولاړ شي، له پاتې حق. پیل د عملياتو د اجرا حق دې: د شاخص په لست کې دی او د اصلي د ټولو ارزښتونو سره پرتله کړئ. د څرخ بشپړ شوی نه وي کله چې د عنصر دی چې د خط څخه کم يا مساوي. دا ده چې، د يوه په پرتله شته دی او د هغه شاخص ارزښت کموي. په چپ لاس کله چې د کار څخه تر یا مساوي ارزښت زیات پای. دلته، د په پرتله د ارزښت د زياتوالي.

د partitioning الګوریتم چې پکې quicksort دې پړاو کې، د دوو حالتونو ښایي راپورته شي. لومړی دا چې په چپ د شاخص په پرتله ښي لږ. ددې مانا کې تېروتنه، نو عناصر چې دا په لست کې څرګنده شوه په غلط نظم شته. السته راوړنې - د هغوی ځایونه سره بدلوي. دوهم حالت دی چې کله د کالم دواړه سره برابر او يا دي اوښتي. دا په ګوته کوي چې د لست د يوه بريالي جلا، چې وي، د کار اوس بشپړ شوي دي.