تخيل أنك تعمل بمكتبة الكلية.
وبينما أنت تقضي فترة ظهيرة هادئة،
فجأة تصل شحنة من 1280 كتابًا مختلفًا.
أنزلت الكتب في صورة خط واحد طويل مستقيم،
ولكنها جميعها غير مرتبة،
ونظام الفرز الآلي معطل.
وما زاد الوضع سوءًا هو أن الدراسة ستبدأ غدًا،
مما يعني أنه وفي الصباح الباكر
ستأتي جموع من الطلاب باحثة عن هذه الكتب.
فكيف يمكن ترتيبها كلها في الوقت المحدد؟
إحدى الطرق هي البدء بناحية واحدة من الخط بالزوج الأول من الكتب.
إذا كان أول كتابين مرتبين، فاتركهما كما هما.
وإلا فبادلهما.
ثم تفقّد الكتابين الثاني والثالث
وكرر العملية
واستمر حتى تصل إلى نهاية الخط.
في مرحلة ما، ستقابل الكتاب الذي يجب أن يكون الأخير،
وستستمر بتبديله بكل كتاب لاحق،
محركًا إياه على طول الخط إلى أن يصل إلى موقعه الصحيح في النهاية.
ثم ابدأ من البداية وكرر العملية
لوضع الكتاب قبل الأخير في مكانه الصحيح،
واستمر حتى يتم ترتيب جميع الكتب.
يسمى هذا النهج "ترتيب الفقاعات".
وهو بسيط لكن بطيء.
ستقوم بإجراء 1279 مقارنة في الجولة الأولى
ثم 1278، وهكذا،
ليبلغ المجموع 818560 مقارنة.
إذا استغرقت كل مقارنة ثانية واحدة فقط، فستستغرق العملية أكثر من تسعة أيام.
الإستراتيجية الثانية هي البدء بترتيب أول كتابين فقط،
ثم مقارنة الكتاب الثالث بالكتاب الموجود بالمركز الثاني.
إذا كان مكانه قبل الكتاب الثاني فبدلهما،
ثم قارنه بالكتاب الموجود بالمركز الأول،
وأعد التبادل إذا لزم الأمر.
الآن رتبت الكتب الثلاثة الأولى.
استمر بإضافة كتاب واحد في كل مرة إلى الخط الفرعي المرتّب،
مقارنًا ومبدلًا الكتاب الجديد بالذي يسبقه
حتى يوضع بشكل صحيح بين الكتب المرتبة حتى الآن.
يسمّى هذا "ترتيب الإدراج".
بعكس ترتيب الفقاعات، فإنه لا يستلزم مقارنة كل زوج من الكتب.
في المتوسط، من المتوقع أن نحتاج فقط لمقارنة كل كتاب
بنصف عدد الكتب التي سبقته.
في هذه الحالة، فإن مجموع عدد المقارنات
سيكون 409280،
مستغرقًا ما يقرب خمسة أيام.
ولكن ما زلت تُجري عددًا كبيرًا من المقارنات.
فإليك فكرة أفضل.
أولًا، اختر كتابًا عشوائيًا،
اعتبره الفاصل وقارنه بكل كتاب آخر.
ثم قسّم الخط
عن طريق وضع كل الكتب التي تسبق الفاصل على يساره
وكل الكتب التي تليه على يمينه.
لقد وفرت الكثير من الوقت
بعدم الاضطرار لمقارنة أي من الكتب على اليسار
بتلك الموجودة على اليمين مرة أخرى.
الآن بالنظر فقط إلى الكتب على اليسار
يمكنك مرة أخرى اختيار كتاب فاصل عشوائي
وفصل الكتب التي سبقته عن تلك التي تلته.
استمر بإنشاء أقسام فرعية هكذا
حتى تحصل على مجموعة من الخطوط الفرعية الصغيرة،
ترتب كل منها سريعًا باستخدام إستراتيجية أخرى كترتيب الإدراج.
كل جولة من التقسيم تتطلب حوالي 1280 مقارنة.
إذا كانت الأقسام متوازنة نوعًا ما،
فإن تقسيم الكتب إلى 128 خطًا فرعيًا من عشرة سوف يستغرق حوالي سبع جولات،
أو 8960 ثانية.
فرز هذه الخطوط الفرعية سيضيف حوالي 22 ثانية لكل منها.
عمومًا فإن هذه الطريقة المعروفة باسم "الترتيب السريع"
يمكنها ترتيب الكتب في أقل من ثلاث ساعات ونصف.
ولكن هناك تعقيد.
قد تصبح أقسامك غير متوازنة، مما يتسبب في ضياع الوقت.
لحسن الحظ، هذا نادرًا ما يحدث.
هذا هو سبب كون الترتيب السريع أحد أكثر الإستراتيجيات فعاليةً
والمستخدمة من قبل المبرمجين اليوم.
يستعملونه لأغراض مثل ترتيب الوحدات في متجر إلكتروني حسب السعر
أو إنشاء قائمة بجميع محطات الوقود الواقعة على مقربة من موقع معين
مرتبة حسب المسافة.
وفي حالتك، فقد انتهيت من الترتيب السريع ووفرت الوقت.
مجرد يوم مشوق آخر في المكتبة.