مرتب‌سازی مسابقه‌ای
مرتب‌سازی مسابقه‌ای یک الگوریتم مرتب‌سازی است. این الگوریتم مرتب‌سازی انتخابی ساده را با استفاده از یک صف اولویت‌دار یا یک درخت برنده برای پیدا کردن عنصر بعدی در مرتب‌سازی بهبود می‌بخشد. در مرتب‌سازی انتخابی ساده، formula_1 عمل صورت می‌گیرد تا عنصر بعدی از formula_2 عنصر را انتخاب کند؛ در یک مرتب‌سازی مسابقه‌ای، formula_3 عمل صورت می‌گیرد (پس از ساختن مسابقه ابتدایی در formula_1). مرتب‌سازی مسابقه‌ای یک تنوع از مرتب‌سازی هرمی است.
درخت برنده نوعی درخت مسابقه است که از formula_2 راس خارجی و formula_6 راس داخلی تشکیل می‌شود. رئوس خارجی نمایندهٔ بازیکنان و رئوس داخلی هر کدام نمایندهٔ یک تک‌مسابقه بین دو بازیکن است. در درخت برنده هر راس داخلی باید بازیکن برنده بین دو راس فرزند خود را ذخیره کند و در انتها ریشه درخت حاوی بازیکنی خواهد بود که در تمام تک‌مسابقه‌ها برنده شده‌است. اگر برنده را در هر تک‌مسابقه بازیکنی در نظر بگیریم که مقدار آن کمتر است؛ در این صورت ریشه درخت اشاره به بازیکنی خواهد داشت که کمترین مقدار را بین تمام بازیکنان دارد. با طراحی چنین داده ساختاری می‌توان الگوریتم مرتب‌سازی مسابقه‌ای را اجرا نمود. اگر آرایه مورد نظر برای مرتب‌سازی دارای formula_7 عنصر باشد؛ درخت مسابقه‌ای با formula_2 راس خارجی (formula_2 اولین عدد توان ۲ است که بزرگتر یا مساوی formula_7 باشد) و formula_6 راس داخلی می‌سازیم. رئوس خارجی به ترتیب به عناصر آرایه اشاره می‌کنند و رئوس خارجی اضافه نیز به هیچ خانه‌ای اشاره ندارند. رئوس داخلی درخت از پایین به بالا به برنده هر تک‌مسابقه اشاره می‌کنند تا زمانی که ریشه مشخص کنندهٔ برندهٔ نهایی شود. برندهٔ نهایی را به عنوان کوچکترین عنصر در ابتدای یک آرایهٔ جدید می‌گذاریم و راس خارجی که به آن اشاره داشت را از دور مسابقات حذف می‌کنیم. در مسیر رسیدن آن راس به ریشه مسابقات را تکرار می‌کنیم تا برندهٔ نهایی را با نبود راس برندهٔ دور قبل شناسایی کنیم. آن‌قدر به این کار ادامه می‌دهیم تا تمام بازیکنان از مسابقات حذف شوند. در این مرحله آرایهٔ ساخته‌شده مرتب خواهد بود.
زمان اجرای این الگوریتم به دو قسمت تقسیم می‌شود. به اندازه formula_1 طول می‌کشد که بازیکنان در رئوس خارجی قرار گیرند و به اندازه formula_1 نیز طول می‌کشد تا درخت برنده تکمیل شده و برندهٔ نهایی مشخص شود. سپس در هر عمل حذف بازیکن از مسابقات به اندازه formula_3 طول می‌کشد تا درخت برنده بازسازی شود. formula_2 مرتبه این عمل انجام می‌شود تا در نهایت آرایه مرتب شود. پس در مجموع زمان اجرای این الگوریتم از formula_16 می‌شود. مقدار حافظه لازم برای این الگوریتم متشکل است از آرایهٔ اولیه و آرایهٔ مرتب شده و یک درخت مسابقه که تعداد رئوس خارجی آن از ۲ برابر تعداد بازیکنان کمتر است. در درخت مسابقه تعداد رئوس داخلی همیشه یکی کمتر از تعداد رئوس خارجی است. پس در کل پیچیدگی فضایی این الگوریتم از formula_1 است.
مرتب‌سازی مسابقه‌ای با استفاده از درخت برنده (آرایه) در زبان برنامه‌نویسی پایتون به صورت زیر پیاده‌سازی می‌شود. در این پیاده‌سازی از مفهوم هرم کمینه، که نوعی هرم دودویی است، استفاده شده که در آن هر راس با اندیس formula_7 در آرایه، پدر دو راس با اندیس‌های formula_19 و formula_20 است. به همین دلیل تعداد رئوس زائد بالا می‌رود و اندازه کل آرایه می‌تواند تا ۴ برابر تعداد اعضای آرایه اولیه افزایش یابد؛ اما به هر صورت پیچیدگی فضایی آن از formula_1 است. import math def build(A, B, x, l, r):
def pop(B):
A = [-8, 3, 17, 57, 0, -19, 21, 5, 965 , 2, 0, 1, 34, 83] n = len(A) B = [None] * (2 ** (math.ceil(math.log2(n)) + 1)) build(A, B, 1, 0, n - 1) sorted_array = [pop(B) for _ in range(n)] print(sorted_array)
Donald Knuth, The Art of Computer Programming, Sorting and Searching, Volume 3, 1973. Stepanov, Alexander and Aaron Kershenbaum. Using Tournament Trees to Sort, Brooklyn: Center for Advanced Technology in Telecommunications, 1986. https://www.cise.ufl.edu/~sahni/cop3530/slides/lec252.pdf