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

Արագ դասակարգում
ՏեսակWikimedia duplicated page?

Ալգորիթմի կարճ նկարագրությունԽմբագրել

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

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

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

ԱլգորիթմԽմբագրել

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

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