سوال ۳
یک «مقایسه کننده» را مطابق شکل زیر تعریف می‌کنیم:
این مقایسه کننده دو عدد را به عنوان ورودی دریافت کرده، عدد کوچک‌تر را در خط اول خروجی خود و عدد بزرگ‌تر را در خط دوم خروجی قرار می‌دهد. با وصل کردن تعدادی از این مقایسه کننده‌ها بر اساس یک نظم خاص می‌توان یک «مدار مرتب‌کننده» سخت بطوری که تعدادی عدد (از ورودی دریافت نموده و سپس از تعدادی عمل مقایسه این اعداد را به صورت مرتب در خروجی قرار دهد. به عنوان مثال شکل زیر یک مدار مرتب‌کننده با چهار ورودی را نشان می‌دهد:
این مدار شامل ۴ ردیف و ۲ عدد «زوج ردیف» می‌باشد. نحوه کار یک مدار مرتب‌کننده به این صورت است که در هر مرحله تمامی مقایسه‌کننده‌های یک ردیف که دو عدد ورودی خود را دریافت کرده‌اند هم‌زمان با هم عمل می‌کنند. در ابتدای مرحله‌ی اول اعداد بر روی خطوط ورودی قرار دارند. پس از تعداد مراحلی برابر با تعداد ردیف‌ها اعداد به‌صورت مرتب در خروجی ظاهر می‌شوند.
نحوه‌ی کار مدار مرتب‌کننده فوق برای اعداد ورودی ۳، ۲، ۴ و ۱ به صورت زیر است:
یک مدار مرتب‌کننده‌ی $n$ تایی دارای $n$ خط با شماره‌های ۱ تا $n$ است که ردیف‌های شماره فرد شامل مقایسه‌کننده‌هایی است که خطوط با شماره‌ی $2k-1$ و $2k$ $(k=1,2,…)$ را با هم مقایسه می‌کند و مقایسه‌کننده‌های ردیف‌های زوج خطوط با شماره ی $2k+1$ و $2k$ $(k=1,2,..)$ را با هم مقایسه می‌نماید.
یک مدار مرتب‌کننده‌ی ۸ تایی را در شکل زیر می‌بینید:
الف) حدس بزنید که یک مدار مرتب‌کننده‌ی $n$ تایی حداقل باید شامل چند زوج ردیف باشد و تعداد کل مقایسه‌کننده‌های آن را به‌دست آورید. در این قسمت اثبات لازم نیست.
ب) ثابت کنید که مدار مرتب‌کننده‌ی $n$ تایی با تعداد زوج ردیف‌هایی که در قسمت الف حدس زده‌اید، کلیه‌ی جایگشت‌های ورودی از اعداد صفر و یک را مرتب می‌کند. در این قسمت باید حدس بند الف را برای ورودی‌های صفر و یک بطور کامل اثبات نمایید.
برای دریافت بخشی از نمره‌ی این قسمت می‌توانید آن‌را برای $n=8$ ثابت کنید.