Արագ դասակարգում

Վիքիպեդիայից՝ ազատ հանրագիտարանից
(Վերահղված է Quicksortից)
Jump to navigation Jump to search
Արագ դասակարգում
ՏեսակWikimedia duplicated page

Արագ դասակարգում (անգլ.՝ quicksort), հաճախ անվանում են qsortqsort Си լեզվի ստանդարտ գրադարանի իրականացման անունով։ Այն հայտնի դասակարգման ալգորիթմ է, որը մշակվել է անգլիացի ինֆորմատիկ Չարլզ Խոարի կողմից 1960 թվականին։

Ալգորիթմի կարճ նկարագրություն[խմբագրել | խմբագրել կոդը]

  • ընտրել էլեմենտ, հենակետային անվանումով
  • համեմատել մնացած էլեմենտները հենակետայինի հետ, համեմատման հիման վրա բաժանելքանակությունը 3 մասի - «փոքր հենակետային», «հավասար» և«մեծ», դասավորել նրանց

հերթականությամբ՝ փոքր-հավասար-մեծ։

  • կրկնել այն փոքրերի և մեծերի համար

Ալգորիթմ[խմբագրել | խմբագրել կոդը]

Արագ դասակարգումը օգտագործում է «բաժանիր և տիրիր» ստրատեգիան։ Ալգորիթմի քայլերի հաջորդականությունը հետևյալն է՝

  1. Ընտրում ենք զանգվածից մի քանի էլեմենտ, որոնք պետք է անվանենք հենակետային էլեմենտ։ Ալգորիթմի կոռեկտության տեսանկյունից հենակետային էլեմենտի ընտրությունը անկարևոր է։ Ալգորիթմի էֆեկտիվության բարձրացման տեսանկյունից պետք է ընտրվի մեդիանան, բայց առանց լրացուցիչ տեսակավորված տվյալների հնարավոր չե տեղեկություն ստանալ։ Հայտնի ստրատեգիա է ՝ մշտապես ընտրել միևնույն էլեմենտը, օրինակ մեջտեղի կամ վերջին զետեղվածը, ընտրել պատահական ինդեքսով ընտրված էլեմենտ։
  2. Զանգվածից բաժանման օպերացիան՝վերակազմել զանգվածը այնպես, որպեսզի բոլոր էլեմենտները փոքր կամ հավասար գտնվեն հենակետային էլեմենտից ձախ, իսկ հենակետայինից մեծը նրանից աջ։