خوارزميات الفرز والترتيب PDF

‫الجامعة الوطنية الخاصة‬ ‫كلية الهندسة‬ ‫قسم هندسة الحاسوب‪-‬االتصاالت‬ ‫‪ ‬المقرر‪ :‬مبادئ الخوارزميات وبنى المعطيات‬ ‫المحاضرة ‪ :‬الثالثة‬ ‫‪Dr. Mohammed AL-Mohammed‬‬ ‫‪1‬‬  ‫‪Chapter 3‬‬ ‫خوارزميات الفرز والترتيب‬ ‫‪Sort...

‫الجامعة الوطنية الخاصة‬ ‫كلية الهندسة‬ ‫قسم هندسة الحاسوب‪-‬االتصاالت‬ ‫‪ ‬المقرر‪ :‬مبادئ الخوارزميات وبنى المعطيات‬ ‫المحاضرة ‪ :‬الثالثة‬ ‫‪Dr. Mohammed AL-Mohammed‬‬ ‫‪1‬‬  ‫‪Chapter 3‬‬ ‫خوارزميات الفرز والترتيب‬ ‫‪Sorting Algorithms‬‬ ‫الجزء ‪- 1-‬‬  ‫المقدمة‬ ‫‪ ‬خوارزميات الترتيب هي خوارزميات تمكن من تنظيم مجموعة عناصر حسب ترتيب‬ ‫محدد(تصاعدي ‪ -‬تنازلي) ‪ ،‬العناصر المراد ترتيبها توجد في مجموعة مزودة بعالقة‬ ‫ترتيب معينة‪.‬‬ ‫‪ ‬تصنيف خوارزميات الترتيب مهم جدا‪ ،‬النه يمكن من اختيار نوع الخوارزمية األكثر‬ ‫مناسبة للشكل المعالج‪ ،‬مع األخذ بعين االعتبار السلبيات الموجودة في الخوارزمية‬ ‫‪ ‬أي أن الترتيب هو عبارة عن عملية ترتيب مجموعة من العناصر البيانية وفق قيمة‬ ‫معينة تسمى حقل أو وفق حقول تسمى المفتاح إما بصورة تصاعدية أو تنازلية ‪.‬‬ ‫‪ ‬وبالتالي فالغرض من الترتيب هو‪:‬‬ ‫‪-‬زيادة كفاءة الخوارزمية " البحث عن عناصرها"‬ ‫‪ -‬تبسيط معالجة الملفات‬ ‫‪3-3‬‬ ‫‪ -‬حل مشكلة تشابه القيود‬  ‫أنواع الترتيب ‪Types of Sorting‬‬ ‫‪– 1‬الترتيب الداخلي (‪)Internal Sort‬‬ ‫‪– 2‬الترتيب الخارجي (‪)External Sort‬‬ ‫‪ ‬الترتيب الداخلي‪ :‬يحدث داخل الذاكرة بحيث يكون حجم البيانات مناسب وليس كبير‬ ‫ويشمل‪:‬‬ ‫‪.1‬ترتيب االختيار (‪)Selection Sort‬‬ ‫‪.2‬الترتيب الفقاعي (‪)Bubble Sort‬‬ ‫‪.3‬ترتيب الحشر أو االضافة (‪)Insertion Sort‬‬ ‫‪.4‬ترتيب شيل (‪)Shell sort‬‬ ‫‪3-4‬‬  ‫‪.5‬الترتيب السريع (َ‪)Quick Sort‬‬ ‫‪.6‬ترتيب االساس (‪)Radix Sort‬‬ ‫‪.7‬ترتيب المؤشرات (‪)pointers Sort‬‬ ‫‪.8‬الترتيب الشجري(‪)Tree Sort‬‬ ‫‪ ‬الترتيب الخارجي ‪ :‬وهو الترتيب الذي يحدث خارج الذاكرة في أواسط الخزن الثانوي‬ ‫عندما يكون حجم البيانات كبير بحيث يتعذراستيعابها في الذاكرة اثناء عملية الترتيب‬ ‫ويشمل‪:‬‬ ‫‪.1‬الترتيب بالدمج (‪)Merge Sort‬‬ ‫‪.2‬الترتيب بالدمج المتوازن ذو المسارين (‪)Balanced two Merge Sort‬‬ ‫‪.3‬الترتيب بالدمج باستخدام طريقة فرق تسد(‪)Divided & conquer Merge Sort‬‬ ‫‪3-5‬‬  ‫المقدمة‪:‬‬ ‫من خالل دراستك لخوارزميات الترتيب المختلفة ستجد أن مفهوم ‪ Swap‬أو تبادل‬ ‫ُمحتوى متغيرين يتكرر باستمرار ‪..‬فأغلب خوارزميات الترتيب (إن لم تكن كلها !)‬ ‫تعتمد في مرحلة ما على تبديل محتوى خانتين لوضعهما في الترتيب الصحيح‪ ،‬لذا‬ ‫سنوضح كيفية تبديل محتوى متغيرين قبل أن نبدأ بكتابة الخوارزمية بلغة السي‪.++‬‬ ‫سنتناول فيما يلي ‪ 4‬طرق لعمل ‪ Swap‬لكل منها إيجابيات كما لها سلبيات أيضا‪.‬‬ ‫الطريقة األولى (و هي األكثر شهرة) تكمن في استخدام وسيط مساعد يُساعدنا على‬ ‫تبديل محتوى المتغيرين‪ ،‬فنضع قيمة المتغير األول في الوسيط ثم نضع قيمة المتغير‬ ‫الثاني في المتغير األول ثم نضع قيمة الوسيط في المتغير الثاني‪ ،‬و بهذا نكون قد بادلنا‬ ‫بين قيمة المتغير األول و الثاني‪.‬لنفرض أن ‪ x=5‬و ‪: y=-1‬‬ ‫‪t = x // (t = 5 ) , x = y‬‬ ‫)‪//(x = -1‬‬ ‫‪y=t‬‬ ‫)‪// (y = 5‬‬ ‫‪3-6‬‬ ‫في النهاية تكون ‪ x=-1‬و ‪ y=5‬و بالتالي تم تبديل قيمتي ‪ x‬و ‪y‬‬ ‫هذه الطريقة بسيطة و تقليدية أيضا‪ ،‬إال أنها تأخذ مساحة أكثر من الذاكرة باإلعالن عن الوسيط‬ ‫الثالث‪.‬‬ ‫يمكننا عمل ‪Swap‬بدون حاجة إلى وسيط مساعد عن طريق إجراء بعض العمليات‬ ‫الحسابية البسيطة على المتغيرين‪.‬‬ ‫الطريقة الثانية (تصلح للمتغيرات العددية فقط) ‪:‬‬ ‫; ‪x=x+y ; y=x-y ; x=x-y‬‬ ‫الطريقة الثالثة (تصلح للمتغيرات العددية فقط و يجب أن تختلف قيمة ‪y‬عن الصفر) ‪:‬‬ ‫;‪x=x*y; y=x/y‬‬ ‫;‪x=x/y‬‬ ‫مالحظة ‪ :‬الطريقتان السابقتان يمكنهما أن يتسببا في حدوث ‪ Overflow‬إذا كانت قيمة‬ ‫‪3-7‬‬ ‫‪ x+y‬أو ‪ x*y‬أكبر من القيمة العظمى لنوع المتغيرين ‪x , y‬‬ ‫الطريقة رابعة ال تحتاج إلى وسيط مساعد و ال يمكن أيضا أن تكون سببا في حدوث ‪Overflow‬‬ ‫تعتمد هذه الطريقة على أحد الــ ‪) Bitwise‬مؤثرات الــ ‪ (Bit‬وهو المؤثر ‪ XOR‬اختصار‬ ‫لـــ )‪ )Exclusive OR‬و الذي يُرمز له بــ ^ ‪ ،‬هذا المؤثر يعطينا ‪ True‬إذا و فقط إذا كان‬ ‫المدخلين مختلفين‪ ،‬أما إذا كانا متشابهين فالنتيجة ستكون ‪ False‬و يعمل هذا المؤثر كالتالي ‪:‬‬ ‫كمثال على ذلك‬ ‫‪3-8‬‬  ‫سنقوم بتجربة هذه الطريقة على المتغيرين ‪ x‬و ‪ y‬حيث ‪ x = 15‬و ‪ ، y=7‬لذلك‬ ‫سنقوم بالخطوات الثالثة التالية ‪:‬‬ ‫‪x = x^y‬‬ ‫‪// x = 15 XOR 7 = 8‬‬ ‫‪y = y^x‬‬ ‫‪// y = 15 XOR 8 = 7‬‬ ‫‪x = y^x‬‬ ‫‪//‬‬ ‫‪x = 7 XOR 8 = 15‬‬ ‫‪ x‬و‪y‬‬ ‫و بهذا تم تبديل محتوى المتغيرين‬ ‫يمكننا اآلن كتابة دالة تبادل بين ُمحتوى ُمتغيرين باستخدام إحدى الطرق األربعة الموضحة‬ ‫أعاله‪ ،‬مع األخذ في االعتبار سلبيات كل طريقة‪.‬‬ ‫إذا أدرت التوسع أكثر في هذه الجزئية‪ ،‬فيمكنك البحث عن أفضل طريقة لتبديل محتوى‬ ‫متغيرين بحيث تحقق النقاط اآلتية في آن واحد ‪:‬‬ ‫ ال تحتاج إلى وسيط مساعد (المستوى ‪ :‬بسيط)‬ ‫ ال تسبب ‪( Overflow‬المستوى ‪ :‬صعب)‬ ‫ ال تضع أي شرط على قيم أو نوع المتغيرين (المستوى‪:‬أكثر صعوبة‪ ،‬إن لم يكن مستحيال !)‬ ‫‪3-9‬‬  ‫كتابة دالة تقوم بعملية التبديل ‪:‬‬ ‫بعد أن تطرقنا إلى الطرق األربعة التي يمكننا من خاللها تبديل محتوى متغيرين‪.‬سنقوم‬ ‫اآلن بكتابة دالة تُبادل بين محتوى خانتين من المصفوفة ‪ X‬باستخدام الطريقة األولى‬ ‫(ألنها األكثر شعبية ‪..‬رغم احتوائها على انتهاك صارخ لحقوق الــ ‪)Overflow ! :‬‬ ‫‪3-10‬‬ ‫حيث يبحث عن اصغر(أكبر) عنصر في المصفوفة و يقارنه مع اول عنصر في المصفوفة‪.‬‬ ‫مثال ‪:‬‬ ‫‪3-11‬‬  1. int maxSelect (int a[],int n) 2. { 3. int maxPos(0),currentPos(1); 4. while (currentPosa[maxPos]) 6. maxPos=currentPos; 7. currentPos++; 8. } 9. return maxPos; 10. } 11. void swapElements(int a[],int maxPos,int last); 12. void selectionSort(int a[ ],int n) 13. { 14. int last(n-1); 15. int maxPos; 16. while(last>0){ 17. maxPos=maxSelect(a,last+1); 18. swapElements(a,maxPos,last); 19. last --; 20. } 3-12 21. } 3-13  ‫التعقيد ‪ Big-O‬لهذه الخوارزمية‬ ‫‪Slide 3-14‬‬ Slide 3-15  ‫حيث يقارن اول عنصرين ثم يقارن‬ ‫العنصرين التاليين و يبدل بينهم و هكذا‪....‬‬ ‫‪3-16‬‬ ‫تقارن هذه الخوارزمية بين قيم الخانات المتجاورة‪ ،‬تبدأ بالمقارنة بين أول خانتين من‬ ‫المصفوفة‪ ،‬إذا كان محتوى الخانة األولى أكبر من محتوى الخانة الثانية سيتم تبادل‬ ‫محتوى الخانتين و هكذا مع بقية الخانات‪.‬عند انتهاء الدورة األولى ستكون الخوارزمية قد‬ ‫أنجزت ‪ n-1‬مقارنة و بهذا ستتم إزاحة أكبر عناصر المصفوفة إلى الخانة األخيرة‪.‬‬ ‫بقي اآلن ترتيب الــ ‪ n-1‬عنصر‪.‬و هكذا األمر مع بقية الدورات ‪...‬‬ ‫النتيجة ‪ :‬عملية الترتيب تـخـتلف عن عملية البحث في هذه النقطة‪ ،‬فالترتيب ال يقبل‬ ‫وجود عدة احتماالت في النتيجة‪ ،‬فعند تطبيق الخوارزمية سنحصل على مصفوفة مرتبة‬ ‫تصاعديا و بالتالي ال توجد احتماالت للمناقشة‪.‬‬ ‫اإليجابيات ‪ :‬الخوارزمية سهلة التصور و بسيطة المفهوم‪.‬‬ ‫السلبيات ‪ :‬بطيئة شيئا ما وغير عملية‪ ،‬خصوصا عند معالجة المصفوفات الضخمة‪.‬‬ ‫‪3-17‬‬  1. void swapElements(int a[],int b,int c); 2. void bubbleSortPhase(int a[],int last) 3. { 4. int pos; 5. for(pos=0;posa[pos+1]){ 7. swapElements(a,pos,pos+1); 8. } 9. } 10. void bubbleSort(int a[],int n) 11. { 12. int i; 13. for(i=n-1;i>0;i--) 14. bubbleSortPhase(a,i); 15. } 3-18  ‫التعقيد ‪ Big-O‬لهذه الخوارزمية‬ ‫‪3-19‬‬  ‫مثال‪:‬‬ ‫‪3-20‬‬