الفصل الثاني

Getting Started

ضربة البداية

مقدمة

في الفصل الأول اتعرضنا لشوية مفاهيم أساسية عن الـ algorithms وأهمية العلم ده وتطبيقاته , في الفصل الثاني بنبدأ نتعرض عمليا لأول algorithms لحل مشكلة ال sorting اللي تم توضيحها في الفصل الأول , هندرس بالتفصيل 2 algorithms لحل المشكلة دي وهما insertion sort و merge sort.

Insertion Sort

كلمة sort يعني ترتيب وكلمة insertion جاية من الفعل insert بمعنى يدخل أو يدرج(كأنك في ال algorithm هتمسك حاجة وتدرجها في مكان معين وهتشوف ده بيحصل إزاي) , ال insertion sort بيشتغل بطريقة بسيطة ومفهومة جدا , هنفرض اننا بنرتب تصاعدي من الصغير للكبير , ببساطة معاك شوية أرقام عددهم n وعايز ترتبهم , هنرتبهم واحدة واحدة , بس عايزين لما نرتب شوية نفصلهم عن الباقيين , يعني دايما معانا مجموعة أرقام مرتبة ومجموعة أرقام غير مرتبة , تبدأ ناخد رقم رقم , طبعا لما تكون مجموعة العناصر مكونة من رقم واحد فهي مترتبة جاهزة ,فلما ناخد أول رقم مش هنحتاج نرتب , كدة مجموعة الأرقام المرتبة مكونة من الرقم ده بس والمجموعة الغير مرتبة مكونة من باقي الأرقام , نبدأ ناخد رقم من المجموعة الغير مرتبة ونحطه في مكانه المظبوط في المجموعة المرتبة (وده ال insertion انك بتدرج رقم جديد من المجموعة الغير مرتبة في المجموعة المرتبة) في كل مرة المجموعة الغير مرتبة بتقل عنصر والمجموعة المرتبة بتزيد عنصر لغاية في النهاية تنتهي المجموعة الغير مرتبة وبكدة يكون ال algorithm رتب كل الأرقام بنجاح , لغاية دلوقتي بيتهيقلي كل ال algorithm واضح إلا خطوة انك تحط الرقم في مكانه المظبوط (Insertion) هي اللي ممكن تكون بتفكر هتتعمل ازاي برمجيا , ببساطة انت هتحط الرقم ده وسط مجموعة أرقام مرتبة أصلا (اللي هي ال insertion من المجموعة الغير مرتبة للمجموعة المرتبة) وبالتالي انت بتعدي على عناصر المجموعة المرتبة دي لغاية متلاقي أول عنصر أصغر منه تروح حاطه قبليه , وبكدة هو كل اللي قبليه أصغر منه وكل اللي بعديه أكبر منه(يعني في مكانه المظبوط تمام)

تعالى نشوف مثال علشان الأمور توضح أكتر

 

في الصورة اللي قدامك خطوات ترتيب مجموعة الأرقام (5, 2, 4, 6, 1, 3) , طبعا قلنا أن أول عنصر هو كدة كدة مترتب , وبالتالي أول خطوة(a) بتبدأ بإدراج (insertion) تاني عنصر في مكانه المظبوط في المجموعة المترتبة بأنها تجيبه قبل العنصر 5 لأن 2 أصغر من 5

تاني خطوة(b) بتعمل insertion لتالت عنصر اللي هو 4 بأنها تجيبه بعد ال 2 وقبل ال 5

تالت خطوة(c) بتعمل insertion لرابع عنصر اللي هو 6 بأنها تسيبه مكانه لأنه أكبر من كل العناصر اللي في المجموعة المرتبة

رابع خطوة(d) بتعمل insertion لخامس عنصر اللي هو 1 بأنها تجيبه أول عنصر لأنه أصغر من كل العناصر اللي في المجموعة المرتبة

خامس وآخر خطوة بتعمل insertion لسادس وآخر عنصر اللي هو 3 بأنها تجيبه بعد ال 2 وقبل ال 4

هو في ال algorithm بيفرض إن مجموعة العناصر موجودين في array data structure وكلنا عارفين ان ال array مفهاش امكانية انك تحط عنصر بين عنصرين فعلشان تحط عنصر بين عنصرين لازم تعمل shift(إزاحة) لكل العناصر اللي انت عايز تحط العنصر الجديد قبليها وبالتالي توفر مكان للعنصر الجديد , علشان كدة في أسهم كتير بتشير لعملية الإزاحة دي في الصورة.

تعالى بقى نشوف ال pseudocode بتاع أول algorithm معانا , قبل منشوف ال pseudocode أنا بنصح أي حد إنه يجرب يكتب ال pseudocode بنفسه قبل ميشوفه بعد مفهم ال algorithm وبعد ميتأكد ان ال pseudocode بتاعه صح يحاول ي implement(ينفذ) ال algorithm بإيده برده بأي لغة برمجة قبل ميشوف ال implementation بتاعه , الحوار ده هيبني عندك ال ability(القدرة) إنك تحل مشكلة(problem solving) بالبرمجة , لإن دايما بيكون الموضوع واضح إنه سهل بس لما تيجي تنفذه بإيدك بتظهر مشاكل , لما تحل المشاكل دي انت بتبني skills(مهارات) كتير .

ال pseudocode بتاعنا ببساطة قبل منشوفه هو إنك هتعدي على العناصر من العنصر التاني(لإن الأول مترتب) لغاية آخر عنصر في كل مرة بتاخد العنصر وتحطه في مكانه المظبوط وخلص الحوار , ازاي بقى الكلام ده يتكتب بالانجليزي ويكون translatable (قابل للترجمة) ﻷي لغة برمجة هو ده اللي هتشوفه في الصورة اللي جاية.

في الـ line(السطر) الأول عملية ال loop من العنصر التاني لغاية آخر عنصر

في line 2 بيخزن العنصر اللي هيعمله insertion في variable(متغير) وسماه key

في line 3 كتب comment(تعليق) انه هيعمل insertion للعنصر ده في مكانه المظبوط في المجموعة المرتبة

في line 4 عرف variable وسماه i واداله قيمة j - 1 وهو ال index(مكان) العنصر اللي قبل العنصر اللي هنعمله insertion

في line 5 دخل while loop وحط ال condition(الشرط) بتاعها ان ال i > 0 يعني يمر على عناصر المجموعة المرتبة كلها و a[i] > key يعني العنصر الحالي من عناصر المجموعة المرتبة يكون أكبر من العنصر اللي عايز يعمله insertion يعني لسة موصلش لعنصر أصغر من العنصر اللي عايز يعمله insertion علشان يحطه قبليه

في line 6 بيعمل shift للعنصر الحالي من عناصر المجموعة المرتبة علشان يوفر مكان لل key العنصر اللي عايز يعمله insertion

في line 7 بيقلل المتغير i بواحد علشان ينقله يشاور على مكان العنصر اللي جاي من عناصر المجموعة المرتبة

سطر 6 و 7 بيتنفذوا تحت شرط الـ while

في line 8 ود خارج ال while يعني هيتنفذ بعد مال while تنتهي بيحط ال key في المكان اللي ال index بتاعه i + 1 وده لإن ال while loop ب terminate (تنتهي) وال i بيشاور على أول عنصر أصغر من العنصر اللي عايز يعمله insertion وبالتالي هو بيحطه قبليه وده بعد متكون ال while عملت shift لكل العناصر اللي أكبر منه علشان توفرله مكان

ملحوظة : في الـ pseudocode دايما بيعتبر ان اول index في الـ array هو 1 مش 0 زي معظم لغات البرمجة.

طبعا دي مش الطريقة الوحيدة لكتابة pseudocode لل insertion sort في الحقيقة أي واحد ممكن يكتب pseudocode بطريقته.

Analyzing algorithms

عملية تحليل analyzing ال algorithm تنقسم إلى جزئين أول جزء إثبات ال correctness(صحة) ال algorithm والجزء الثاني تحديد ال resources(المصادر) اللي بيستهلكها ال algorithm يعني ال cost(التكلفة) بتاعة ال algorithm زي عدد ال instructions اللي بتتنفذ على ال cpu علشان يحل المشكلة أو عدد ال bytes اللي بيستهلكها من ال memory وغيره من ال hardware resources. الجزئين دول التفصيل فيهم بيحتاج معرفة بالرياضة علشان كدة انا ه skip(اعدي) أول جزء خالص وده على مدار الشرح أما الجزء التاني فهذكره بشكل abstracted(مبسط) بدون إثبات وخوض في تفاصيل رياضية , وده مش معناه إن الأجزاء دي مش مهمة ولكن لتسهيل الكورس للقارئ.

أهم measure(مقياس) لأي algorithm هو ال running time وهو الوقت اللي بيستهلكه فالتنفيذ أو بشكل أدق عدد ال instructions اللي بتتنفذ , ال analysis بيتقسم ل 3 أنواع , الأول هو ال worst case يعني أسوء حالة أو أقصى time ممكن يستهلكه ال algorithm وده مهم جدا لأنه بيعمل guarantee(ضمان) إن ال algorithm مش هياخد أكتر من كدة , النوع التاني هو best case وهو أقل time وده في حالة إن المشكلة محلولة أصلا زي مثلا في مشكلة ال sorting لو ال input مترتب أصلا , النوع التالت هو ال average case أو ال expected case وده بيستخدم أكتر حاجة وهو هو نفسه ال worst case لأنه دايما ال average نص ال worst وال constants(ثوابت) دي بيتم إهمالها.

لتحديد ال time اللي بيستهلكه ال algorithm بيتم حسايه كدالة في عدد الـ input لأن الـ time بيزيد بزيادة الـ input كمان بيتم إهمال ال low order terms يعني مثلا لو حسبنا ال running time بتاع algorithm وطلعه مثلا an³ + bn² + cn + d بحيث ان a, b, c, d ثوابت و n عدد ال input هيتم إهماله ال n², n وكل الثوابت ويتم عرض ال running time في صورة n3 لأن العناصر التانية فعلا ممكن تهمل عند زيادة الدخل لأرقام كبيرة , فلو فرضنا ان الدخل مليون مثلا كل ال terms دي فعلا ممكن اهمالها بالنسبة لل n3 وده ما يسمى بال order of growth.

Insertion sort running time

عند حساب ال worst time لل insertion sort هنلاقيه n² وال best time هنلاقيه n , وهيتم شرح بإذن الله إزاي الكلام ده بنوضحه بال notation في الفصل التالت.

Insertion sort Implementation

بعد ماشفت الـ pseudocode وفهمته يا ريت تحاول تنفذ الـ algorithm بنفسك , وده implementation لل algorithm بلغة الـ C ممكن تطلع عليه للإفادة.

https://github.com/hossamnasser938/Introduction-to-Algorithms-TextBook/blob/master/insertion_sort.c

Designing algorithms

شرحنا في الفصل الأول الفرق بين الـ design وال analysis وقلنا إن ال design انك بتصمم أو بتبتكر algorithm أما الـ analysis انك بتحلل algorithm يعني بتقيس مدى صحته وكفاءته, في طرق كتير جدا لتصميم الـ algorithms منها الطريقة اللي بيشتغل بيها ال insertion sort وهي طريقة incremental(تزايدية) يعني إيه بقى؟ بشكل عام يعني في كل خطوة ال algorithm بيحل المشكلة ل item(عنصر) واحد من ال problem instance واحنا عارفين يعني إيه problem instance من الفصل الأول , وبشكل خاص يعني كل مرة بيرتب رقم من مجموعة الأرقام اللي عايزة تترتب. في طريقة تانية أكثر كفاءة اسمها divide-and-conquer , كلمة divide يعني يقسم (كأنك بتمسك حاجة وتقسمها نصين) وكلمة conquer يعني يغزو كأنك قدامك جيش(ال problem) وعايز تهزمه فبتقسمه نصين علشان تضعف قواه وتمسك كل نص تغزوه لوحده وبالتالي تقدر تتغلب عليه , كمان العملية دي مش بتتعمل مرة واحدة يعني انا لو بحارب الجيش ده (ال problem) مش بقسمه لنصين وابدا أحارب كل نص منهم .. لأ , انا بقسمه نصين وبعد كدة اقسم كل نص لنصين وهكذا لغاية ماوصل لـ2 جنود بس اقسمهم برده وامسك واحد بس اقدر اهزمه بسهولة جدا , وبعدين ارجع امسك الجندي التاني اهزمه بسهوله كدة هزمت جنديين امسك بقى جنديين تاني بنفس الطريقة واهزمهم كدة هزمنا 4 وبعدين 8 وبعدين 16 وهكذا لغاية مكون هزمت الجيش كله أو حليت المشكلة كلها, الطريقة دي عبارة عن 3 خطوات divide وبعدين conquer وفي الاخر combine يعني اجمع أو بعد مقسمت وحليت إجمع أجزاء المشكلة.

افتكر انك كدة فاهم طريقة ال divide and conquer بشكل logically(منطقيا) ولكن علشان تفهمها وتقدر توظفها برمجيا في حل المشاكل لازم تفهم ال recursion (العودية) ايه ده بقى؟ ال recursion ببساطة ان ال algorithm بيرجع ي call(ينادي أو يعيد) نفسه على أجزاء صغيرة من المشكلة لحل المشكلة الكبيرة, هناخد مثال بسيط يوضح الامور اكتر , لو انت عايز تعمل algorithm يحسب الfactorial(المضروب) والمضروب دالة رياضية بسيطة بتتحسب لرقم واحد يعني مضروب 5 مضروب 7 كدة, بتتحسب بانك تضرب الرقم ده في كل الارقام الأقل منه لغاية الواحد, مثلا factorial(5) = 5 * 4 * 3 * 2 * 1 = 120 , لو فكرت في تنفيذ دالة المضروب هتلاقي انك بتعمل نفس العملية اللي هي الضرب لدخل مختلف كل مرة , يعني بتضرب 5 * 4 ,وبعدين الناتج * 3 وبعدين الناتج * 2 , ومن هنا ال recursion ان ال algorithm ينادي او يعيد نفسه, هكتب pseudocode سريع كدة لتنفيذ دالة المضروب بال recursion علشان نفهمه عمليا.

factorial(n)

1 if n > 1

2 return n * factorial(n - 1)

3 else

4 return 1

ال algorithm بيتنفذ بشكل بسيط جدا , بيشوف العدد اللي عايز يجبله المضروب لو هو 1 يبقى المضروب بتاعه 1 لو هو اكتر بيرجع حاصل ضرب الرقم ده في (وينادي نفس ال algorithm ويغير الدخل ل العدد - 1) , كمثال لو دخلتله 5 هيرجع 5 * وينادي على مضروب 4 فترجع 4 * وينادي على مضروب 3 فترجع 3 * وينادي على مضروب 2 فترجع 2 * مضروب 1 فترجع 1 وبكدة ال algorithm رجع 5 * 4 * 3 * 2 * 1 , بيتهيقلي كدة فكرة ال recursion مفهومة.

Merge sort

كلمة merge يعني يدمج (كأنك بتدمج حاجتين في حاجة واحدة) وال merge sort هو algorithm بيتبع طريقة ال divide-and-conquer اللي لسة فاهمينها , ال algorithm بسيط ان شاء الله.

في الصورة اللي قدامك تقدر تشوف ان ال algorithm عبارة عن 5 خطوات بس

ال algorithm بياخد دخل: A اللي هي مجموعة العناصر الكلية اللي المفروض تترتب , p و r هما indices(أماكن) اللي بتحدد بداية ونهاية المجموعة اللي هتترتب , وده لان كل مرة بنبعت subset أو جزء من المجموعة الكلية اللي عايزة تترتب.

في السطر 1 بيختبر لو المجموعة الحالية تحتوي على أكتر من عنصر ولا لأ

في السطر 2 بيحسب ال index بتاع منتصف المجموعة علشان يعمل divide

في السطر 3 بي call ال algorithm مع نص المجموعة الأول

في السطر 4 بي call ل algorithm مع نص المجموعة التاني

في السطر 5 بيعمل merge بين المجموعتين

أعتقد كل الخطوات واضحة ماعدا الخطوة ال 5 مبهمة التنفيذ وهي خطوة ال merge او ال combine ودي algorithm لوحده هنشوفه دلوقتي.

دلوقتي محتاجين نعمل procedure (مجموعة خطوات مرتبة) أو algorithm لتنفيذ عملية ال combine او ال merge , نوصف المشكلة الأول علشان نعرف نحلها , عندي مجموعتين من العناصر مرتبين وعايز أجمعهم في مجموعة واحدة مرتبة , علشان المجموعتين أصلا مرتبين فأصغر عنصر هو إما أول عنصر في المجموعة الأولى أو أول عنصر في المجموعة التانية , وبالتالي ال procedure هيكون إنه يختبر أول عنصر من المجموعتين وياخد أصغر واحد فيهم ويكون هو ده أصغر عنصر في المجموعتين , بعد كدة ياخد أول عنصرين تاني بعد حذف العنصر اللي هو خده ويختبرهم وياخد أصغر عنصر وهكذا لغاية ممجموعة منهم تنتهي كدة يقدر يحط باقي المجموعة التانية بالترتيب لأن المجموعة التانية فاضية والمجموعة دي مترتبة أصلا.

في مشكلة , ازاي يعرف إن في مجموعة منهم خلصت؟ في طريقة سهلة انك في كل iteration(لفة في ال loop) تختبر وصلت لنهاية مجموعة ولا ﻷ , ودي طريقة مكلفة ﻹنها بتضيق خطوة في كل iteration , وفي طريقة تانية ودي انك تحط أكبر رقم ممكن في نهاية كل مجموعة علشان لو خلصت لما يقارن الرقم ده بأي عنصر في المجموعة التانية ياخد عنصر المجموعة التانية , ودي طريقة أقل تكلفة.

في الصورة اللي قدامك ال procedure اللي بيحل مشكلة ال merging

وهو بياخد دخل: A المجموعة الكلية اللي هتترتب , p هو ال index اللي بيحدد بداية المجموعة الأولى و q ال index اللي بيحدد نهاية المجموعة الأولى وبداية المجموعة التانية و r ال index اللي بيحدد نهاية المجموعة التانية.

السطر 1 بيحدد عدد العناصر في المجموعة الأولى

السطر 2 بيحدد عدد العناصر في المجموعة التانية

السطر 3 بينشئ 2 arrays علشان يخزن فيهم المجموعتين بعيد عن المجموعة الأم

السطر 4 بيدخل for loop بعدد عناصر المجموعة الأولى

السطر 5 بينسخ عناصر المجموعة الأولى في ال array الجديدة

السطر 6 و 7 بينسخ فيهم المجموعة التانية بنفس الطريقة

السطر 8 و 9 بيحط رقم كبير جدا في نهاية كل array

السطر 10 و 11 بيحط قيمة 1 في كل counter(عداد) i للمجموعة الاولى , و j للمجموعة التانية

من السطر 12 ل 17 بيشوف أصغر عنصر في المجموعتين وينسخه في ال array الكبيرة وبعد ميخلص يكون رتب المجموعتين

في الصورتين اللي قدامك مثال على عملية ال merge بالخطوات من a ل i.

وفي الصورة دي مثال لل algorithm كله على input صغير.

Merge sort running time

ال worst time لل merge sort هو nlg(n) instructions وده ليه إثبات رياضي إحنا مش هنخوض فيه.

Merge sort implementation

ده implementation لل merge sort بلغة الـ C

https://github.com/hossamnasser938/Introduction-to-Algorithms-TextBook/blob/master/merge_sort.c

Insertion sort VS Merge sort

أول فرق بين ال 2 algorithms في ال memory , لأن ال insertion sort مش بيحتاج يحجز أي حاجة في ال memory وكل شغله sorted in place يعني بيرتب في نفس ال data structure اللي جاية فيها مجموعة الأرقام , أما ال merge sort فزي ما شفنا بينسخ المجموعتين اللي هيعملهم merge في arrays جديدة وبالتالي بيحتاج memory إضافية. أما بالنسبة لل running time فمن الواضح جدا إن ال merge sort أسرع في التنفيذ من ال insertion sort ولكن ده في حالة ان ال input كبير ولكن لو ال input صغير ال insertion sort بيكون أسرع , وده لإن الفرق بين الاتنين هو ان ال insertion sort عبارة عن c1 * n * n ولكن ال merge sort عبارة عن c2 * n * lgn. ال c1 في ال insertion sort دايما بيكون قليل أما c2 في ال merge sort دايما بيكون كبير فلو ال input صغير فرق الثوابت هيبان أكتر من الفرق بين ال n وال lgn , أما في حالة إن ال input كبير ففرق ال n وال lg n هيغطي على الثوابت. ناخد مثال لو c1 = 5 و c2 = 50

لو ال input عبارة عن 8 أرقام

running time for insertion sort = 5 * 8 * 8 = 320

running time for merge sort = 50 * 8 * lg(8) = 50 * 8 * 3 = 1200

أما لو ال input عبارة عن 1024 رقم

running time for insertion sort = 5 * 1024 * 1024 = 5242880

running time for merge sort = 50 * 1024 * lg(1024) = 50 * 1024 * 10 = 512000

لو ال input عبارة عن 1048576 رقم

running time for insertion sort = 5 * 1048576 * 1048576 = 5497558139000

running time for merge sort = 50 * 1048576 * lg(1048576) = 50 * 1024 * 20 = 1048576000

وهكذا كل متزود ال input كل ميظهر الفرق الشاسع بين ال merge sort وال insertion sort.