🚺 👃🏾 ✴️ مقارنة خوارزميات فرز الصرف 👨🏽‍💻 🤜 🤦🏾

تتناول هذه المقالة خيارات متعددة لفرز التبادلات ، وتصف أيضًا تطبيق رسومي بسيط ( processing.js ) مع أمثلة على أنواع.

قبل القراءة ، أوصي بأن تقرأ المقالات حسب المستخدم valemak :

→ تبادل الفرز
→ فرز فقاعة وجميع الكل
→ فرز سخيفة وبعض أكثر ذكاء

فرز فقاعة

أبسط خيار هو التكرار على الصفيف من العنصر الأول إلى العنصر الأخير ، متبادل (إذا لزم الأمر).

→ تحقق هنا

لتحريك شريط التمرير ، تحتاج إلى النقر فوق الزر الرمادي في الزاوية اليسرى السفلى.
عند النقر فوق الزر ، حرك شريط التمرير خطوة واحدة إلى اليمين

slider++;

بعد ذلك ، نتحقق من: هل وصلنا إلى نهاية الصفيف (ثم انتقل إلى البداية) ، ثم قارن (تبادل) العناصر المجاورة

رمز الزر

 //  //  void mousePressed() { if(boolButton) { counter++; if(mods[slider].rectHight < mods[slider-1].rectHight) { vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[slider].rectHight; mods[slider].rectHight=vTemp; } } } // void mouseReleased() { if(boolButton) { slider++; if(slider>=moduleSize) { slider=1; } } }

يستخدم Processing.js بنيات بيانات Java ، ثم تتم ترجمة التعليمات البرمجية إلى javascript ( link ) ، وبالتالي فإن الإعلان عن مجموعة من مثيلات فئة الوحدة النمطية ، المسؤولة عن تقديم العناصر وتهيئة المثيلات ، يحدث مثل هذا

قانون

 Module[] mods; ... mods[0] = new Module(1*30, 30); mods[1] = new Module(2*30, 50); mods[2] = new Module(3*30, 10); mods[3] = new Module(4*30, 60); mods[4] = new Module(5*30, 20); mods[5] = new Module(6*30, 100); mods[6] = new Module(7*30, 80); mods[7] = new Module(8*30, 70); mods[8] = new Module(9*30, 90); mods[9] = new Module(10*30, 40);

تتمثل الوظيفة الرئيسية لرسم draw void draw () في حلقة لا نهائية يتم فيها فرز مثيلات الفئة

 for (Module mod : mods) { mod.display(); }

أضف الدالة randFoo () ، والتي تُرجع قيمًا عشوائية. لضمان عدم تكرار القيم ، سنضيفها إلى ArrayLis في قائمة listRand ، وفي وظيفة randFoo () ، تحقق لمعرفة ما إذا كان الرقم العشوائي الجديد في قائمة listRand

 int randFoo(){ newRand = int(random(1,11)); if(!listRand.contains(newRand) ) listRand.add(newRand ); else newRand=randFoo(); return newRand; }

→ تحقق هنا

ترتيب بكسل

فرز البكسل (هنا) هو تطبيق لفرز الفقاعة.
سنقوم بتحويل البيكسلات الأكثر دفئًا / أخف إلى جانب واحد ، والباكن الداكن / الأبرد إلى الجانب الآخر

 void draw(){ while (i <= height) { c=get(i,j); //    cTemp=c; //      i++; //     c=get(i,j); //     if(cTemp>c) { //   fill(c); //    rect(i-1,j,1,1); fill(cTemp); rect(i,j,1,1); } } if(mousePressed) { if(j>=width) j=0; } //      if(i >= height) {j++; i=0;} }

→ تحقق هنا
لبدء الفرز ، انقر على الصورة مع الاستمرار على الزر.
يمكنك قراءة المزيد عن أنواع البكسل هنا .
فيديو حول فرز البكسل على القناة الرسمية The Coding Train هنا

المحدد والعلم

يمكنك تقليل عدد التكرارات إذا لم تقم بالتكرار على العناصر التي تم فرزها بالفعل. للقيام بذلك ، أضف محددًا إلى نهاية الصفيف ، والذي سينتقل إلى بداية الصفيف بعد كل تكرار

 if(slider>=limiter) { slider=1; limiter--; if(limiter<1) limiter=1; }

→ تحقق هنا

يمكن العثور على طريقة أخرى لتقليل عدد التماثيل النصية في مقالة Bubble Sort (ويكيبيديا). إذا لم يتم تبديل العناصر المجاورة أثناء مرور المصفوفة مرة واحدة ، فسيتم فرز المصفوفة ويمكن إكمال الدورة (حالة Iverson ).

أضف علامة العلم ، والتي يتم رفعها عندما نلتقي مع اثنين من العناصر التي تحتاج إلى التغيير. إذا تم رفع العلم ، تكرر على الصفيف مرة أخرى. إذا لم يكن كذلك ، قم بإنهاء الدورة. يتم عرض حالة العلم في وحدة التحكم

تحقق من العناصر المجاورة

 if(mods[slider].rectHight < mods[slider-1].rectHight) { flag=true; //   vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[slider].rectHight; mods[slider].rectHight=vTemp; }

→ تحقق هنا

إذا وضعت محددًا على اليسار واستخدمت عنصرًا محددًا كمرجع / الحد الأدنى ، فسنحصل على التصنيف حسب الاختيار.

أضف المتغير min الذي سيتم تحميل الحد الأدنى للقيمة عليه. افترض أن العنصر الموجود في أقصى اليسار في البداية هو الحد الأدنى: أثناء المرور الأول للصفيف ، إذا كان العنصر أقل من الحد الأدنى ، فإننا نقوم بحفظ هذا العنصر نفسه في المتغير min

 if(mods[slider-1].rectHight < min){ min=mods[slider-1].rectHight; }

ثم مبادلة العنصر الأول والحد الأدنى

 if (mods[limiterL-1].rectHight>min) { vTemp= mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=mods[slider-1].rectHight; mods[slider-1].rectHight=vTemp; }

إذا وصل شريط التمرير إلى الحافة اليمنى للصفيف ، فإن المحدد يتحرك خطوة واحدة إلى اليمين ، وينتقل شريط التمرير إلى المحدد

 if(slider==moduleSize){ if(limiterL<moduleSize) limiterL++; min=mods[limiterL-1].rectHight; incPaddle=limiterL-1; }

→ تحقق هنا
يمكن تقليل عدد المقاييس إذا قمنا في بداية البحث بمقارنة (تبادل) العنصر الحالي والعنصر الأقصى للصفيف

 if(mods[limiterL-1].rectHight>mods[moduleSize-1].rectHight) { vTemp=mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=mods[moduleSize-1].rectHight; mods[moduleSize-1].rectHight=vTemp; }

ثم لا يمكنك التحقق من أقصى اليمين عنصر الصفيف

 //if(slider==moduleSize){ if(slider==moduleSize-1){ //if(limiterL<moduleSize) limiterL++; limiterL++; min=mods[limiterL-1].rectHight; slider=limiterL-1; } // slider++; if(slider<moduleSize) slider++;

→ تحقق هنا

هنا يمكنك إضافة فرز الجزء الأيمن من المصفوفة بترتيب تنازلي عن طريق إضافة الحد الأقصى للعنصر كحد أقصى - نحصل على فرز شاكر حسب التحديد. راجع القسم الخاص بفرز شاكر في نهاية المقالة.

فرز سريع

يتم استخدام آلية اختيار عنصر الدعم أيضًا في الفرز السريع. تتضمن هذه الخوارزمية تحديد عنصر المرجع الأولي الذي تتم بمقارنة كافة العناصر الأخرى للصفيف به. يعتمد وقت تنفيذ الخوارزمية على اختيار العنصر الأولي. في gif أعلاه ، عنصر البداية هو رقم 3 . يمكنك قراءة المزيد حول اختيار عنصر دعم البدء في المقالة (ويكيبيديا).
يتوفر مقطع فيديو عن الفرز السريع على قناة يوتيوب الرسمية للغات المعالجة ولغة p5.j. هنا يمكنك رؤية تصور الخوارزمية.
إذا كان العنصر الأول أساسيًا ، فيمكنك إدراج عناصر أصغر من العنصر الأساسي الموجود أمامه ، ثم يتم تقسيم الصفيف إلى جزأين ، وتكون العناصر الموجودة على اليسار أصغر من العنصر الأساسي ، على اليمين - أكثر. لمثل هذه الطريقة ، راجع القسم الخاص بالفرز حسب المدرج أدناه.

قزم فرز

في الأساس ، ينظر الجنوم إلى أواني الحديقة التالية والسابقة: إذا كانت في الترتيب الصحيح ، فهو يتقدم للأمام ، وإلا فإنه يقايضها ويعيد الوعاء.

بعد رفع العلامة ، احفظ إحداثي شريط التمرير في المحدد المتغير وارجع شريط التمرير إلى بداية الصفيف في خطوات

 slider--;

مرة واحدة في بداية الصفيف ، إعادة تعيين العلم ووضع شريط التمرير في الخلية مع الإحداثيات التي قمنا بحفظها في المحدد المحدد R

 if(slider==0){ flag=false; slider=limiterR; }

→ تحقق هنا

عن طريق تغيير هذه الخوارزمية ، نحصل على " الفرز بواسطة إدراجات ".
في الفرز حسب إدراج ، يتم تحديد العنصر المرجعي / الأدنى ، ثم في الجزء غير المصنف من المصفوفة ، يتم تحديد العنصر ، أصغر من المرجع وإدراجه قبل المرجع

دعونا نحصل على الحد الأدنى من أماكن تبادل العناصر مع الأماكن السابقة ، حتى المرجع ، وهكذا. إدراج أمام المرجع.
إضافة شرط

 if(slider==limiterR-1 && mods[slider-1].rectHight<mods[limiterR-1].rectHight){ flag=false; slider=limiterR; }

→ تحقق هنا

مقارنة مع المحدد

يمكن تسمية خيار الفرز هذا بشكل تعسفي "فرز الإدراج القزم".
ضع المحدد على اليسار وسنستخدم العنصر مع المحدد كمرجع / الحد الأدنى ، كما هو الحال في اختيار الفرز.
إذا كان العنصر الحالي أكبر من الحد الأدنى ، انقل المنزلق إلى اليمين

 if(mods[slider-1].rectHight > mods[limiterL-1].rectHight) slider++;

إذا كان العنصر الحالي أقل من الحد الأدنى ، فاحفظ إحداثي شريط التمرير في المحدد المتغير R وأعد شريط التمرير إلى بداية الصفيف بخطوات ، كما هو الحال في فرز gnome

 vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[slider-2].rectHight; mods[slider-2].rectHight=vTemp; slider--;

 if(flag && slider==limiterL) { flag=false; slider=limiterR; }

إذا تجاوز المنزلق الحافة اليمنى ، انقل المحدد خطوة واحدة إلى اليمين ، فأرجع المنزلق إلى المحدد

 if(slider==moduleSize+1) { limiterL++; slider=limiterL+1; }

→ تحقق هنا

هنا يمكنك إضافة مقارنة (تبادل) للعناصر الحالية والعناصر التالية بطريقة الفقاعة

 if(slider<moduleSize)if(mods[slider].rectHight<mods[slider-1].rectHight){ vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[slider].rectHight; mods[slider].rectHight=vTemp; }

→ تحقق هنا

فرز "سريع" الإدراج

في هذه الخوارزمية ، يتم تقسيم الصفيف إلى قسمين بواسطة العنصر الداعم.
اجعل العنصر الأول هو المرجع: قارن ، بدءًا من الثاني ، عناصر المصفوفة بالمرجع ، إذا كان العنصر أصغر من المرجع

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight)

أدخل العنصر الموجود قبل المرجع

 if(mods[slider-1].rectHight < mods[pivot-1].rectHight){ flag=true; //   vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[slider-2].rectHight; mods[slider-2].rectHight=vTemp; }

إذا تم رفع العلم ، حرك المنزلق إلى اليسار بخطوات حتى نلتقي بعنصر الدعم

 if(flag){ slider--; if(slider<pivot){ flag=false; //   pivot++; slider=pivot; } }

وهكذا يتم تقسيم الصفيف إلى قسمين ، على اليسار - العناصر أصغر من المرجع ، على اليمين - أكثر

→ تحقق هنا

إذا ، بعد كل تعداد ، يتم حفظ إحداثيات عنصر الدعم في تحويلة. مجموعة pivotsArr ، ثم عندما يصل العنصر المرجعي إلى الحافة اليمنى ، نحصل على مصفوفة مرتبة حسب المستوى / الخطوة. ستكون العناصر في كل مستوى تالي أكبر من العناصر الموجودة في المستوى السابق. سيتم تضمين حدود المستويات في الإضافة. مجموعة pivotsArr
في كل مرة تنقر فوق الزر ، سنقوم بإخراج مجموعة pivotsArr إلى وحدة التحكم

 for(int i=0;i<pivotsArr.length;i++){ print(" "); print(pivotsArr[i]); print(" "); }

أضف الوظيفة العشوائية randFoo () إلى نهاية البرنامج.

→ تحقق هنا

أنت الآن بحاجة إلى فرز عناصر كل مستوى على حدة (يبقى فقط لإضافة شرط لإنهاء الدورة)

→ تحقق هنا
يمكن أن يوصف هذا الفرز كفرز حسب المستوى.
لأنه بعد كل تعداد ، يتم ترتيب البيانات الرقمية في مستويات ، وتتجاوز أرقام كل مستوى تالي الأرقام الموجودة في المستوى السابق.

الغريب الفرز

سنقوم بتحريك شريط التمرير بخطوتين ، مقارنة العناصر المجاورة

 slider=slider+2;

وهكذا نقارن العناصر 0 و 1 و 2 و 3 و 4 و 5 و 6 و 7 ، إلخ.
إذا وصل شريط التمرير إلى حافة الصفيف ، فاترك المحدد يتحرك خطوة واحدة إلى اليسار ، وينتقل شريط التمرير إلى بداية الصفيف.
بعد ذلك ، نقارن بين العناصر 1 و 2 و 3 و 4 و 5 و 6 و 7 و 8 ، إلخ.
بعد الوصول إلى المحدد ، نقوم بتحويله خطوة واحدة إلى اليمين ، ونضع شريط التمرير في بداية الصفيف.

→ تحقق هنا

فرز فرشاة الشعر

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

 if(limiter==moduleSize) { limiter = limiterStore-1; limiterStore = limiter; slider=1; }

حرك المنزلق مع الإيقاف إلى نهاية الصفيف في خطوات

 if(limiter!=moduleSize) { //  limiter     limiter++; slider++; }

بعد الوصول إلى نهاية الصفيف كمحدد ، ضع شريط التمرير في بداية الصفيف ، ثم ضع المحدد في limiterStore-1

 if(limiter==moduleSize) { limiter = limiterStore-1; limiterStore = limiter; slider=1; }

→ تحقق هنا

شاكر الفرز

إضافة المحدد المحدد الأيسر إلى بداية الصفيف.
دع علامة العلم ترتفع عندما يصل شريط التمرير إلى المحدد المحدد R ، ثم يتحرك المحدد خطوة واحدة إلى اليسار. علاوة على ذلك ، عندما يتم رفع العلم ، يتحرك شريط التمرير بخطوات إلى المحدد المحدد الأيسر L - يتحرك المحدد خطوة واحدة إلى اليمين - يتحرك شريط التمرير بخطوات إلى اليمين

رمز الزر

 //  void mouseReleased() { if(boolButton) { if(!flag) { slider++; if(slider==limiterR) { flag=true; limiterR--; if(limiterR<=limiterL+1) limiterR=limiterL+1; } } if(flag) { slider--; if(slider==limiterL) { flag=false; limiterL++; if(limiterL>=limiterR-1) limiterL=limiterR-1; } } } }

→ تحقق هنا

شاكر فرز حسب الاختيار
أضف إلى فرز الفقاعة مع المحدد الأيمن المحدد الأيسر. عند كل تحول لشريط التمرير إلى اليمين ، نتحقق من (المبادلة) ، وهو أكبر - العنصر أو المحدد الحالي

 if(mods[slider-1].rectHight<mods[limiterL-1].rectHight){ vTemp= mods[slider-1].rectHight; mods[slider-1].rectHight=mods[limiterL-1].rectHight; mods[limiterL-1].rectHight=vTemp; }

عندما يصل شريط التمرير إلى المحدد المحدد R ، يتحرك المحدد الأيمن خطوة واحدة إلى اليسار ، يتحرك المحدد الأيسر خطوة واحدة إلى اليمين ، يعود شريط التمرير إلى المحدد الأيسر

 if(slider>=limiterR){ limiterL++; slider=limiterL; limiterR--; }

→ تحقق هنا

PS هذا هو المكان الذي يتم فيه وصف أحد التطبيقات التي تجعل دراسة الخوارزميات وهياكل البيانات أكثر إثارة للاهتمام .
تصور آخر لعدد من الخوارزميات وهياكل البيانات.
تشير هذه المقالة إلى موقع آخر حيث يمكنك معرفة كيفية فرز البيانات حسب خوارزميات مختلفة.
يعطي هذا المقال تقييمًا لتعقيد فرز الفقاعات.
يمكن قراءة المزيد حول تقييم التعقيد هنا ، هنا ، هنا ، هنا .

مقارنة خوارزميات فرز الصرف

فرز فقاعة

ترتيب بكسل

المحدد والعلم

فرز سريع

قزم فرز

الغريب الفرز

فرز فرشاة الشعر

شاكر الفرز

More articles: