الجزء الثاني

Sorting and order statistics

مقدمة

في الباب الأول اتعرضنا لمقدمة عن الـ algorithms عرفنا فيها يعني إيه algorithms وإيه مدى أهميتها واستخداماتها , وشفنا الـ sorting problem وشفنا 2 algorithms بيحلوها هما الـ insertion sort وال merge sort وكل واحد فهمنا الـ design approach (طريقة التصميم) اللي اتبنا على أساسها وهما بالترتيب incremental approach و divide-and-conquer approach , كمان اتعرضنا لأساسيات مهمة جدا هتقابلنا كتير في دراسة الـ algorithms زي الـ asymptotic notation وال recurrence وال probabilistic analysis and randomized algorithms .

في الباب التاني هنكمل على الـ sorting problem وهناخد more advanced algorithms بتحلها , في الباب الأول أقصى تقدم وصلناله هو الـ merge sort algorithm اللي كان الـ running time بتاعه Θ(nlgn) , في الباب التاني هنشوف algorithms الـ running time بتاعها linear يعني Θ(n) .

Sorting problem

نفتكر مع بعض ازاي بنعرف أي problem؟ بنعرفها من خلال تحديد الـ input وال output , يعني عندنا إيه وعايزين نوصل لإيه , أما هنوصل إزاي فده الـ algorithm اللي هنستخدمه , وبالتالي ممكن نعرف الـ sorting problem كالتالي:

Input: a sequence of numbers (a₁, a₂, …., a_n)

Output: a permutation(reordering) (a’₁, a’₂, …., a’_n) of the input sequence such that (a’₁ <= a’₂ <= … <= a’_n).

يعني الدخل مجموعة أرقام والخرج نفس المجموعة بس مرتبين تصاعديا.

في أغلب الـ problems مش بنرتب مجموعة أرقام منفصلة بالشكل ده , ولكن بنرتب مجموعة objects أو records وال object أو الـ record هو مجموعة data بتمثل حاجة معينة زي شخص كتاب جهاز إلخ , يعني أي شئ ممثل بشوية data أو معلومات , كمثال ممكن في system بيمثل جامعة أكون برتب مجموعة طلبة , أو في system بيمثل business معين أكون برتب مجموعة منتجات , على أي حال بيكون معايا مجموعة records وأنا برتبهم , وكلمة record معناها شوية معلومات متخزنة عن حاجة معينة , يعني إنت لو حضرت محاضرة ولخصتها في ورق أو ملف عالكمبيوتر فده record (شوية بيانات عن حاجة معينة) , الـ record بنقسمه لجزئين , أول جزء عبارة عن المعلومة اللي بنرتب يناءا عليها زي مثلا لوبنرتب الطلبة بناءا على درجاتهم أو بنرتب منتجات بناءا على أسعارها , والجزء ده بنسميه key (مفتاح) لإن هو المفتاح اللي نستخدمه في عملية الترتيب , أما الجزء التاني فهو باقي الـمعلومات اللي متخزنة في الـ record , زي لو طالب يبقى إسمه وسنته الدراسية والكورسات اللي بيدرسها إلخ , كلها بيانات مهمة ولكن متهمنيش في عملية الترتيب , الجزء ده بنسميه satellite data وكلمة satellite ليها معنى مشهور اللي هو "قمر صناعي" ولكن ليها معنى تاني هو اللي يهمنا وهو "جسم فضائي صغير بيلف حولين جسم فضائي كبير أو دولة صغيرة تايعة لدولة كبيرة" وعلشان كدة سموها satellite data لإن في الـ sorting problem أهم حاجة الـ key اللي احنا بنرتب بناءا عليه أما باقي الـ data فهي بتلف حواليه وتابعة ليه.

لما بنيجي نعمل sorting مش بنعمل permutation (إعادة ترتيب) لل keys بس ولكن لل records كلها وبالتالي لو الـ satellite data حجمها كبير فمش هيكون efficient ان انت تفضل تنقل الـ records في الـ memory وهي حجمها كبير ففي الحالة دي ممكن نسيب الـ records مكانها في الـ memory ونعمل array of pointers كل pointer بيشاور على record ونعمل permutation على الـ array of records دي لإن حجمها صغير.

واحنا بنكتب pseudocode ل algorithm لل sorting بنكتبه كأنه هيشتغل على مجموعة أرقام منفصلة وبعد كدة تحويل ال algorithm ده إنه يشتغل على مجموعة records بتكون حاجة straightforward (سهلة) , وده concept (مبدأ) عام انك لما تكتب pseudocode ل algorithm تكتبه عام جدا وتفاصيل ال implementation تبقى في مرحلة تحويله ل programming language وده لإن الغرض من ال algorithm انه يوضح الفكرة بلغة بسيطة ويعمل abstraction لل low-level details .

Why sorting?

أكيد أي واحد يقرأ الكتاب يقول ليه يعني الـ sorting هي المشكلة اللي بدأ بيها وخد فيها بابين كاملين؟ الحقيقة الكاتب قال إن كتير من علماء الكمبيوتر بيعتبروا الـ sorting problem المشكلة الجوهرية في دراسة الـ algorithms وذكر أسباب أهمها : 

• إن الـ sorting بتستخدم ك subroutine في حل مشاكل تانية كتيرة جدا يعني بتمثل جزء كبير من حل المشاكل دي.
• إن فيه design techniques كتيرة ممكن نفهمها من خلال دراسة الـ sorting problem.
• إن فيه engineering issues (مواضيع هندسية) بتظهر أثناء تنفيذ الـ sorting algorithms زي الـ caching وال memory hierarchy.