السلام عليكم ورحمة الله نكمل في هذا التسجيل ما بدأناه في التسجيل السابق وكنا في التسجيل السابق قد قدمنا بشرح فكرة الكويك سورت بشكل عام الآن سنقوم باستعراض التفاصيل الخاصة بالكويك سورت شرح عن الكويك سورت بشكل أكثر تفصيلا استعراض السودوكود الخاص بهذه الخوارزمية ثم تحليل التعقيد الزمني الخاص بها وأخيرا سنقوم بتطبيق الكويكسورد باللغة الجافة طيب دهنا ننتقل ننتقل أولا إلى الفكرة الخاصة بالكويكسورت. كما قلنا بأن الكويكسورت تأخذ المصفوفة التي تحتوي مجموعة من العناصر ثم تقوم بتقسيمها إلى مصفوفتين. وهذه المصفوفتين ليس بالضرورة أن تكونان متساويتين. الجزء الأول يحتوي على العناصر التي سيكون ترتيبها بعد عملية الفرز النهائي لجميع العناصر ضمن هذا الجزء.
والمصفوفة الثانية ستحتوي على مجموعة عناصر التي سيكون بعد عملية الفرز النهائي موقعها ضمن هذا الجزء. طيب يمكن أنه عربي. نعرف هذا الشرط بطريقة أخرى بأن نقول بأن جميع العناصر الموجودة في الجزء الأول قيمتها أصغر تماما أو مساوية للعناصر الموجودة في هذا الجزء وبالتالي نضمن أن هذه العناصر موقعها في الجزء الأول وهذه العناصر موقعها في الجزء الثاني دعونا نرى الـ Quick Sort كما هو الحال في تقنية التقسيم ثم الحل تتألف أيضا من ثلاثة أجزاء ثلاثة مراحل.
المرحلة الأولى هي مرحلة التقسيم. وهي التي من خلالها نضمن بأن هذه المصوفة ستكون مجزئة إلى جزئين. جزء يحتوي على مجموعة العناصر التي قيمها أصغر تماما أو مساوية إلى مساوية أو أصغر تماما للعناصر الموجودة في الجزء الثاني في الجزء الثاني.
طيب هذه أول أول آآ مرحلة من مراحل المرحلة الثانية هي مرحلة الكونكور. ومرحلة الكونكور. في divide and conquer أو في طريقة التفريق ثم الحل هو عملية حل كل جزء من هذه الأجزاء بنفس الأسلوب المعتمد في حل المسألة الكلية بطريقة التفريق ثم الحل ولكن هنا نقوم بذلك باستخدام الاستدعاء العودي إذن هو عملية استدعاء عودي لنفس المسألة ولكن بجزء أصغر منها ونقوم بعملية الحل لكل جزء من هذه الأجزاء بنفس الطريقة إذن نرى بأن الconquer هو recursively بشكل عودي نقوم بعملية حل لكل جزء أو عملية فرز لكل جزء من الجزئين من الـ P إلى Q لنفترض أن بدأنا هنا من الـ P وكانت نهاية المصوفة الأولى في الـ R وقمنا بعملية التقسيم بحيث أن عملية التقسيم آخر عنصر في الجزء الأول هو Q وبالتالي سنقوم بعملية الفرز مرة أخرى أو استدعاء لنفس الخوارز مثل QuickSort لفرز العناصر من P إلى Q ومن Q زائداً الواحد هذا العنصر Q Q زائداً الواحد وحتى الار طيب هذه مرحلة الكونكور طيب لدينا المرحلة الأخيرة وهي الكمباين طيب في حال قمنا بفرز الجزء الأول وفرز الجزء الثاني لم يعود بحاجة لعملية الكمباين لأن كل جزء أصبح مكانه لذلك مكتوب هنا لدينا الكمباين هي عملية تريفيال هي عملية تافية لا تحتاج إلى أي عمل لماذا؟ لأن كل مصفوفة في مكانها ومفروزة in place وبالتالي ليس لدينا حاجة لأن نقوم بأي عمل إضافي لجمع الحلول لا يوجد عمل إضافي لا يوجد حاجة لأي عمل إضافي لعملية جمع الحلول جميع المصفوفة أصبحت الآن مفروزة دعونا نرى السودوكول الخاص بهذه الخوارزمية إذن قبل أن نرى السودوكول الخاص بهذه الخوارزمية دعونا نقوم بإستراضها بشكل رسومي لدينا الآن هذه المصفوفة تم تقسيمها بشكل من الأشكال طريقة الآن سنقوم بإستراضة كيف يتم التقسيم بحيث أن هذه المصفوفة جميع العناصر التي فيها أكبر تماماً أو مساوية مساوية أو أكبر تمام العناصر الموجودة هنا.
فأصبح لدينا مسألتين. هذا الجزء وهذا الجزء. نقوم بتطبيق نفس العملية على هذا الجزء.
نقوم بتقسيمها بطريقة معينة. مثلاً قمنا بتقسيمها هنا. فأصبح لدينا هذا الجزء أول فيه جميع العناصر الأصغر تماماً من الجزء الثاني.
وكذلك هذه نقسمها لقسمية. مثلاً نفرض أن هذا قسم وهذا قسم. إذن عملية تقسيم الأولى هنا. بعد بعدها قمنا بعملية التقسيم الأولى أيضا كل جزء من هذه الأجزاء أو هذا الجزء تم تقسيم المصفوفة إلى جزءين هذا الجزء الأول وهذا الجزء الثاني هذا الجزء تم تقسيمه إلى جزءين هذا الجزء الأول وهذا الجزء الثاني هذا الجزء تم تقسيمه إلى جزءين جزء أول وجزء الثاني وهكذا نستمر في عملية التقسيم حتى نصل إلى حجم مصفوفة صغير كفاية لأنه قمنا بفرزه بشكل مباشر دون استخدامه مسلوب الـ Quick Sort وهذا الجزء عنده بعملية الاستدعاء العودي نسميه بالـ Base Case بمعنى نستمر في عملية الاستدعاء العودي لحل المسألة بنفس الاسلوب حتى نصل إلى حجم مصفوفة يكون صغير نسبيا بحيث نقوم من التوقف عن عميلة الاستدعاء العودي طيب بالحالة العامة لتوصيف هذا سودو كود سنفترض بأن حجم مصوفة التي نتوقف عندها عن الاستدعاء العودي هنا ما تكون مصوفة مؤلفة من عنصر واحد ومصوفة من عنصر واحد هي مصوفة مفروزة غير بحاجة إليها ليست بحاجة إلى فرز طيب هذه إذن الفكرة العامة عملية هذه عملية الـ divide كل مرة نقوم بعملية تقسيم بكل جزء بجزء الأصغر وجزء الأناصر الأكبر جزء الأصغر وجزء الأناصر الأكبر طيب في عملية الـ combine لا نقوم بأي شيء لماذا؟ لأن كل جزء أصبح في مكانه الصحيح وبالتالي لسنا بحاجة لـ combine إذن عملية الـ combine في الـ quick sort هي عملية غير موجودة لأن العناصر تكون قد تم فرزها في مكانه الصحيح وليس من حاجة لقيام بأعمال زائد لعملية الكمبيوتر دعونا نرى الآن السودوكود الخاص بهذه المسألة طيب عفوا طيب طيب دعونا نرى سودا كود الخاص بهذه المسألة كما قلنا بأن عميلة الاستداع العودي مستمرة ما دام أننا نرى نصيب الـ base case متى تكون الـ base case حينما تكون لدينا مصوفة مكونة من عنصر واحد طيب لنفرض أن المصوفة التي لدينا الكلية التي نتعامل معها هي عبارة عن مصوفة A ونحن الآن نطبق هذه الخوارزمية من العنصر صاحب الـ index P إلى العنصر صاحب الـ index R إلى العنصر صاحب الـ index R طيب وقمنا بتطبيق الـ Quick Sort عليها حتى نقوم بتطبيق الـ Quick Sort عليها يجب أن نكون في حالة الـ Base Case ماذا تكون حالة الـ Base Case؟ هنا تكون الـ P مساوية إلى R بمعنى أن المصففة مألفة من عنصر واحد ما هي الحالة أو General Case التي نقوم بها بعملية الاستداع العودي؟ هنا تكون الـ P ليست مساوية إلى R وبالتالي P أصغر من R لذلك لدينا هنا بدل أن نكتب إذا كانت الـ P مساوية إلى R لدينا Base Case وإلا نقوم بالعمل بالتنفيذ العودي نكتب هنا if p أصغر من r نقوم بالتنفيذ وإلا لنقوم بأي شيء دون أن نقوم بكتابتها هنا إذا كانت p أصغر من r أي أن المصفوفة أكثر من عنصر واحد ماذا نفعل؟ نقوم بعملية الـ divide أولا كيف سنقوم بعملية الـ divide؟ سنتعامل مع الـ divide بأنها صندوق أسود ما هي الآلية التي على أساسها نمر على هذه العناصر ثم نقوم بتقسيمها سنقوم بإدراجها ضمن الإجرائية أو ضمن الطريقة اذا نقوم بتمرير المصفوفة الكلية نقوم بتمرير بداية العنصر الاندكس صاحب الاندكس الاول في المصفوفة التي نرغب بعملية تطبيق العملية التجزئة عليها او تقسيمها الى جزئين والاندكس الاخير في هذا الجزء التي سنقوم بتقسيمها اذا ال بي هو بداية المصفوفة والار هي نهاية المصفوفة التي سنقوم بعملية تقسيمها او تجزئتها طيب هذا البرتشن بعد ان يقوم بعملية التجزئة سيقوم بتجزئة هذه المصفوفة الى جزئين جزئين. اخر اندكس في الجزء الاول هو كيو.
وبالتالي سيعيد لنا الكيو. اذا الكيو سيشير الى اندكس اخر عنصر في المصفوفة الاولى. طيب بعد ذلك سنقوم بعمل استداع العودي للكويكسورت من بي الى كيو.
ثم عمي استداع العودي لكويكسورت من الكيو زايد واحد وحتى الار. اذا هذا هو السودو كود بشكل واضح وبسيط الذي يظهر لنا عملية. اذا كل الفكرة الرئيسية الخاصة بالكويكسورت تعتمد.
كيف سنقوم بتطبيق الـ Partition كيف سنقوم بتطبيق عملية التجزئة ما هي العلاقة العودية لهذه العملية؟ طبعاً العلاقة العودية تختلف عن العلاقة العودية العامة الخاصة بال Default and Conquer وهي أنه لمعرفة التحقيق زمن T زائد الـ N سيتضمن ذلك الجهد المطبق في عملية التجزئة وهذا نسميه FN بعد عملية التجزئة سيكون لدينا جزءين الجزء الأول سيكون طوله مثلاً مثلاً Q والجزء الثاني سيكون طوله N-Q وبالتالي لدينا TN لحالها أو TQ لحالها ثم لدينا زائد TN-Q أيضاً لوحدها ضمن علاقة العودية الكلية هذه هي الـ Quick Sort في البداية كيف سيتم استدعائها؟ سيتم استدعائها في البداية بأن نكتب Quick Sort التالي Quick Sort ونقوم باستدعائها لنفس المصفوفة A ولكن Index البداية سيكون 1 و Index النهاية سيكون عبارة عن N إذا اخترضنا طبعا هذا Sudo Code أن المصفوفة تبدأ من 1 إذا من 1 وحتى الـ N ثم بعد ذلك تباعا حينما نقوم بإعادة المصفوفة سنقوم بالتقسيم مثلا عند العنصر 10 سيكون لدينا عملية استدعاء لـ Quick Sort لـ A من 1 حتى 10 و Quick Sort لـ A من 11 حتى الـ N إذن عملية التقسيم تتتالى وضمن كل وكاننا في حالة جديدة من المسألة يتم استدعاء بشكل عودي. طيب. دعونا الان آآ ننتقل الى التابع المهم او عفوا اطلع الاجرائية المهمة ضمن هذه الخوارزمية وهي كيف سنقوم بعملية كيف سنقوم بعملية التقسيم بهذه المصفوفة الى جزئين.
النقطة الرئيسية هنا ان نختار القيمة التي على اساسها سيتم عملية التقسيم. القيمة التي عساسها سيتم التقسيم. وعملية التقسيم التي سيتم على اساسها. او القيمة نسمي العنصر نقوم بانتقاء عنصر من المصفوفة.
هذا العنصر نسميه عنصر تمام? عنصر او المحور. اذا سنختار عنصر او محور.
هذا المحور سيكون هو احد عناصر هذه المصفوفة. نأخذ القيمة الموجودة فيه وعلى اساس نقوم بعملية تقسيم. فمثلا لنفرض انه قمنا باختيار اول عنصر لان يكون ماذا يعني? اي ان القيمة المخزنة وهذا العنصر هي القيمة التي على أساسها سنقوم بعملية التقسيم وإذا اخترنا هذا العنصر لأن يكون هو البيفوت ستكون القيمة الموجودة ضمن هذا العنصر هي القيمة التي على أساسها يزداد التقسيم يعني مثلا كانت القيمة المخزنة هنا خمسة ماذا يعني ذلك؟ يعني ذلك أننا سنقوم بعملية التجزئة كالتالي إلى جزئين جميع العناصر التي قيمها أصغر أو تساوي الخمسة ستكون موجودة هنا وجميع العناصر التي قيمها أكبر أو تساوي الخمسة ستكون موجودة هنا طيب الآن يمكن أن يأتي سؤال لماذا وضعنا هنا أصغر ويساوي وهنا أكبر أو يساوي طيب كيف يكون يساوي موجود في هذا الجزء وهذا الجزء لا مشكلة الفكرة هي يمكن أن يكون لدينا أكثر من خمسة في هذه أكثر من عنصر خمسة ضمن هذه المصوفة وبالتالي يمكن أن يكون بعض الخمسة بعض هذا العناصر هنا وبعض هذه العناصر هنا لا مشكلة لأنه بعد عملية الفرز النهائية ستتجمع هذه العناصر على حدود هاتين الجزئين ولكن الفكرة بأن جميع العناصر الموجودة لدينا هنا قيمها أصغر تماما أو مساوية للعناصر وهذا محقق ضمن هذا الشرط بأن تكون العناصر التي هنا أصغر أو تساوي الخمسة وهنا أكبر أو تساوي الخمسة إذن دعونا نعود عملية التجزئة ستبتدأ بالفكرة الأولى ما هي الفكرة الأولى أن نختار عنصر البيفوت ضمن المصفوفة وعلى أساسه يتم عملية التقسيم بعد أن يتم اختبارها عنصر البفل ضمن المصفوفة سنقوم بعملية المرور على جميع العناصر ضمن هذه المصفوفة.
سنقوم بعملية المرور على جميع العناصر ضمن هذه المصفوفة. من اليسار الى اليمين. ومن اليمين الى اليسار. ونقوم بعملية تبديلات ضمن المصفوفة لتحقيق هذه النتيجة. لتحقيق هذه النتيجة.
طيب دعونا نرى السلايد التالي يوضح الفكرة. طيب. طيب.
لدينا كما قلنا هذه المصفوفة المطلوب عملية تجزئة. هذه المصفوفة الى مصفوفتين. المطلوب تجزئة هذه المصفوفة الى مصفوفتين. طيب. سنقوم بعملية بناء هذه المصفوفة بشكل تدريجي.
بحيث نقوم بناء المصفوفة اليسارية تدريجيا وبناء المصفوفة اليمينية تدريجيا. ولكن نقطة البداية هو ان نختار عنصر الذي سنقوم على اساسي بعملية التقسيم. طيب سنقوم طبعا وجد لدينا لديها نسخ كثيرة. يمكن ان نختار عنصر بان يكون العنصر الاول.
يمكن يكون الاخير. يمكن ان يكون اي عنصر في المنتصف. طيب لدينا استراتيجيات كثيرة يمكن ان نتبعها نتبعها في سنقوم نحن بالاعتماد على على طريقة اختيار عنصر ليكون هو اول عنصر ضمن المصفوفة التي نرغب بعملية التجزئة لها.
طيب في مثل حالتنا هذا العنصر الاول هو هو العنصر الاول وبالتالي قيمته قيمة المحور الذي سنقوم بالتقسيم على اساسه هو الخمسة. اذا هو و X مساويا إلى الخمسة. طيب هذه كنقطة أولى.
كنقطة ثانية سنقوم بعملية البناء آآ المصفوفة اليمينية واليسارية بشكل تدريجي. كيف سيتم ذلك؟ سنستخدم مت غيري فارسي. المتغير الأول اليساري I.
والمتغير اليميني J. طيب. الآي ماذا سيفعل؟ سيمر على العناصر ويقوم ببناء مصفوفته اليسارية.
والجي سيقوم بالمرور من اليمين إلى اليسار. وسيقوم ببناء المصفوفة اليمينية طيب قبل البداية سنفترض بأن الجي الآن يشير إلى العنصر الذي ضمن المصفوفة اليمينية والآخر سيشير إلى العنصر الذي هو ضمن المصفوفة اليسارية وكوننا لم نبدأ بعد سنجعل الجي يشير إلى خارج المصفوفة معتبرين بأن ما خارج المصفوفة هو ضمن المصفوفة والآي سيشير إلى ما خارج المصفوفة أيضا ولكن نحن قلنا ولكن نحن قلنا بأن عملية التجزئة ستكون تبعاً للبيفوت والبيفوت هو في حالتنا أول عنصر وبالتالي نقبل بأن يكون الآي ضمن يشير إلى أول عنصر بحيث أن هذا العنصر سنضمن أنه موجود ضمن المصفوفة اليسارية حينما تبدأ العملية ما الذي سيحدث؟ سنبدأ مع الجزء اليساري ماذا سيفعل الجزء اليساري؟ هذا الآي كخطوة أولى بالانتقال خطوة إلى الأمام ويقوم بفحص العنصر إذا كان هذا العنصر مطبق لشرط أن هذا العنصر قيمته أصغر تماما من البيفوت يكون هذا العنصر ضمن المصفوفة وبالتالي يقوم بالانتقال إلى العنصر التالي كذلك يفحص مرة أخرى إذا كان هذا العنصر مطبق للشرط بأنه أصغر تماما من العنصر البيفوت يقوم باعتماده كعنصر ضمن المصفوفة وينتقل إلى العنصر في حال وجد أن هذا العنصر لا ينتمي لمصفوفته أي أن قيمته أكبر أو تساوي أكبر أو تساوي البيفوت ماذا يفعل؟ يتوقف عنده لأن هذا العنصر غير مرغوب به في جزئه بنفس الطريقة الجي الجي سيبتدأ مفترضا بأنه يقف عند عنصر ضمن مصفوفته وهو بالأصل خارج حدود المصفوفة وبالتالي هذا الافتراض ابتداءا مقبول بعد ذلك أول خطوة سيقوم بزيادة قيمته بمقدار واحد يصبح عند هذا العنصر هذا العنصر قيمته أكبر تماما أكبر تماما من فإذا كان كذلك ينتقل العنصر التالي. يفحص مرة أخرى. هل هذا العنصر قيمته أكبر تماما وبالتالي هو جزء من مصفوفته. فإذا كان تمام يقوم بانتقال عنصر التالي.
يبقى بذلك حتى يصل إلى عنصر قيمته ليست أكبر تماما من البفوت وبالتالي لا ينتمي لمصفوفته. طيب هنا هذا يفحص أن يكون أكبر تماما من وهذا يفحص أن يكون أصغر تماما من بحيث أن كل واحد منهم لا يرغب أن في حالة المساواة مع البيفوت لا يرغب بهذا العنصر وبالتالي يسعى إلى أرساله إلى الطرف الآخر طيب ماذا يحدث هنا؟ بعد أن يتوقف هذا الآي عند عنصر قيمته أكبر تماما من البيفوت وعندما يصل هذا الجي إلى عنصر قيمته أصغر تماما من البيفوت يتوقف كل من العنصري الجي والآي هنا ويقوم كل منهما بمساعدة الآخر بعملية تبديل هذا يعطيه العنصر الذي لديه وهذا يعطيه العنصر الذي لديه عملية التبديل طبعا طبعا بحاجة إلى متغير وسيط تيمب يقوم كل واحد منهم بإرسال القيمة مثلا نسخ القيمة التي هنا إلى التيمب ثم نقوم بنسخ هذه القيمة إلى الموقع الجي ثم يتم نسخ الأنصر في التيمب إلى هذا الموقع بنهاية عملية التبادل نضمن بأن كل من الآي والجي تقف الآن على عنصر مقبول لهم نبدأ باللوب أو الدورة الثانية ينطلق الآي مرة أخرى يزيد قيمته بمقدار واحد ويفحص إن كان عنصر التالي وهكذا نستمر في في هذه العملية حتى يصل حتى يتم في نقطة من النقاط حتى نصل في نقطة من النقاط يقوم الـ بالوصول الى نقطة. والـ يصل الى النقطة التي او الموقع السابق يعني انه في نهاية المطاف سيصبح الـ هنا والـ هنا. وبالتالي نعلم بان الـ دخل في الجزء الخاص لمصفوفة الجيب المصوفة اليمينية والـ والجي يقف.
على اخر عنصر في المصفوفة اليسارية. وبالتالي عند هذه النقطة تنتهي التنفيذ ونقوم بتجزئة المصفوفة عند العنصر جئ اذا الجاي سيشير او الجاي سيشير الى الموقع الذي على اساسه سيتم عملية التقسيم. الذي سيتم عملية التقسيم. طيب. هذا شرح عام.
الان في التنفيذ ستكون الامور اوضح واكثر وضوحا. طيب. طيب دعونا نقوم باستراضيها هنا الآن في البداية تم اختيار البيفوت بأن يكون هو أول عنصر وبالتالي بيفوت X مساويا إلى 5 إذن الخمسة هو العنصر الذي سيتم عملية التقسيم على أساسي الآي سينطلق من هذا الموقع طبعا الخمسة سيعتبرها جزءا من مصفوفتي وبالتالي هذا العنصر الذي يقف عليه حاليا هو ضمن مصفوفتي والجي سيبتدأ من خارج المصفوفة معتبرا أن هذا الموقع هو ضمن مصفوفته طيب بعد ذلك ستبدأ عملية التنفيذ ستبدأ عملية التنفيذ طيب ممكن نبدأ من الآي باتجاه اليسار أو من الجي باتجاه اليمين أو من الجي باتجاه اليسار دعونا نأخذ في هذا المثال بدأت الجي تتقدم وصلت أول خطوة لها إلى السبعة هل السبعة أكبر من خمسة؟ نعم إذن سبعة من مصفوفة اليمينية ننتقل للموقع التالي ما هو الموقع التالي؟ ثلاثة هل ثلاثة أكبر من خمسة؟ جواب لا إذن هذا العنصر غير مرغوب به وليس جزءا من مصفوفتنا سنقوم بترحيله إلى الطابق الطرف الاخر. طيب انتهت مسيرة الجهة هنا.
نبدأ الان بتحريك الاي. الاي كان واقفا عند الخمسة. والخمسة جزء مصوفته. وبالتالي اول خطوة يقوم بها الاي حينما يأتي دوره يقوم بزيادة اه زيادة قيمته بمقدار واحد يصل للثلاثة. هل الثلاثة اصغر من خمسة?
نعم. ضمن مصوفته ينتقل الى خطوة الامام. هل اتنين ضمن مصوفته? نعم. طيب انتقل خطوة الامام.
هل الستة اصغر من خمسة? لا اكبر وبالتالي يقف عند هذا الموقع مشيرا الى ان هذا عنصر غير مرغوب به ويسعد عملية تبادل مع الطرف الآخر. طيب عند هذه النقطة تتم عملية تبادل.
الثلاثة تأتي لهنا. والستة تأتي لهنا. في نهاية عملية تبادل يكون الآي يقف على عنصر مقبول بالنسبة له لمصففته. والجي يقف على عنصر مقبول بالنسبة له وهو الستة.
طيب. حينما يبتدأ دور الجي مرة اخرى. ماذا سيفعل?
سيبتدأ اول خطوة بزيادة قيمته بمقدار واحد. ويتصل الى الآي. الى هذه الاذاء الموقع. هل الواحد اصغر?
أكبر من 5 الجواب لا إذن هذا عنصر غير مرغوب به يتوقف عنده طيب بنفس الطريقة تبتدأ الآي بالانتقال حينما تنتقل الآي الثلاثة أول خطوة تقوم بزيادة قيمتها بمقدار 1 تصل إلى الأربعة هل الأربعة أصغر من نعم تقوم بزيادة قيمتها بمقدار 1 فتصل إلى الواحد هل الواحد أصغر من نعم تقوم بزيادة قيمتها بمقدار 1 تصل الآي إلى هنا في اللحظة التي يتقاطع فيها كل من الجي والآي نعرف نعلم أو يعبر كل منهما الآخر نعلم بأن عملية التجزئة قد انتهت وأن كل منهما يقف على عتبة طرف المصفوفة الطرف الآخر فالآية تكون في أقصى يسار المصفوفة اليمينية والجي يكون بأقصى يمين المصفوفة اليسارية طيب عند هذه النقطة يتم التقسيم والقيمة المعادة لالكيو هي ستكون قيمة الجي إذن هذه الفكرة الخاصة بعملية التجزئة دعونا نستخدم السودو كود الخاص بها إذن في البداية نقوم بتعريف متغيرين المتغير الأول وهو الآي والمتغير الثاني وهو الجي الآي سنقوم بإسناد القيمة البي له الموقع الأول ضمن المصفوفة والجي سنقوم بإسناد قيمة الار زائدة الواحد الأنصر التالي ما بعد المصفوفة لماذا؟ لأننا نقولنا لاحقا حينما تبدأ الجي بالحركة أول خطوة تقوم بها هي إنقاص قيمتها بمقدار واحد وحينما تبدأ الآي بالحركة هو القيمة قيمة أول خطوة تقوم بها هو زيادة قيمتها بمقدار واحد. طيب الآن يعني السؤال لماذا قمنا باختيارها هنا في الموقع البداي ولم نختارها أيضا مثل الجي ما قبل المصفوفة كون أول قيمة ستقوم باختيارها هي القيمة التالية أو ستقوم بزيادة قيمتها بمقدار واحد. طيب دهون نجيب على هذا السؤال ثم نكمل في السودا كود.
سأعطيكم مثالا معاكسا. تخيلوا بأن القيمة التي قمنا باختيارها هي طبعا أول قيمة وكانت خالصة. كانت هذه القيمة هي عبارة عن خمسة.
طيب. وكانت القيم التالية هي كلها ستة مثلا سبعة ثمانية ناش مثلا او اثنين وعشرين مثلا ثلاثة. طيب. الان في حال بدأت هذه الجهة بالحركة ستنتقل اه الى تنقص قيمتها بمقدار واحد. الجهة محقق التلاتين تحقق الشرط نعم.
ناش تحقق نعم. تمانية تحقق اكبر من خمسة نعم. سبعة اكبر نعم. ستة اكبر نعم.
ستة ستة. الجي بخطوة واحدة الى هنا. بعدة خطوات حتى تصل الى هنا. طيب الان الاي حينما تبتدأ بالحركة. اذا كانت الاي قيمتها هنا.
ستقوم بزيادة قيمتها بمقدار واحد تصل الى هنا. هذه القيمة ليست اصغر تماما من من خمسة. وبالتالي ستقف الاي هنا. طيب اول خطوة سيتم عملية التبادل بين الطرفين.
الاي ستسلم القيمة التي تشير لها الى الجي والجي ستسلم القيمة التي تشير لها الى الاي. طيب ماذا تفعل? سيتم التبادل في نفس الموقف.
بعدها ما الذي سيحدث الجي ستقوم بأول خطوة لها ستقوم بالانتقال خطوة إلى الأمام وحتى تصل إلى خارج حدود المصفوفة وهذا أمر غير مرغوب به لماذا؟ لأنهم في هذه الحالة حينما يشير كل من الطرفين إلى نفس العنصر تكون الآي ليست أكبر الآي لا يكون الشرط الذي يؤدي إلى توقف التنفيذ وهو حينما تصبح الآي قيمتها أكبر من قيمة الجي وهذا الأمر غير محقق في هذه الحالة لذلك لتجاوز هذه الحالة يجب أن نسمح أو نسمح نحن في البداية بأن تكون هذه القيمة مع الآي طيب دعونا نعيد نفس المثال لو كانت الآي ابتدأت من هذا الموقع دعونا نقوم بأرض نفس المثال لو أن الآي ابتدأت من هنا والجي ابتدأت من هنا طيب الجي ستستمر في حركته حتى تصل إلى هنا الآي أول ما تبدأ بحركتها إلى أين ستصل ستنتقل إلى العنصر التالي طيب هنا أصبح الشرط غير محقق وبالتالي أو شرط التوقف أصبح محققاً وهو أن الآية أصبحت أكبر من J وبالتالي سيتم الإيقاف وتكون Q هي عبارة عن J هي عبارة عن القيمة التي تشير لها J وسيتم فصل المصفوفة بهذا الشكل هذا جزء المصفوفة الأولى وهذا جزء المصفوفة اليمينية طيب إذن بذلك نكون قد أوضحنا لماذا قمنا بحساب هذا العنصر أو إدراجه مع العناصر المضمنة في المصفوفة اليسارية حتى نتجاوز هذه الحالة التي قمنا بها قمت بذكرها الآن الآن نعود في البداية نجعل I تشير إلى أول عنصر وهو البيفوت والجي تشير إلى خارج حدود المصفوفة كما التالي جي سينسد لها قيمة R زائد 1 والI سينسد لها قيمة البي أو القيمة المخزنة في البي بعد ذلك أو عفوا ليس القيمة المخزنة وإنما الاندكس بي سيتم إسناده إلى الـ I كذلك سيتم اختيار البيفوت ونضع في قيمة القيمة التي يشير لها اول عنصر وهي الخمسة. اذا هو الخمسة الذي سيتم على اساسه عملية التجزئة. سندخل في حلقة سندخل في حلقة بهذا الشكل. طيب من هذا النقطة الى هذه النقطة. اذا الكلية.
طيب هذه الكلية سنقوم باعطاء اي مجال لتتحرك حتى تصل الى عنصر غير مرغوب به. ونجعل الجي ايضا تتحرك بحلقة خاصة بها. تتحرك بحلقة Y-Loop خاصة بها حتى تصل للعنصر الغير المرغوب به طيب الآي في البداية أول ما تتحرك تزيد قيمتها بمقدار واحد فتكون هنا تصبح هنا ثم بعد ذلك تدخل في حلقة Y-Loop ما دام أن الآي الأي عند الآي أكبر من X طبعا هنا لدينا خطأ بحاجة لتعديل هو حينما تكون الآي أكبر تماما من X ماذا يحدث؟ تقوم بمدام أن الآي أكبر عفوا هذا بالنسبة لي الآي ما دام أن الآي أكبر القيمة التي لدينا اصغر تماما من الاكس استمر في التنفيذ. هنا ايضا هذا ساقوم بتعديله.
بدا من اصغر تماما من الاكس قم بالانتقال الى الخطوة التالية. قم بالتنفيذ. ماذا سيقوم? سيقوم بزيادة الاكس بمقدار واحد. ينتقل الموقع التالي.
وطبعا في كل مرة يفحص. هل القيمة التي وصلتها هي الحد المصفوفة هو العار. فاذا كان الحد يقوم بقطع التنفيذ وعمل لهذه الوايلو.
وعمل بريك لهذه الواي لوب طيب هذه بالنسبة للجزء الخاص بالجي أيضا سيتم تفعيله سيتم في البداية انقاص الجي بمقدار واحد دائما أول خطوة انقاص الجي بمقدار واحد مادام أن القيمة التي يشير لها الآن الجي قيمتها أكبر من X ماذا يفعل؟ يقوم بالتنفيذ يقوم بانقاص الجي بمقدار واحد ثم يفحص هل وصلنا إلى حدود المصفوفة أو لا فإذا وصل إلى حدود المصفوفة يقوم بعمل بريك من الواي لوب طيب بعد أن يتم تم تمشي هذه الـ I مسافة أو عدد من المواقع التي تحقق شرطها وتصل إلى موقع لا يحقق شرط خاص بها تتوقف وتمشي الـ J عدد من المواقع وتتوقف عند الموقع الذي يحوي عنصرا لا يحقق الشرط الخاص بمصفوفتها بعدها نصل إلى فحص بعد أن نقوم في فحص الـ Y-Loop الأولى والـ Y-Loop الثانية نقوم بـ I تمضي مسافة والـ J تمضي مسافة التي تحقق شرطها بفحص الشرط هل ما زالت ال I أو هل ال I أصبحت قيمتها أكبر من J فإذا أصبحت قيمة ال I أكبر من J نقوم بعمال break ونخرج من الحلقة الكلية ونخرج من الحلقة الكلية إذن هذه ال while الأولى وهذه ال while الثانية وهذه ال while ال كلية طيب في حال لم يتم تنفيذ هذا الشرط أي أن ال I ما زالت أصغر من J ما الذي يحدث لدينا نقوم بعملية تبادل إذن الآن الموقع التالي الحالي الذي يشير يشير له الآي يرغب بالتبادل مع الموقع الذي يشير له الجي يتم تبادل عناصر في كلا الموقعين وندخل في حلقة وايلوب جديدة نسمح للآي بالحركة وتتوقف حينما يصبح الشرط محققا غير محقق والجي تمشي أيضا مسافة وتتوقف حينما يصبح الشرط غير محقق ثم نفحص هل الآي ما زالت أصغر من جي فإذا كانت أصبحت الآي أكبر من جي نقوم بعمل بريك وإلا نقوم بعملية التبادل وندخل في دورة جديدة فايد بعد أن نصل إلى مرحلة يكون الآي قيمتها أكبر من ج ويحصل بريك من الواي لوب ما الذي نفعله؟ نكون قد انتهينا من عملية التجزئة ويبقى لنا خطوة واحدة قبل أن نعيد الموضع الذي تم التقسيم عنده نقوم بعملية تبديل للعنصر الموجود في بداية المصفوفة مع الموقع الذي تم التوقف عنده إذا اعتبرنا أن هذه المصفوفة الأولى وهذه أصبحت المصفوفة الثانية نقوم بتبديلها هذا العنصر موقعه مع العنصر المخزن هنا لماذا حتى في الدورة التالية لا يتم استخدام نفس العنصر كبيفوت مرارا وتكرارا وبالتالي نقوم بنقله إلى هنا هذه إذن التعليمة exchange القيمة المخزنة في ال P مع القيمة المخزنة في الجي طيب كخطوة أخيرة هذه الإجراءية ال partition ستعيد الموضع الذي تم على أساسي أو عنده عملية التقسيم بحيث أصبح لدينا من P إلى جي ومن جي زي إذا واحد إلى R فنقوم بإعادة قيمة الجي طيب هذه إذن الـ partition الـ pseudo code الخاص بالـ partition سنقوم أيضا باستعراض هذا الكود ولكن بلغة الجافا بعد قليل