• الإعلانات

    • فيصل الحربي

      تسجيل عضوية جديدة في المنتدى   01/31/2016

      السلام عليكم ورحمة الله وبركاته  عزيزي العضو الجديد :  حاليا رسالة الإيميل لتأكيد صحة إيميلكم تذهب للبريد العشوائي ( جاري حل المشكلة )  فإذا لم تجد رسالة التحقق من إيميلكم في صندوق الوارد لديكم إتجه للبريد العشوائي ( JUNK)  وقم بتفعيل إشتراككم من هناك   

البحث في المنتدى

Showing results for tags 'Bubble Sort'.

  • البحث بالتاقات

    اكتب الكلمات المفتاحيه بينها علامه الفاصله
  • البحث بكاتب الموضوع

تم إيجاد 10 نتيجة

  1. السلام عليكم ورحمة الله وبركاته إنه لمن الممتع أن تكتب دوالك بنفسك .. ستتعلم الكثير وتكتسف الأخطاء وتتدرب على المفاهيم الأساسية .. ولكن عليك ان تعتاد رغم ذلك على استخدام الدوال الجاهزة التي قام عشرات المبرمجين بتطويرها لتصل الى المستوى المطلوب  .. وغالبا ستجدها أسرع وأفضل من أي دالة تكتبها بنفسك .. (إن كانت تحقق المطلوب ) سنتعامل اليوم مع دالة الترتيب السريع qsort وهي التي تعتبر أسرع طرق الترتيب .. الترتيب QuickSort والذي يأخذ( n*log(n عملية في الحالة المتوسطة .. لترتيب مصفوفة من n عنصراً .. ( هذه القيمة تسمى بالتعقيد الزمني Time Complexity وهي ليست عدد العمليات تماما  ) يجدر بك الاطلاع على خوارزمية الترتيب السريع لمعرفة كيفية عملها ... ولكن هذا غير ضروري الآن .. تحتاج إلى معرفة أولية بالمؤشرات والدوال لفهم جيد .. كما انه من المهم جدا المامك بعملية تحويل الانواع cast لنتعرف الآن على الدالة qsort تأخذ هذا الدالة أربع وسطاء هي بالترتيب : 1-  مؤشر من نوع void يشير الى أول عنصر في المصفوفة (أي إلى المصفوفة ) . 2- عدد صحيح يحدد عدد عناصر المصفوفة . 3- عدد صحيح يحدد حجم العنصر الواحد في المصفوفة . 4- مؤشر إلى دالة مقارنة عنصرين ... صفاتها :           1- تعيد عدداً صحيحاً يدل على ناتج مقارنة العنصرين الممررين كوسطاء           2- تأخذ وسيطين من نوع const void *  أي أنهما مؤشران ثابتان على العنصرين الذين ستتم مقارنتهما .   أهم ما عليك تحديده هو أن دالة المقارنة إذا أعادت 0 فهي تقول أن القيمتين متساويتين أما إذا أعادت أي عدد موجب فهذا يعني أن الوسيط الأول أكبر من الثاني وإن أعادت قيمة سالبة فالوسيط الثاني هو الأكبر   هذا كل ما تحتاجه لمعرفة استعمال الدالة ..   توقيع الدالة معقد بعض الشيء ولكن يمكننا تعديله قليلا لنقرأه كما يلي : void qsort(void * _Base,    int _NumOfElements, int _SizeOfElements,       int (* _FuncCompare)(const void *, const void *));(قمت باستبدال بعض الاسماء مثل size_t إلى int وحذف بعض المعرفات مثل__cdecl للتسهيل ) _______________________   لاستعمال الدالة .. يكفي تعريف دالة المقارنة فقط لا غير ثم يمكننا استعمال الدالة فورا .. مثال يوضح طريقة الاستعمال : نبدأ دوما مع دالة المقارنة .. حافظ على تعريف الدالة كما هو .. int compare(const void*a,const void*b){    int A=*((int*)a);    int B=*((int*)b);    if ( A < B )return -1;    else if(A==B)return 0;    else return 1;}يمكننا ان نجعل الترتيب تصاعديا أو تنازليا بتغيير الشروط ..  ويمكن جعل الدالة أعقد لتقوم بمقارنة عناصر من كائن مع عناصر كائن آخر بطريقة تحددها انت .. ليس هناك حدود لاستخدام الدالة طالما أنك تخافظ على القيم المعادة وتعريف الدالة كما هو .. وهذا برنامج يوضح استخدام الدالة .. بأبسط ما يمكن .. #include<cstdio>int main(){    int a[10]={8,5,7,1,2,47,6,9,2,3};    qsort ((void *)a, 10, sizeof(int), compare);    for(int i=0;i<10;i++)        printf("%i\n",a[i]);}لاحظ سهولة الاستخدام كما أن وجود مؤشرات من نوع void*يعني أن الدالة عامة الاستخدام ولا تقتصر على نوع واحد من المصفوفات .. المهم هنا هو الانتباه إلى القيام بتحويل الانواع المناسب عند تمرير الوسطاء وعند اختبار المقارنة .. كيف يمكنك اغناء المشاركة ... 1- يمكنك كتابة برنامج يوضح ترتيب مصفوفة من struct ما .. يحوي اسماً ورقما ويقوم بالترتيب حسب الاسماء وعند تشابه الاسم يرتب حيب الرقم 2- يمكنك كتابة مثال آخر على استخدام الدالة .. 3- يمكنك تقديم روابط تشرح qsort من مصادر أخرى .. بشكل أفضل 4- يمكنك كتابة موضوع عن دوال أخرى للترتيب أو البحث مثل bsearch  مثلاً كيف يمكنك الاساءة الى المشاركة .. 1-أن ترد بكلمة شكر فقط .. 2- أن تسأل عن أمر غير متعلق بالموضوع ..   أخيرا .. نسيت أن أذكر أن qsort موجودة في المكتبة cstdlib .. :) والسلام عليكم ورحمة الله وبركاته
  2. السلام عليكم ورحمة الله وبركاته ترتيب المشط خوارزمية ترتيب بسيطةً نسبياً , صممها في البداية Włodzimierz Dobosiewicz في عام 1980. ثم أعاد اكتشافها Stephen Lacey و Richard Box في عام 1991. وتعد تحسيناً لخوارزمية ترتيب الفقاعات. الخوارزمية الفكرة الأساسية هي إزالة السلاحف, أو القيم الصغيرة الفريبة من نهاية القائمة, فهي سبب رئيسي في بطء خوارزمية ترتيب الفقاعات . في حين لا تسبب الأرانب, القيم الكبيرة في بداية القائمة, أي مشكلة في ترتيب الفقاعات.   عند مقارنة أي عنصرين في ترتيب الفقاعات يكون بينهما فجوة (مسافة بين عنصرين) قيمتها 1. الفكرة الأساسية في ترتيب المشط هي : إمكانية جعل هذه الفجوة أكبر من 1. بكلام أكثر تخصصاً, تم تعديل الحلقة الداخلية في ترتيب الفقاعات, حيث تتم عملية الـتبديل الفعلية, بحيث تتناقص قيمة الفجوة بين العناصر التي تتم مقارنتها (خلال كل دورة للحقة الخارجية) بخطوات يحددها عامل الانكماش . يتم ذلك كما يلي: [ حجم الدخل\عامل الانكماش , حجم الدخل\عامل الانكماش^2, حجم الدخل\عامل الانكماش^3, ...., 1 ]. وذلك على عكس ترتيب الفقاعات, حيث تكون قيمة الفجوة ثابتة أي 1.   تبدأ قيمة الفجوة من حجم القائمة مقسوماً على عامل الانكماش (عادةً 1.3), ويتم ترتيب القائمة بهذه القيمة للفجوة (بعد تقريبها لأقرب عدد صحيح أصغر منها إن لزم الأمر) . ثم يتم تقسيم قيمة الفجوة على عامل الانكماش مرة أخرى ,ثم إعادة ترتيب المقائمة بقيمة الفجوة الجديدة , وهكذا يتم تكرار العملية حتى وصول قيمة الفجوة إلى 1. عند هذه المرحلة , تتابع خوارزمية ترتيب المشط بقيمة الفجوة 1 حتى إتمام عملية الترتيب كلّيّاً . بالتالي فهي مكافئة لترتيب الفقاعات خلال هذه المرحلة , ولكن معظم السلاحف الموجودة يكون قد تم التعامل معها , ولذلك سيكون ترتيب الفقاعات فعالاً خلال هذه المرحلة.   يؤثّر معامل الانكماش بشكل كبير على ترتيب المشط . وقد اقترح المؤلف في مقاله الأصلي عن الخوارزمية قيمة 1.3 للهذا العامل .فالقيمة الصغيرة للمعامل تسبب بطء الخوارزمية لاحتياجها للمزيد من المقارنات , بينما تسبب القيمة الكبيرة للمعامل عدم حدوث أي مقارنة .وقد وجد Lacey و Box بالتجربة (عبر اختبار ترتيب المشط على أكثر من 200,000 قائمة عشوائية )أن القيمة 1.3 هي الأفضل لعامل الانكماش. الصورة المتحركة التالية توضح الترتيب لقائمة من أعمدة مختلفة الأطوال :   شبه الكود ================================================================================    تابع    ترتيب_المشط(  مصفوفة   الدخل )     الفجوة    :=    الدخل.الحجم \\تهيئة حجم الفجوة     الانكماش    :=    1.3 \\تعيين قيمة عامل الانكماش        كرر حتى تصبح    الفجوة   =   1  و  المبادَل   =    غ يرصحيح         \\تحديث قيمة الفجوة لمشط جديد. ما يلي مجرد مثال          الفجوة   :=  عددصحيح( الفجوة  \  الانكماش  )\\قسمة صحيحة         إذا كانت  الفجوة  < 1           \\أصغر قيمة للفجوة هي 1            الفجوة  := 1         نهاية جملة الشرط                   س    :=   0          المبادَل   :=    غيرصحيح \\انظر ترتيب الفقاع ات للتوضيح                  \\"مشطٌ" واحد على قائمة الدخل          كرر حتى تصبح   س  + الفجوة >=  الدخل.الحجم              إذا كانت  الدخل[س] > الدخل[س+الفجوة]                  مبادلة (الدخل[س], الدخل[س+الفجوة])                 المبادَل  :=  صحيح \\ ضع علامة بأن عملية تبادل  قد تمّت مما يعني                                 \\ أن القائمة ليست مرتبة بالضرورة             نهاية جملة الشرط             س := س + 1         نهاية جملة الشرط     نهاية حلقة التكرار نهاية التابع ================================================================================     وإليكم كود بسيط بلغة ++C هو مجرد ترجمة مباشرة لشبة الكود: #include <iostream>using namespace std;int*CombSort(int*input,int input_size){    int gap=input_size;    double shrink=1.3;    bool swapped;    while (!( gap==1 and swapped==false )){//repeate until gap==1 and swapped==false        gap=int(gap/shrink);        if(gap<1)        {            gap=1;        }//end if        int i=0;        swapped=false;        while(!(    i+gap>=input_size    )){            if(input[i]>input[i+gap]){                swap(input[i],input[i+gap]);                swapped=true;            }//end if            i=i+1;        }//end while    }//end while    return input;}//end combSortint main(){    int A[10]={9,7,1,8,6,4,5,2,4,1};    for(int i=0;i<10;i++)        cout<<A[i]<<" ";    cout<<endl;    CombSort(A,10);    for(int i=0;i<10;i++)        cout<<A[i]<<" ";    cout<<endl;    return 0;}خاتمة : أخي الكريم , لقد قمت أثناء كتابة هذه المقالة بالرجوع إلى صفحة ويكيبيديا الانكليزية كمرجع رئيسي , ولكن رغبة مني في تحسين المقال الذي بين يديك الآن , ورغبة مني في تحقيق الأمنية الغالية وهي وجود مرجع عربي ممتاز لعلوم الحاسب بشكل رئيسي , فقد قمت بكتابة صفحة ويكيبيديا العربية الخاصة بترتيب المشط , أرجو من أن تساهم في تحسينها لأنك تفيدنا جميعاً بذلك , كما أرجو أن يكون هذا المقال بذرة لمقالات أخرى نساهم فيها جميعاً , ربما يتطوع أحدنا لتشكيل ُ ٌ ٍ ِ ُ بعض الكلمات , وآخر لتصحيح بعض الأخطاء الإملائية وآخر لاستبدال الكلمات المترجمة بترجمة أفضل , كل هذا ليس له علاقة بخبرتك في الموضوع بل بغيرتك على لغتنا العربية وحبك لها .   والله ولي التوفيق
  3. السلام عليكم ورحمة الله وبركاته اعتدنا أثناء الترتيب على البحث عن الخوارزمية ذات عدد المقارنات الأقل less comparisons , او على الخوارزمية ذات عدد الاستبدالات الأقل less swaps بين العناصر , ولكن ماذا لو كان لدينا كومة من الفطائر المكدسة فوق بعضها البعض وذات أقطار مختلفة .. ونريد ترتيبها . إن سبب تعدد خوارزميات الترتيب هو اختلاف الخوارزمية المثالية لبنية المعطيات التي لدينا , وهذا مبدأ هام جداً في دراسة الخوارزميات , فقد تكون عملية الاستبدال swap مكلفة في بنية ما , بينما تكون (O(1 في بنية أخرى , لذلك علينا العثور على خوارزمية تشمل العمليات الأقل كلفة حسب البنية المعطاة لنرجع إلى فطائرنا .. إن عملية استبدال فطيرتين مكلفة ! فهي تسبب اتساخ اليد بالـ"sauce" الموجود عليها , كما ان استخدام الملاعق لاستبدال الفطيرتين ... لك أن تتخيل ذلك , رفع ما فوق الفطيرة السفلى ثم رفع ما فوق الفطيرة العليا ثم التبديل ثم انزال الكدسات المرفوعة ... عملية مكلفة بكل ما تعني الكلمة ولكن ماذا عن عملية القلب flip  ؟ يمكننا وضع ملعقة بداخل الكدسة ثم قلب كل ما فوق هذه الكدسة , الشكل التالي يوضح كدسة فطائر قبل وبعد القلب واضح ان العملية بسيطة جداً , وغير مكلفة , ولذلك تم عمل خوارزمية الترتيب Flip Sort او ما يسمى Pancake Sort التي تعتمد على هذه الـ operator غير المكلفة , الـ FLIP operator في هذه الخورازمية يمكننا فقط القيام بعملية الـ flip هذه , ولترتيب القائمة التي لدينا علينا اتباع الخطوات التالية :   إذا كان لدينا n عنصر , فعلينا تكرار ما يلي n  مرة ولنضع عدادا i يبدأ من 1 : 1- العثور على العنصر الأكبر خلال المجال من i إلى n 2- وضع الملعقة على موضع العنصر الأكبر وقلب الكدسة التي فوقه . 3- وضع الملعقة في الموضع i وقلب الكدسة التي فوقه 4- زيادة العداد i والتوقف إذا كان i==n   للتوضيح : عملية قلب الكدسة هي عملية flip للعناصر من موضع القلب إلى القمة (أي إلى n ) هذا المقطع يوضح هذه الخوارزمية   الخوارزمية السابقة , يمكن تحسينها حيث لا نحتاج لعمليتي القلب إن كان العنصر في مكانه , كما لا نحتاج عملية القلب الأولى إن كان العناصر أصلاً في القمة (أي في الموضع n ) وبذلك يمكننا تحسينها إلى :   إذا كان لدينا n عنصر , فعلينا تكرار ما يلي n  مرة ولنضع عدادا i يبدأ من 1 : 1- العثور على العنصر الأكبر خلال المجال من i إلى n 2-    2.1- إذا كان العنصر الأكبر في الموضع i نتركه كما هو    2.2- إذا كان العنصر الأكبر في الموضع n نقوم بوضع الملعقة في الموضع i ونقلب الكدسة رأساً على عقب    2.3- إذا لم يكن العنصر الأكبر هو العنصر i  ولا  العنصر n  فعلينا وضع المعقة في موضع العنصر الأكبر وليكن j وقلب الكدسة التي فوقها عندها سيصبح في الموضع n ثم ننفذ 2.2 3-نزيد قيمة i (عند هذه النقطة يكون كل العناصر من الأسفل وحتى i مرتبة ) ونتوقف إذا كان i==n   إذا اعتبرنا عملية الـ flip هي العملية الوحيدة فإن أكبر عدد من الـ flip تحتاجه الكدسة حتى يتم ترتيبها هو 2*n (مرتان لكل موضع ) ولا ننسى أننا بحاجة إلى العثور على العنصر الأكبر في الكدسة , مما يعني (O(n للبحث كل مرة , وبذلك يكون التعقيد الزمني للخوارزمية لو كانت عملية القلب (O(1 هي (O(n2 ولكن عملية القلب حوسبياً هي عملية (O(n وبالتالي تعقيد الخوارزمية حسابياً هو (O(n3 إذا هي فعالة في الحياة العملية أكثر منها في الحاسوب .   كانت هذه لمحة موجزة و سريعة عن هذه الخوارزمية , أرجو أن تكون مفيدة والله ولي التوفيق     المصادر : Wikipedia GeeksForGeeks
  4. تعرف على التابع std::sort

    السلام عليكم ورحمة الله ويركاته   هدف هذا المقال هو التعرف على تابع الترتيب الجاهز في مكتبة STL التي توفرها ++C , والذي يتم تطوير الـimplimentation بداخله نسخةً بعد نسخة , فقد بدأت بالترتيب السريع quick sort مع أول ظهور لها (إذ كانت تماثل تابع qsort في cstdlib ) أما الآن فهي تعتمد خوارزميات ترتيب أفضل , وأكثر ثباتاً ( ليست عشوائية , وتحقق(n*log (n في الحالة الأسوأ ) , آخر نسخة أعرفها تستخدم intro sort كمرحلة أولى ثم insertion sort كمرحلة ثانية .   فهرس المقالة : 1-  تعريف التابع sort 2- وسطاء التابع 2.5- عملية المقارنة 3- Member < Operator 4- Global < Operator 5- تمرير الوسيط الثالث كمؤشر إلى تابع 6- تمرير الوسيط الثالث كــ function object 7- تمرير الوسيط الثالث كعبارة lambda   التابع sort : ما يهمنا هنا هو استخدام هذا التابع , والمعرّف كقالب template بالشكلين التاليين : template <class RandomAccessIterator>void sort ( RandomAccessIterator first, RandomAccessIterator last );template <class RandomAccessIterator, class Compare>void sort ( RandomAccessIterator first, RandomAccessIterator last, Compare comp );  التعريف الأول يستخدم االعملية <  لمقارنة العناصر , أما الثاني فيستخدم تابع خاص للمقارنة .   وسطاء التابع : الوسيط الأول: مؤشر وصول عشوائي لأول عنصر في القائمة المراد ترتيبها , مثلاً لو أردنا ترتيب مصفوفة فهو عنوان أول عنصر , أما لو أردنا ترتيب vector فهو الـ iterator الذي تعيده الدالة ()begin الوسيط الثاني: مؤشر وصول عشوائي للعنصر بعد الأخير القائمة المراد ترتيبها .مثلاً لو أردنا ترتيب مصفوفة فهو عنوان أول عنصر + عدد العناصر , أما لو أردنا ترتيب vector فهو الـ iterator الذي تعيده الدالة ()end الوسيط الثالث : هو مؤشر إلى تابع , أو functor سيتم شرحه بالتفصيل لاحقاً في هذا المقال . مثال على ترتيب مصفوفة أعداد صحيحة : #include <iostream>#include <algorithm>using namespace std;int main(){    int a[]={9,7,5, 4,1,8,  2,3,4,  5};    sort(a,a+10);    for(int i=0;i<10;i++){        cout<<a[i]<<" ";    }    return 0;}مثال على ترتيب vector : #include <iostream>#include <algorithm>#include <vector>using namespace std;int main(){    vector<int>a={9,7,5, 4,1,8,  2,3,4,  5};    sort(a.begin(),a.end());    for(int i=0;i<10;i++){        cout<<a[i]<<" ";    }    return 0;}  عملية المقارنة : أثناء القيام بعملية الترتيب , تتم مقارنة العناصر . في لغة C يوجد التابع qsort الذي يحتاج وسيطاً هو تابع مقارنة , يعيد 1 في حال كان الوسيط الأول أكبر من الثاني , و -1 في حال أصغر , و 0 في حال التساوي . أما في ++C , فالتابع sort  يقوم باختبار بولياني bool يعيد true أو false   Member < Operator : ففي النسخة الأولى من التابع (ذات الوسيطين ) يقوم تلقائياً باختبار(if(a<b أي أنه يستخدم العملية (أصغر > )  , فلو كنت تريد ترتيب قائمة من نوع جديد , يجب أن يحوي هذا النوع بداخله على تعريف للعملية > . مثال : لدينا نوع جديد اسمه book وأردنا تعريف عملية المقارنة > بحسب تاريخ الكتاب , ثم اسم مؤلفه , #include <iostream>#include <algorithm>#include <string>#include <vector>using namespace std;struct book{    int date;// 2000bc --> 2014 ac    string author;    book(int d,string a):date(d),author(a){    }    bool operator<(const book second){        if(date<second.date)            return true;        else if(date==second.date){            if(author<=second.author)                return true;            else                return false;        }else            return false;    }    void print(){        cout<<"author "<<author<<" date:"<<date<<endl;    }};int main(){    vector<book>a;    a.push_back(book(1999,"mohammad"));    a.push_back(book(2014,"mostafa"));    a.push_back(book(2010,"ahmad"));    a.push_back(book(1988,"mohammad"));    sort(a.begin(),a.end());    for(unsigned int i=0;i<a.size();i++){        a[i].print();    }    return 0;}/*( ملاحظة : الكود لا يعمل على Code::blocks لسبب لا أعرفه , تمت تجربته بنجاح على VS2008 )*/هنا استعملنا العملية كـ member function , وكملاحظة سريعة : يمكننا استخدام أي من التعاريف التالية للوسيط :     bool operator<(const book second);    bool operator<(const book &second);    bool operator<(book second);    bool operator<(book &second);ولكن تختلف بغعاليتها , أما من ناحية الصلاحية فهي صالحة .   Global < Operator: كما يمكننا تعريف عملية > بدون وضعها داخل فئة معينة , أي تعريقها كــ  Global Operator كما يلي : #include <iostream>#include <algorithm>#include <string>#include <vector>using namespace std;struct book{    int date;// 2000bc --> 2014 ac    string author;    book(int d,string a):date(d),author(a){    }    void print(){        cout<<"author "<<author<<" date:"<<date<<endl;    }};bool operator<(const book&first,const book&second){        if(first.date<second.date)            return true;        else if(first.date==second.date){            if(first.author<=second.author)                return true;            else                return false;        }else            return false;    }int main(){    vector<book>a;    a.push_back(book(1999,"mohammad"));    a.push_back(book(2014,"mostafa"));    a.push_back(book(2010,"ahmad"));    a.push_back(book(1988,"mohammad"));    sort(a.begin(),a.end());    for(unsigned int i=0;i<a.size();i++){        a[i].print();    }    return 0;}   إن مسألة تعريف عملية الأصغر, مسألة مثيرة للاهتمام , فلا يمكنك ترتيب قائمة إن لم تكن تستطيع تحديد أي العناصر تريدها أن تكون في بداية القائمة وأيها في نهاية القائمة . وعلى هذا المبدأ , يتعمد (التعريف الثاني للتابع ) على الوسيط الثالث compare وهو تابع يأخذ وسيطين (من نوع العناصر في القائمة) ويعيد قيمة بوليانية boolean تكون true إن كان الأول أصغر من الثاني وfalse إن كان أكبر أو يساوي . وبذلك يمكننا خداع الدالة بحيث تتعامل مع العملية > ونكون فعلياً نتعامل معها على أنها < لكي نعكس الترتيب (تصاعدي أو تنازلي ) ولكن للأسف , لا يمكننا إعادة تعريف عملية > للأنواع الأساسية , مثل int . فالكود التالي يعتبر خاطئاً bool operator<(const int&a,const int&b){    /*some operations*/}لذلك سنلجأ إلى كتابة تابع compare يقوم بالمهمة , وهو تماماً كفكرة عملية الـ > , يعيد قيمة بوليانية boolean ويأخذ وسيطين هما القيمتان المراد مقارنتهما .   تمرير الوسيط الثالث كمؤشر إلى تابع : لفهم عمل التابع يجب فهم كيفية التعامل مع القيمة المعادة منه : عندما يعيد هذا التابع true فإنه يضمن لك أن يكون الوسيط الأول قبل الوسيط الثاني ( لننس فكرة الأصغر والأكبر ) , فلو كنت تريد أن يكون العنصر الأصغر في البداية والأكبر في النهاية (ترتيب تصاعدي ) عليك إعادة true في حال كان الوسيط الأول أصغر من الثاني , أما إن كنت تريد الترتيب التنازلي فعليك إعادة true  إن كان الوسيط الأول أكبر من الوسيط الثاني , وبذلك سيضمن لك التابع أن الوسيط الأول سيستقر قبل الثاني في المصفوفة . لمعرفة هل العددان متساويان يتم استدعاء التابع مرّتين بحيث تكون الثانية هي نقس الأولى ولكن بعكس ترتيب الوسطاء ,لذلك على التابع أن يحقق هذه العمليات المنطقية , فلا يجوز أن يعيد true مهما كانت الوسطاء مثلاً .. المثال التالي يوضح كيفية تمرير (مؤشر إلى تابع) أو ببساطة (تابع) كوسيط ثالث للدالة sort #include <iostream>#include <algorithm>using namespace std;bool compare(const int&a,const int&b){    if(a<b)        return true;    else return false;}int main(){    int a[]={9, 7,6,4,   8,2,5, 4,3,1};    sort(a,a+10,compare);    for(unsigned int i=0;i<10;i++){        cout<<a[i]<<" ";    }    return 0;}الكود السابق يقوم بالترتيب التصاعدي العادي , أما التالي فهو (بتغيير محتوى تابع المقارنة ) يقوم بالترتيب التنازلي (سأضع الدالة compare  فقط ) bool compare(const int&a,const int&b){    if(b<a)        return true;    else return false;}لاحظوا أننا لو كتبنا الدالة compare كما يلي : bool compare(const int&a,const int&b){    return true;}سيتم وضع المصفوفة بشكل عشوائي لأن عملية الترتيب لن تتم بأي شكل منطقي .   تمرير الوسيط الثالث كــ function object : يمكن تمرير الوسيط كـ functor أي كـ struct تم تعريف العملية () بداخله , وهذه الطريقة مفيدة في تسريع الكود , حيث يمكنها استغلال خاصية الـ inlining في الكود #include <iostream>#include <algorithm>using namespace std;struct test{    bool operator()(const int&a,const int&b){        if(a>b)            return true;        else return false;    }};int main(){    int a[]={9, 7,6,4,   8,2,5, 4,3,1};    sort(a,a+10,test());    for(unsigned int i=0;i<10;i++){        cout<<a[i]<<" ";    }    return 0;}  أحد هذه الfunctor الجاهزة هو greater نستخدمه للترتيب التنازلي كـ functor جاهز : #include <iostream>#include <algorithm>using namespace std;int main(){    int a[]={9, 7,6,4,   8,2,5, 4,3,1};    sort(a,a+10,greater<int>());    for(unsigned int i=0;i<10;i++){        cout<<a[i]<<" ";    }    return 0;}  تمرير الوسيط الثالث كعبارة lambda  (خاص بـ C++11 وما بعد ) : بالعودة إلى مؤشر التابع , من الأمور الممتعة في C++11 تعابير lambda , التي تسمح بتعريق التابع في وقت استخدامه ,وأحياناً يكون استخدامه مفيداً جداً في توضيح الكود ( بحيث نضع طريقة المقارنة في نفس مكان استدعاء الترتيب ) #include <iostream>#include <algorithm>using namespace std;int main(){    int a[]={9, 7,6,4,   8,2,5, 4,3,1};    sort(a,a+10,[](const int&a,const int&b){if(a>b)return true;else return false;});    for(unsigned int i=0;i<10;i++){        cout<<a[i]<<" ";    }    return 0;}  هنا نصل إلى نهاية المقالة , أرجو أن أكون قد نقلت معظم الطرق التي تستخدم بها المقارنة في هذه الدالة , وأتمنى انه قد أصبح بإمكانك البدء باستخدام التابع std::sort دون أن تجد صعوبة في تحديد الطريقة التي تريد بها ترتيب العناصر .     المصادر : STL Sort Comparison Function cpp-reference كيف تكتب تابع compare مثال على ترتيب vector يحوي vector     والله ولي التوفيق
  5. السلام عليكم ورحمة الله وبركاته حديثنا اليوم عن خوارزمية ترتيب ممتعة , بالرغم من كون تعقيدها الزمني (O(n2 , إلا أنها ملفتة للنظر بفكرتها , ومعرفتُها (قد) تؤدي بنا إلى تطوير خوارزميات أخرى أو على الأقل التفكير بطريقة جديدة , والهدف من استهداف هذه الخوارزمية في هذه المقالة هو جماليتها لا فاعليتها . خوارزمية خلّاط الكوكتيل ! أو باسمها الرسمي الترتيب الفقاعي ثنائي الاتجاه . تعتمد خوارزمية الترتيب الفقاعي على مقارنة كل زوجين متجاورين وتبديل مكانيهما إن كان شرط الترتيب غير محققاً (حيث شرط الترتيب هو الذي يحدد طريقة الترتيب تصاعدي أو تنازلي) ويتم الترتيب الفقاعي بالمرور على عناصر القائمة أو المصفوفة بجهة واحدة وإجراء المقارنة والاستبدال إن لزم , ثم تكرار عملية المرور بنفس الجهة عدداً n من المرات (حيث n هو عدد عناصر القائمة ). مثال (على الترتيب الفقاعي) :لدينا القائمة نريد ترتيبها تصاعدياً بحيث يكون الأصغر على اليسار والأكبر على اليمين لذلك نقوم بعمل n-1 مقارنة (حيث n هنا هو 6 ) كما يلي بعد المقارنة نقوم بتبديل مكاني العددين إن كان الأيسر أكبر من الأيمن (أي بعكس الهدف الذي نريد الوصول إليه ) فتصبح ثم نقوم بمقارنة الزوج الثاني ونقوم بالاستبدال لأن الأيسر أكبر من الأيمن وهكذا سينتج لدينا بعد كل مقارنة واستبدال التسلسل التالي والآن انتهى المرور الأول (احتاج إلى 5 عمليات استبدال)  لاحظ كيف أن الرقم 9 انتقل من أقصى اليمين إلى أقصى اليسار  ,ولكن الرقم الأصغر 1 انتقل خطوة واحدة فقط لليمين وهذا ما يسمى بمشكلة السلحفاة ,  أي أن الرقم الصغير يسير ببطء شديد نحو موضعه الحقيقي , فالترتيب الفقاعي للقائمة السابقة (بعد انتهاء المرور الثاني , يحتاج إلى 3 عمليات استبدال ) سيكون : لاحظوا أن النتيجة ظهرت وكأننا قمنا بعمل insertion sort بحيث وضعنا الـ 4 في مكانها وأزحنا الباقي لليسار بعد المرور الثالث (عمليتا استبدال) : وبعد المرور الرابع ( عملية استبدال واحدة ) احتجنا إلى 11 عملية استبدال أما ترتيب الكوكتيل , فالاختلاف الوحيد بينه وبين الترتيب الفقاعي هو أن المرور ذو الرقم الزوجي ( مثلاً المرور الثاني والرابع .. ) يكون من اليمين لليسار (بعكس جهة المرور الفردي ) لنرجع إلى القائمة نفسها : المرور الأول مطابق تماماً للترتيب الفقاعي (يحتاج 5 عمليات استبدال ) وسيعطي : والآن إلى المرور الثاني : نبدأ من اليمين إلى اليسار (سنرمز بالمقارنة التي لا ينتج عنها استبدال بخط , والتي ينتج عنها استبدال بسهمين متعاكسين) انتهى المرور الثاني (احتاج 3 عمليات استبدال ) بوضع 1 في البداية , وبذلك تخلصنا من أثر السلحفاة .  بعد انتهاء المرور الثالث (باستخدام عمليتي استبدال )سيكون لدينا : وبانتهاء المرور الرابع (بعملية استبدال واحدة )   كلا الخوارزميتين احتاج 11 عملية استبدال , وكلاهما قام بـ 4 مرات مرور على المصفوفة . ملاحظة : في المراجع يتم اعتبار المرورين (من اليسار لليمين ثم من اليمين لليسار كمرور واحد للكوكتيل) فأين هو التحسين ؟ أحياناً تحتاج خوارزمية الكوكتيل عدداً أقل من عمليات المرور مثلاً المصفوفة (2,3,4,5,1) , وفي الحالة الوسطية فإن ترتيب الكوكتيل يكون أسرع بأقل من مرتين تقريباً من الترتيب الفقاعي . ولكن ربما يمكننا الاستفادة من أن الخوارزمية تقوم بنقل العناصر ذات القيمة المتوسطة إلى المنتصف كل دورتين , أي أنه يمكننا اعتبار المصفوفة مرتبة بشكل جزئي , فلو اضطررنا لإنهاء الترتيب للبيانات فسيكون لدينا البداية والنهاية مرتبة وهذا عملي أكثر من ترتيب النهاية فقط . كما ذكرت في بداية المقالة , فالهدف هو رؤية جمالية الخوارزمية , لذلك أترككم مع فيديو يوضح عملية ترتيب قائمة ( حيث تم تمثيل قيمة العناصر بارتفاع العمود ) الفيديو يستحق المشاهدة بالفعل http://www.youtube.com/watch?v=njClLBoEbfI http://www.youtube.com/watch?v=JiJXnEpDk5o   المراجع : http://en.wikipedia.org/wiki/Cocktail_sort http://www.codingunit.com/cocktail-sort-algorithm-or-shaker-sort-algorithm http://en.algoritmy.net/article/40270/Shaker-sort   والله ولي التوفيق
  6. الترتيب في الجافا

    السلام عليكم ورحمة الله وبركاته اريد كود جافا للترتيب بطريقة (replacement sort), (external merge sort) ارجو الرد بسرعة وشكرا
  7. مواضيع متنوعة حول الفيجوال بيسك دوت نت   استخدامات متقدمه للماوسConsole Applicationبرنامج البحث عن الملفات في جهازككيف يمكنك تعداد تكرار كلمة في نص معين بواسطة ال Linqالبحث عن تعابير معينة في جملة معينة بواسطة Linqالبحث عن ملفات تبعا لإمتدادها بواسطة ال Linqنظرة على جديد الفيجوال بيسك 9 – الجزء الثانينظرة على جديد الفيجوال بيسك 9 – الجزء الأولHashSet(T)كيف اكسر حماية برنامج مكتوب بالـ .NETتقنية ال .NET Remotingشرح خوارزمية ال Bubble Sortقنص الأخطاء و طرق التخلص منها – Exceptions Handlingالمعامل IsNotال Using Instructionال Global InstructionXML Commentsال Partial Classال Genericsالمعامل TryCastالإختصار MYMake Data Types NullableEncrypt Secrets for the Current UserADO.NET مقدمة لاهم كائناتهامكتبة للتحكم بال Nintendo’s WiimoteVisual Basic TVجرب قدراتك البرمجية مع مايكرسفتلغة XAMLال WinFX و ال Avalonوضع أسماء الالوان المتاحة في كومبوبوكسعمل خاصية Nudge كالتي في المسنجر!لفرق بين ByRef و ByValاستعمال كلمة محجوزة كمتغيرGets Installed Printers In your Computerاستخدام الكلمة المحجوزة withFlash Window – عمل اضاءة لبرنامجك في TaskBarرسم شكل هندسيعمل Drag&Dropالتعامل مع ال ProcessThreading and the Asynchronous Pattern in VB.NETكيفية ايقاف و الخروج من الويندوزتنفيذ أوامر Dos في برنامجك و إظهار النتائج فيهانشاء Button ذات Design خاص بك بواسطة برنامج Ms Blendمن MS Expression Design الى MS Expression Blend – الجزء الأMake some effects to images with VB.NETManaging text files with vb.netشرح الحصول على ip address من ال HostNameWebServices in Visual Basic.NET Part 2 (Arabic)WebServices in Visual Basic.NET Part 1 (Arabic)الوراثة في الفيجوال بيسك دوت نت – الجزء الثانيالوراثة في الفيجوال بيسك دوت نت – الجزء الأولاستخدام ال Crystal Report مع الفيجوال بيسك دوت نتمقدمة لبرنامج Microsoft Expression Blendخطوة بخطوة في التعامل مع الملفات و المجلداتالتعامل مع الملفات (قراءة،كتابة،،،)إستخلاص معلومات حول ملف معينCompress/Decompress Filesإستخراج ال Tags من ملف MP3اجعل جهازك يعمل شيئا من أجلك.التعامل مع ال Stringأساسيات البرمجة – مقدمة عامةالمصفوفات – Arraysالمتغيراتالحلقة التكرارية For … Nextبدايات البرمجة – الأساسياتما هي خاصية IsMdiContainer وكيف تعملخوارزمية ال Bubble SortUsing CodeDomالحلقة التكرارية For … Next 
  8. السلام عليكم لدي بيانات موجودة في DataGridView ارغب بترتيبها استخدمت الكود التالي private void dataGridView2_ColumnHeaderMouseClick(object sender, DataGridViewCellMouseEventArgs e)         {            ;  (dataGridView2.Sort(dataGridView2.Columns[e.ColumnIndex], ListSortDirection.Ascending          } وعند تنفيد الكود حدث الاستثناء التالي: DataGridView control must be bound to an IBindingList object to be sorted ارجو المساعدة ولكم جزيل الشكر
  9. السلام عليكم ورحمة الله المحتوى عبارة عن مقارنة في وقت تنفيذ خوارزميات selection , bubble , quick sort \ وذلك من خلال مصفوفة مكونة من خمسة آلاف عنصر لكي يظهر وقت لأنه في حالة المصفوفات الأقل فإن الوقت لا يظهر بالشكل المطلوب وبإمكانك زيادة حجم المصفوفة حسب ما تريد ويعمل البرنامج على تعبئة المصفوفة بعناصر عشوائية تحددها من خلال دالة الأرقام العشوائية. ومن ثم يتم نسخ عناصر المصفوفة إلى مصفوفتين أخرى ومن ثم استدعاء الدوال الثلاث كلا بمصفوفة منفصلة ومن ثم يتم احتساب الوقت بالمللي ثانية وبأمكانك أن تجعلها ثانية أو كما تريد أرجو أن يكون فيه فائدة لكم ملاحظة: البرنامج بلغة السي شارب :) :) :) :) :) :) :) :) :) :) :) :) :) :) :)DiferenceBetweenSortingAlgo.rar
  10. في هذه السلسلة سأضع بين أيديكم شرحا لأهم الخوارزميات الـمُستعملة في البحث و الترتيب و كلي أمل بأن يستفيد الجميع. خوارزمية ترتيب الفقاعات (Bubble sort algorithm) رابط الجزء الأول كان من المفترض أن نتحدث في هذه المقالة عن خوارزمية الترتيب الثنائي و لكن أحببت أن أبدأ بإحدى خوارزميات الترتيب نظرا لأن الـــ Binary search algorithm يعتمد على فكرة الترتيب. في هذه المقالة (أو لنقل بقية أجزاء السلسلة) ستجدني أتحدث أحيانا مع شخص افتراضي اسمه عمرو, ألجأ إلى الحديث مع هذا الشخص عندما أصل إلى فقرة تحتاج إلى توضيح أكثر. في هذا الدرس سنتطرق إلى النقاط التالية : الخوارزمية (الهدف, الفكرة, النتيجة, الإيجابيات و السلبيات)قبل أن نبدأ .. إليك 4 طرق لعمل Swapكتابة دالة تقوم بعملية التبديلالخوارزمية بلغة السي++التعقيد الزمني.ملأ مصفوفة عشوائيا و اختبار سرعة الخوارزمية. 1. الخوارزمية (الهدف, الفكرة, النتيجة, الإيجابيات و السلبيات) : الهدف : ترتيب عناصر المصفوفة X تصاعديا أو تنازليا. (في بقية الدرس سنعتبر أن الترتيب تصاعدي و n هو عدد عناصر المصفوفة X) الفكرة : تقارن هذه الخوارزمية بين قيم الخانات المتجاورة, تبدأ بالمقارنة بين أول خانتين من المصفوفة, إذا كان محتوى الخانة الأولى أكبر من محتوى الخانة الثانية سيتم تبادل محتوى الخانتين و هكذا مع بقية الخانات. عند انتهاء الدورة الأولى ستكون الخوارزمية قد أنجزت n-1 مقارنة و بهذا ستتم إزاحة أكبر عناصر المصفوفة إلى الخانة الأخيرة. بقي الآن ترتيب الــ n-1 عنصر. و هكذا الأمر مع بقية الدورات ... النتيجة : عملية الترتيب تـخـتلف عن عملية البحث في هذه النقطة, فالترتيب لا يقبل وجود عدة احتمالات في النتيجة, فعند تطبيق الخوارزمية سنحصل على مصفوفة مرتبة تصاعديا و بالتالي لا توجد احتمالات للمناقشة. الإيجابيات : الخوارزمية سهلة التصور و بسيطة المفهوم. السلبيات : بطيئة شيئا ما وغير عملية, خصوصا عند معالجة المصفوفات الضخمة. 2. قبل أن نبدأ .. إليك 4 طرق لعمل Swap : من خلال دراستك لخوارزميات الترتيب المختلفة ستجد أن مفهوم Swap أو تبادل مُحتوى متغيرين يتكرر باستمرار .. فأغلب خوارزميات الترتيب (إن لم تكن كلها !) تعتمد في مرحلة ما على تبديل محتوى خانتين لوضعهما في الترتيب الصحيح, لذا سنوضح كيفية تبديل محتوى متغيرين قبل أن نبدأ بكتابة الخوارزمية بلغة السي++. سنتناول فيما يلي 4 طرق لعمل Swap, لكل منها إيجابيات كما لها سلبيات أيضا. الطريقة الأولى (و هي الأكثر شهرة) تكمن في استخدام وسيط مساعد يُساعدنا على تبديل محتوى المتغيرين, فنضع قيمة المتغير الأول في الوسيط ثم نضع قيمة المتغير الثاني في المتغير الأول ثم نضع قيمة الوسيط في المتغير الثاني, و بهذا نكون قد بادلنا بين قيمة المتغير الأول و الثاني. لنفرض أن x=5 و y=-1 : t = x //t = 5x = y //x = -1y = t //y = 5في النهاية تكون x=-1 و y=5 . و بالتالي تم تبديل قيمتي x و y. يمكنك تـخيل الفكرة كما يلي .. لدينا كأسين x و y, الكأس x يحتوي على العصير و الكأس y يحتوي على الماء, لو أردنا أن نُبادل محتوى الكأسين, (أي نجعل الماء في الكأس x و العصير في الكأس y) سنقوم باستخدام كأس ثالث فارغ (وهو الوسيط المساعد t) و تكون عملية التبادل كما يلي : نجعل العصير في الكأس الفارغ.نجعل الماء في الكأس x.نجعل العصير في الكأس y. الآن أصبح الكأس x يحتوي على الماء و الكأس y يحتوي على العصير. هذه الطريقة بسيطة و تقليدية أيضا, إلا أنها تأخذ مساحة أكثر من الذاكرة بالإعلان عن الوسيط الثالث. يمكننا عمل Swap بدون حاجة إلى وسيط مساعد عن طريق إجراء بعض العمليات الحسابية البسيطة على المتغيرين. الطريقة الثانية (تصلح للمتغيرات العددية فقط) : x=x+y;y=x-y;x=x-y;الطريقة الثالثة (تصلح للمتغيرات العددية فقط و يجب أن تختلف قيمة y عن الصفر) : x=x*y;y=x/y;x=x/y; ملاحظة : الطريقتان السابقتان يمكنهما أن يتسببا في حدوث Overflow إذا كانت قيمة x+y أو x*y أكبر من القيمة العظمى لنوع المتغيرين x,y. توجد أيضا طريقة رابعة لا تحتاج إلى وسيط مساعد و لا يمكن أيضا أن تكون سببا في حدوث Overflow. تعتمد هذه الطريقة على أحد الــ Bitwise (مؤثرات الــ Bit) وهو المؤثر XOR (اختصار لـــ Exclusive OR) و الذي يُرمز له بــ ^ , هذا المؤثر يعطينا True إذا و فقط إذا كان المدخلين مختلفين, أما إذا كانا متشابهين فالنتيجة ستكون False و يعمل هذا المؤثر كالتالي : و كمثال على ذلك : سنقوم بتجربة هذه الطريقة على المتغيرين x و y حيث x = 15 و y=7, لذلك سنقوم بالخطوات الثلاثة التالية : x = x^y // x = 15 XOR 7 = 8y = x^y//y = 8 XOR 15 = 7x = x^y//x = 7 XOR 8 = 15و بهذا تم تبديل محتوى المتغيرين x و y. يمكننا الآن كتابة دالة تبادل بين مُحتوى مُتغيرين باستخدام إحدى الطرق الأربعة الموضحة أعلاه, مع الأخذ في الاعتبار سلبيات كل طريقة. إذا أدرت التوسع أكثر في هذه الجزئية, فيمكنك البحث عن أفضل طريقة لتبديل محتوى متغيرين بحيث تحقق النقاط الآتية في آن واحد : لا تحتاج إلى وسيط مساعد. (المستوى : بسيط)لا تسبب Overflow. (المستوى : صعيب) لا تضع أي شرط على قيم أو نوع المتغيرين. ( المستوى : أكثر صعوبة, إن لم يكن مستحيلا !) 3. كتابة دالة تقوم بعملية التبديل : بعد أن تطرقنا إلى الطرق الأربعة التي يمكننا من خلالها تبديل محتوى متغيرين. سنقوم الآن بكتابة دالة تُبادل بين محتوى خانتين من المصفوفة X باستخدام الطريقة الأولى (لأنها الأكثر شعبية .. رغم احتوائها على انتهاك صارخ لحقوق الــ Overflow !) : عمرو :لم أفهم استخدام المؤشرات ! أحمد : لا بأس !, سترتاح قليلا عندما تعلم أن الكتابة السابقة مُطابقة تماما للكتابة الآتية : عمرو : كيف !؟ أحمد : الدالة السابقة تستقبل 3 وسائط, الأول عبارة عن اسم المصفوفة و الوسيطين, الثاني و الثالث عبارة عن أرقام الخانات الـمُراد تبديلها. عمرو : لكن .. لماذا تُعيد الدالة void ؟ أحمد : ببساطة .. لأن هدف الدالة يكمن في تبديل محتوى الخانتين, فقط ! لا أكثر و لا أقل, لذا ليست هناك قيمة مُعادة. أغلب الدوال التي تستقبل "بالمرجع" تعيد void لأن التغيير سيحصل في المتغير نفسه. لذا لسنا بحاجة إلى إعادة قيمة المتغير الجديدة. عمرو : طيب, لكنني لم أفهم الطريقة التي تستخدم المؤشرات ! أحمد : هل فهمتَ الطريقة الثانية ؟ عمرو : نعم أحمد : إذا أنت بالتأكيد قد فهمت الطريقة الأولى !, دعني أسألك ! عمرو : تفضل أحمد : ألم نقل أن الدالة Swap تستقبل مصفوفة ؟ عمرو : بلى ! أحمد : و هل المصفوفة عبارة عن كتلة واحدة ؟ عمرو : عفوا, لم أفهم السؤال ! أحمد : ...كنت أقصد, هل تُـخَزَّن المصفوفة في خانة واحدة من الذاكرة ؟ كما يحدث مع الأنواع البدائية لللغة كــ int مثلا ؟ عمرو : لا! طبعا, فالمصفوفة عبارة عن مجموعة من الخانات المتجاورة فيما بينها و ليست خانة واحدة. أحمد : جميل جدا, إذا .. كيف تستقبل الدالة هذه الخانات في آن واحد و تميزها عن غيرها ؟ عمرو: بصراحة .. لا أدري ! أحمد : الأمر بسيط جدا .. كما قلت أنت بنفسك قبل قليل " المصفوفة عبارة عن مجموعة من الخانات المتجاورة فيما بينها " و لكي يكون الكلام أكثر دقة يمكننا القول بأن المصفوفة عبارة عن مجموعة من العناصر المتجانسة(من نفس النوع) مُسجلة تحت اسم واحد ,حيث يمكن تمييز كل عنصر بترتيبه (دليله) في المصفوفة. عمرو : ...متجانسة ؟! أحمد : نعم, متجانسة ! و إلا فسنحصل على structure أو class ...عموما, دعنا في الموضوع !, قل لي .. كيف تُفرق بين مصفوفتين ؟ عمرو : بالإسم طبعا .. لأنه لا يمكن وجود أكثر من مصفوفة بنفس الإسم ! أحمد : طيب, لكن اسم المصفوفة ما هو إلا مؤشر يشير إلى أول عنصر فيها. عمرو : أمممممم .. يبدو أن مفتاح الفكرة يكمن في العنصر الأول ! أحمد : بالضبط, فانطلاقا من العنصر الأول يمكننا الوصول إلى بقية عناصر المصفوفة عن طريق إزاحة المؤشر إلى الأمام, لأننا قلنا سابقا أن خانات المصفوفة مُتجاورة ! عمرو: و ماذا لو حصلنا على مصفوفة خاناتها غير مُتجاورة ؟ أحمد: مُستحيل .. المصفوفة بالتعريف هي مجموعة من الخانات المُتجاورة فيـــ... عمرو: نعم .. نعم !, تذكرت ! ...طيب, هل لك أن تُلخص لي فكرة الكود السابق ؟ فأفكاري حوله لم تنضج بعد ! أحمد: الدالة Swap تستقبل مؤشر من نوع int بالإضافة إلى رقمان يدلان على مكان وجود القيم التي نريد إبدالها فيما بينها. واضح ؟ عمرو: مفهوم ! أحمد: في جسم الدالة قمنا باستخدام وسيط مساعد من شأنه مُساعدتنا في عملية Swap. الكتابة *(X + i) يمكننا قراءتها "قم بإزاحة المؤشر i إلى الخانة الموالية" و بالتالي سيشير المؤشر إلى الخانة رقم i+1 لأن الترقيم يبدأ من صفر. بنفس الطريقة قمنا بإزاحة المؤشر للحصول على محتوى الخانة رقم j.و بهذا تمت عملية التبادل. عمرو: اتضحت الفكرة. طيب, هل من تطبيق لما سبق ذكره ؟ أحمد: على مهلك, جواب سؤالك سيكون في الفقرة الموالية :) 4. الخوارزمية بلغة السي++ : كما ذكرنا سابقا فإن هذه الخوارزمية تقوم في الدورة الأولى بإزاحة أكبر عناصر المصفوفة إلى الخانة الأخيرة ثم تقوم في الدورة الثانية بإزاحة العدد الذي يلي أكبر العناصر إلى الخانة القبل الأخيرة و هكذا .. آخر دورة سيتم فيها وضع أصغر العناصر في الخانة الأولى. كل دورة ينتج عنها بعض التبديلات بين خانات المصفوفة مما يُساعد على تحسين ترتيب المصفوفة. تستقبل الدالة bubbleSort وسيطين: اسم المصفوفة و عدد عناصرها. تبدأ الحلقة الأولى ذات العداد i من أول خانة في المصفوفة و حتى الخانة القبل الأخيرة. عمرو : هل أفهم من كلامك أن الترتيب لن يشمل الخانة الأخيرة ؟ أحمد : كلا, لكن إذا وصل عداد الحلقة الأولى إلى القيمة size-1 سيؤدي هذا إلى حصول Underflow !, ستفهم أكثر بعد قليل ... هناك حلقة ثانية, تبدأ في كل مرة من الخانة الأولى و حتى الخانة رقم size - i – 2. عمرو : .. size - i – 2 !!؟, من أين أتيت بهذا العدد ؟؟ أحمد : الحلقة الثانية تعمل على ترتيب المصفوفة و في أسوأ الأحوال سيتم وضع عنصر واحد في الترتيب الصحيح. منطقيا .. إذا عادت الخوارزمية من جديد للترتيب فيجب أن تستثني العناصر التي تم ترتيبها. من أجل i=0 سيتم وضع أكبر الأعداد في الخانة الأخيرة (حصلنا على خانة واحدة مرتبة) و من أجل i=1 سيتم وضع العدد الذي يلي أكبر الأعداد في الخانة القبل أخيرة (حصلنا على خانتين مرتبتين). إذا في كل مرة سنحصل على size-i-1 من العناصر الغير مرتبة. عمرو : و بعد ؟ أحمد: حتى لا نُعيد اختراع العجلة .. لكي يتم ترتيب العناصر الغير مرتبة فقط يجب أن تبدأ الحلقة الثانية من الخانة الأولى (رقم صفر) و تتوقف عند الخانة رقم size-i-1.. و لكي لا يحدث Overflow يجب أن يكون j+1 = size-i-1 مما يعني أن j=size-i-2 و هي القيمة التي تتوقف عندها الحلقة الثانية. أحمد :نعود الآن إلى قضية الــ Underflow, عدد عناصر المصفوفة يساوي size, إذا رقم الخانة الأخيرة هو size-1 و رقم الخانة القبل أخيرة هو size-2, لاحظ أنه إذا كانت i=size-2 ستصبح j=0 وهنا ستتم مقارنة قيمة الخانة الأولى مع الثانية و إبدال محتوى الخانتين إذا كان الترتيب معكوسا و هذه هي آخر خطوات الخوارزمية. أما إذا كانت i=size-1 فستصبح j=-1 و هذا خطأ منطقي لأن ترقيم المصفوفات يبدأ من صفر. نأتي الآن إلى كتابة كود متكامل يحتوي على الدالة bubbleSort : المتغير LENGTH يمثل طول المصفوفة x. قمنا بطباعة عناصر المصفوفة قبل و بعد استدعاء دالة الترتيب. لاحظ الفرق. مثال للتوضيح : لنفترض أننا نريد ترتيب الجدول التالي : عند تطبيق الخوارزمية على الجدول سنحصل على النتائج التالية : إذا كانت i=0 : في كل مرة يتم تبديل محتوى الخانتين ذوات اللون الأزرق الفاتح, الخانة ذات اللون الأخضر تدل على أن ترتيب الخانتين في الوضع الصحيح لذا لم تتم مبادلتهما. لاحظ أنه من خلال الدورة الأولى تمت إزاحة أكبر عناصر الجدول إلى الخانة الأخيرة (في هذا المثال تمت إزاحة العدد 11 إلى الخانة الأخيرة). i=1 : إذا كانت i = 1 فإن القيمة العظمى لــ j ستكون 3 و بالتالي لن تتم المقارنة بين محتوى الخانة الأخيرة و الخانة الموجودة قبلها. لاحظ أنه سيتم ترتيب عناصر الجدول انطلاقا من نهايته. i = 2 : إذا كانت i=2 فإن Jmax=2 و هذا يعني أن الخانات رقم 3,4,5 مُرتبة بشكل صحيح. i = 3 : لاحظ معي أنه تم ترتيب عناصر الجدول مع أن الحلقة لم تنتهي بعد فما زالت دورتان i=4, i=5. ما رأيك لو أضفنا شرطا بسيطا يتعلق بالخروج من الدالة إذا وصلت الخوارزمية إلى ترتيب الجدول قبل انتهاء الحلقة ؟ إضافة بسيطة : الفكرة ببساطة تكمن في استخدام متغير منطقي وتغيير قيمته عندما يتم تبادل محتوى خانتين. عندما نجد أنه لم تتغير قيمة المتغير منطقي في إحدى الدورات فهذا يعني أن خانات الجدول أصحبت مُرتبة بشكل صحيح. مُحتوى الدالة الرئيسية سيكون هذا : 5. التعقيد الزمني : تُعد خوارزمية ترتيب الفقاعات من أبطئ خوارزميات الترتيب حيث يعود السبب إلى كثرة عمليات المقارنة و التبديل. من أجل ترتيب جدول يحتوي على n عنصر سنحتاج إلى n-1 مقارنة (الأول و الثاني, الثاني و الثالث, ... , ما قبل الأخير والأخير) ثم نكرر نفس العملية من جديد على جدول يحتوي على n-1 عنصر و هكذا دواليك. إذا المرور رقم i سيحوي n-i مقارنة و بالتالي سيكون التعقيد الزمني للخوارزمية من حيث عدد المقارنات يُساوي : بالنسبة لعدد التبديلات : في أسوأ الحالات سنحتاج إلى n-i في المرور رقم i. في هذه الحالة نقول أن الجدول مُرتب بشكل مقلوب. إذا نـخلص إلى أنه في المرور رقم i سنحتاج بالضبط إلى n-i مقارنة و n-i تبديل في أسوأ الحالات. في أسوأ الحالات سيكون تعقيد الخوارزمية يساوي : و في المتوسط سيكون عدد التبديلات يُساوي : أما في أفضل الحالات فسيكون التعقيد خطيا : . 6. ملأ مصفوفة عشوائيا و اختبار سرعة الخوارزمية : سبق و أن تعرضنا في الحلقة السابقة إلى ملأ مصفوفة عشوائيا, الجديد هنا هو استخدام عداد و زيادته كل ما تمت عملية تبديل, لا أكثر : عند استدعاء الدالة bubbleSort سيتم إظهار عدد المرات التي تمت فيها عملية التبديل بالإضافة طبعا إلى رقم المرور الذي تمت فيه عملية الترتيب. ملأ المصفوفة x عشوائيا و استدعاء الدالة bubbleSort داخل main سيكون هكذا : إلى هنا أصل بكم إلى نهاية الدرس, أرجو أن تكونوا قد استفدتم. لا تنسوني من صالح الدعاء. تحياتي.