مرتب‌سازی زوج و فرد

در پردازنده‌های موازی با یک مقدار پردازش شده و ارتباطات محلی باهمسایه‌های راست وچپ، پردازنده به‌طور هم‌زمان به انجان عملیات مقایسه و تبادل آن با همسایگان خود به صورت متناوب بین جفت‌ها (فرد و زوج) و (زوج و فرد) می‌پردازد. این الگوریتم در ابتدا توسط هابرمن در سال ۱۹۷۲ ارائه شد و درپردازنده‌ها کارایی بسیاری داشت. گسترش این الگوریتم باعث کارآمدتر شدن پردازنده‌ها در عمل‌ها ترکیبی شد. به‌طور خلاصه مراحل کار این نوع الگوریتم‌ها به این صورت است که هر پردازنده در هر مرحله زیر لیست مربوط به خور را با استفاده از بهینه‌ترین الگوریتم خود را به روش تقسیم - مرتب‌سازی ادغامی یا روش تقدم و تاخر - ادغام مرتب‌سازی می‌کند و آن‌ها را با فهرست مجاورت خود مقایسه می‌کند. در هر مرحله جفت‌های (فرد و زوج) و (زوج و فرد) به صورت متناوب برای برای تشکیل جفت‌های جدید با لیست‌های هم جوار تکرار می‌شود.

یکی دیگر از روش‌های مربوط به این گونه الگوریتم‌ها که با استفاده از عملیات‌های (مقایسه – تبادل) و (ایده آل – درهم) صورت می‌گیرد روش باتچر است. روش باتچر در پردازنده‌های موازی با ارتباطات دراز مدت مؤثر و کارآمد است.

این الگوریتم در الگوریتم‌های تک پردازنده، مانند مرتب‌سازی حبابی، ساده اما کارآمد نیست. در اینجا یک شاخص مبتنی بر صفر فرض شده‌است:

       /* فرض بر این است که آرایه‌ای از عناصر مرتب شده‌اند */
var sorted = false;
while(!sorted)
{
    sorted=true;
    for(var i = 1; i <list.length-1; i += ۲)
    {
        if(a[i]> a[i+1])
        {
            swap(a, i, i+1);
            sorted = false;
      }
  }

    for(var i = 0; i <list.length-1; i += ۲)
    {
        if(a[i]> a[i+1])
        {
            swap(a, i, i+1);
            sorted = false;
      }
  }
}

• H.W. Lang FH Flensburg lang@fh-flensburg.de Impressum © Created: 31.01.1998 Updated: 18.05.2010
• Cem Ozdogan 2006-12-27
• Aaron HARWOOD 2003-10-22