Stooge sort

Stooge sort (Սորտավորում մասերով), ռեկուրսիվ ալգորիթմ ժամանակի բարդությամբ $O(n^{\log _{1{,}5}{3}})\approx O(n^{2.71})$։ Տվյալ ալգորիթմը համեմատած ուրիշ էֆեկտիվ ալգորիթմերի հետ ինչպիսին են՝ պղպջակային սորտավորումը, միաձուլման սորտավորումը շատ ավելի դանդաղ է աշխատում։

Stooge sort
Տեսակ	տեսակավորման ալգորիթմ
Տվյալների կառուցվածք	$O(n)$
Վատագույն դեպքում կատարումը	$O(n^{log{3}/log{1.5}})$
Օգտագործում է	զանգված

Ալգորիթմի տեսքը

• Եթե վերջնականի արժեքը փոքր է սկզբնականից, ապա փոխել տեղերով։
• Եթե ցանկում կա երեքից ավել արժեք, ապա՝
  • <<Stoogesort>> սորտավորել ցանկի սկզբի 2/3-րդ մասը
  • <<Stoogesort>> սորտավորել ցանկի վերջի 2/3-րդ մասը
  • կրկին <<Stoogesort>> սորտավորել ցանկի սկզբի 2/3-րդ մասը

Ռեալիզացիայի օրինակը

 algorithm stoogesort(array L, i = 0, j = length(L)-1)
     if L[j] < L[i] then
         L[i] ↔ L[j]
     if j - i > 1 then
         t = (j - i + 1)/3
         stoogesort(L, i  , j-t)
         stoogesort(L, i+t, j  )
         stoogesort(L, i  , j-t)
     return L

Օրինակը C լեզվով

void stoogesort(int *item, int left,int right)
{
   register int tmp, k;
   if(item[left]>item[right])
   {
      tmp=item[left];
      item[left]=item[right];
      item[right]=tmp;
   }
   if((left+1)>=right)
        return;
 
   k=(int)((right-left+1)/3);
   stoogesort(item,left, right-k);
   stoogesort(item, left+k, right);
   stoogesort(item, left, right-k);
}

Աղբյուրներ

• Բլաք, Պոլ Ե. «stooge sort». Ալգորիթմերի և տվյալների կառութվածքի բառարան. NIST. Վերցված է 2011 թ․ հունիսի 18-ին.

Արտաքին հղումներ

• Everything2.com – Stooge sort
• Sorting Algorithms (պարունակում է Stooge sort)
• Stooge sort-ի գործածումը և համեմատումը