Stooge sort

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Stooge sort
Sorting stoogesort anim.gif
Տեսակտեսակավորման ալգորիթմ
Տվյալների կառուցվածք
Վատագույն դեպքում կատարումը
Օգտագործում էզանգված


Stooge sort (Սորտավորում մասերով), ռեկուրսիվ ալգորիթմ ժամանակի բարդությամբ ։ Տվյալ ալգորիթմը համեմատած ուրիշ էֆեկտիվ ալգորիթմերի հետ ինչպիսին են՝ պղպջակային սորտավորումը, միաձուլման սորտավորումը շատ ավելի դանդաղ է աշխատում։

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

  • Եթե վերջնականի արժեքը փոքր է սկզբնականից, ապա փոխել տեղերով։
  • Եթե ցանկում կա երեքից ավել արժեք, ապա՝
    • <<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-06-18 

Արտաքին հղումներ[խմբագրել | խմբագրել կոդը]