کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
429970 687756 2016 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Sorting nine inputs requires twenty-five comparisons
ترجمه فارسی عنوان
ارزیابی نه ورودی نیاز به 25 مقایسه دارد
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
چکیده انگلیسی


• Twenty-five comparators are minimal to sort nine inputs.
• Twenty-nine comparators are minimal to sort ten inputs.
• New symmetry-breaking results control the growth of the search space.
• Optimized and parallelized algorithms for generating size-optimal sorting networks.
• Use of SAT-solving to speed up the last part of the computation.

This paper describes a computer-assisted non-existence proof of 9-input sorting networks consisting of 24 comparators, hence showing that the 25-comparator sorting network found by Floyd in 1964 is optimal. As a corollary, the 29-comparator network found by Waksman in 1969 is optimal when sorting 10 inputs.This closes the two smallest open instances of the optimal-size sorting network problem, which have been open since the results of Floyd and Knuth from 1966 proving optimality for sorting networks of up to 8 inputs.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 82, Issue 3, May 2016, Pages 551–563
نویسندگان
, , , ,