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

{{جعبه اطلاعات الگوریتم
| کلاس           = [[الگوریتم مرتب‌سازی]]
| تصویر         = [[پرونده:Odd even sort animation.gif]]
| زیرنویس تصویر = نمونهٔ مرتب کردن جابه‌جایی زوج و فرد در مرتب‌سازی یک فهرست از ارقام تصادفی.
| داده‌ها        = [[آرایه (ساختار داده)|آرایه]]
| زمان بدترین   = <math>O(n^2)</math>
| زمان بهترین   = <math>O(n)</math>
| زمان متوسط    = 
| پیچیدگی فضایی = <math>O(1)</math>
}}
از نظر محاسباتی، '''مرتب‌سازی زوج و فرد''' {{به انگلیسی|Odd–even sort}} یا مرتب‌سازی بر اساس تقدم و تاخر جز [[الگوریتم]]های مرتب‌سازی نسبتا ساده هستند که در اصل برای استفاده در [[پردازنده‌های موازی|پردازنده‌های چند هسته]] در ارتباطات درونی (محلی) توسعه یافته‌است. این مرتب‌سازی نوعی از مرتب‌سازی نسبی است که در آن از بسیاری از ویژگی‌های [[مرتب‌سازی حبابی]] استفاده شده‌است. توابع این الگوریتم از طریق مقایسه همه جفت‌های (فرد، زوج) بررسی شده که از عناصر هم جوار هستند، عناصر را به ترتیب در جایگاه خود در زوج مرتب (اول کوچکتر و بعد بزرگتر) قرار می‌دهند. گام بعدی تکرار جفت سازی (زوج، فرد) عناصر هم جوار و بررسی آن‌ها است. این مراحل به تناوب بین زوج‌های (فرد و زوج) و (زوج و فرد) تکرار شده تا جایی که لیست به‌طور کامل مرتب شود.<ref>{{cite web|last=Phillips|first=Malcolm|title=Array Sorting|url=http://homepages.ihug.co.nz/~aurora76/Malc/Sorting_Array.htm#Exchanging_Sort_Techniques|website=Homepages.ihug.co.nz|access-date=3 August 2011|url-status=dead|archive-url=https://web.archive.org/web/20111028201105/http://homepages.ihug.co.nz/~aurora76/Malc/Sorting_Array.htm#Exchanging_Sort_Techniques|archive-date=28 October 2011}}</ref>

== مرتب‌سازی در آرایه‌های پردازنده ==
در پردازنده‌های موازی با یک مقدار پردازش شده و ارتباطات محلی باهمسایه‌های راست و چپ، پردازنده به‌طور هم‌زمان به انجان عملیات مقایسه و تبادل آن با همسایگان خود به صورت متناوب بین جفت‌ها (فرد و زوج) و (زوج و فرد) می‌پردازد. این الگوریتم در ابتدا توسط  هابرمن در سال ۱۹۷۲ ارائه شد و درپردازنده‌ها کارایی بسیاری داشت. گسترش این الگوریتم باعث کارآمدتر شدن پردازنده‌ها در عمل‌ها ترکیبی شد.
به‌طور خلاصه مراحل کار این نوع الگوریتم‌ها به این صورت است که هر پردازنده در هر مرحله زیر لیست مربوط به خور را با استفاده از بهینه‌ترین الگوریتم خود را به روش تقسیم - [[ادغام|مرتب‌سازی ادغامی]] یا روش تقدم و تاخر - ادغام مرتب‌سازی می‌کند و آن‌ها را با [[لیست‌های هم جوار|فهرست مجاورت]] خود مقایسه می‌کند. در هر مرحله جفت‌های (فرد و زوج) و (زوج و فرد) به صورت متناوب برای برای تشکیل جفت‌های جدید با لیست‌های هم جوار تکرار می‌شود.<ref>N. Habermann (1972) "Parallel Neighbor Sort (or the Glory of the Induction Principle)," CMU Computer Science Report (available as Technical report AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Springfield VA 22151).</ref>

== روش باتچر ==
یکی دیگر از روش‌های مربوط به این گونه الگوریتم‌ها که با استفاده از عملیات‌های (مقایسه – تبادل) و (ایده آل – درهم) صورت می‌گیرد روش باتچر است. روش باتچر در پردازنده‌های موازی با ارتباطات دراز مدت مؤثر و کارآمد است.<ref>{{citation|journal=Advances in Computers|editor1-first=Franz L.|editor1-last=Alt|editor2-first=Marshall C.|editor2-last=Yovits|title=Parallel Sorting Algorithms|first1=S.|last1=Lakshmivarahan|first2=S. K.|last2=Dhall|first3=L. L.|last3=Miller|name-list-style=amp|volume=23|publisher=Academic Press|pages=295–351|isbn=978-0-12-012123-6|year=1984|doi=10.1016/S0065-2458(08)60467-2|url=https://books.google.com/books?id=Mo2Q-TEwKGUC&pg=PA322}}</ref>

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

<syntaxhighlight lang="javascript">
       /* فرض بر این است که آرایه‌ای از عناصر مرتب شده‌اند */
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;
      }
  }
}
</syntaxhighlight>

== پیوند به بیرون ==
* [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/oemen.htm H.W. Lang   FH Flensburg   lang@fh-flensburg.de   Impressum   ©   Created: 31.01.1998   Updated: 18.05.2010]
* [https://web.archive.org/web/20120623191236/http://siber.cankaya.edu.tr/ozdogan/GraduateParallelComputing.old/ceng505/node132.html Cem Ozdogan 2006-12-27 ]
* [https://web.archive.org/web/20120517025022/http://ww2.cs.mu.oz.au/498/notes/node34.html Aaron HARWOOD 2003-10-22 ]

== منابع ==
{{پانویس}}

{{مرتب‌سازی}}

[[رده:الگوریتم‌های مرتب‌سازی]]
[[رده:مرتب‌سازی‌های پایدار]]
[[رده:مرتب‌سازی‌های سنجشی]]