Stooge sort

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


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 

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