يعد تعلم خوارزميات البحث والفرز طريقة رائعة لتحسين مهارات حل المشكلات لديك، ستساعدك أيضًا هذه الخوارزميات على كتابة تعليمات برمجية ذات أداء أفضل.
ما هي خوارزميات البحث في الجافا سكريبت
تُستخدم خوارزميات البحث لاسترداد بعض المعلومات المخزنة في بنية البيانات، على سبيل المثال، يمكننا البحث في مصفوفة بنية البيانات عن القيمة (8) بعض المعلومات، وعادةً ستعرض خوارزمية البحث موضع القيمة التي تم العثور عليها، أو إذا لم يتم العثور عليها، فستعيد (-1)، فيما يلي أهم خوارزميات البحث:
1. البحث الخطي Linear Search
البحث الخطي هو خوارزمية بحث شائعة جدًا؛ يتم تنفيذها باستخدام طرق (JavaScript) المضمنة في (() indexOf()، includes، و()find، و() findIndex)، كما يعد البحث الخطي أيضًا مباشرًا جدًا وسهل التنفيذ، حيث أنه ما عليك سوى إجراء حلقة حول كل عنصر في المصفوفة والتوقف إذا كان هذا العنصر يساوي القيمة المستهدفة، ثم قم بإرجاع فهرس هذا العنصر.
2. البحث الثنائي Binary Search
يمكن استخدام البحث الثنائي للبحث عن القيم في مصفوفات (SORTED) فقط، مثل [1 ، 2 ، 3 ، 6 ، 9]، ومن الأفضل أداء البحث الخطي عن أي شيء آخر غير المصفوفات الصغيرة أقل من (10) عناصر، حيث يكون أكثر أداءً من البحث الخطي عندما تكون المصفوفة التي تم فرزها كبيرة، وتحدث أفضل حالة تعقيد للبحث الثنائي عندما تكون القيمة التي نبحث عنها في منتصف المصفوفة، ستكون هناك حاجة إلى مقارنة واحدة فقط، بغض النظر عن حجم المصفوفة، لذلك في أحسن الأحوال يتم تشغيل (Binary Search) في وقت ثابت يعني (O (1)).
ما هي خوارزميات الفرز في الجافا سكريبت
تُستخدم خوارزميات الفرز لتنظيم مجموعة من العناصر بترتيب معين، عادةً ما يكون ترتيب الفرز معجميًا، على سبيل المثال أبجدي (a-z) أو عددي (0-9)، فيما يلي أنواع خوارزميات الفرز:
1. خوارزمية Bubble Sort
الفرز الفقاعي عبارة عن خوارزمية فرز سهلة الفهم، حيث أنه يعمل عن طريق التكرار عبر مصفوفة ومقارنة العناصر المجاورة، ثم تبديلها إذا كانت بالترتيب الخطأ، بهذه الطريقة أكبر عدد “فقاعات” إلى الأعلى، يتكرر هذا حتى يتم فرز المصفوفة، ويحدث تعقيد أفضل حالة لـ (Bubble Sort) عندما يتم فرز المصفوفة تقريبًا وتتطلب تشغيلًا واحدًا فقط مع المقايضات، حيث أنه لن تتطلب عملية التشغيل التالية أي مقايضات، لذلك سيعرف تصنيف الفقاعات أن المصفوفة مرتبة ويمكنها إرجاعها.
2. خوارزمية الفرز بالاختيار Selection Sort
يشبه (Selection Sort) الفرز الفقاعي، ولكن بدلاً من القيم الأكبر “تتدفق” إلى الأعلى، يتم تحديد القيم الأصغر ووضعها في البداية، حيث يعمل (Selection Sort) عن طريق صعود المصفوفة واختيار الحد الأدنى للقيمة، ثم يتم نقل القيمة الدنيا إلى بداية المصفوفة، حيث يصبح الجانب الأيسر من المصفوفة مرتبًا بشكل أكبر في نهاية كل تمريرة عبر المصفوفة، حتى يتم فرز المصفوفة بأكملها.
3. الترتيب بالإدراج Insertion Sort
الترتيب بالإدراج هو خوارزمية فرز بديهية أخرى، كما أن لديها بعض حالات الاستخدام المثيرة للاهتمام، حيث تعمل خوارزمية الترتيب بالإدراج من خلال مقارنة عنصر بالعناصر الموجودة على يساره، حتى يصل إلى عنصر أصغر منه؛ ثم يتم إدخال العنصر أمام العنصر الأصغر.
في مصطلحات علوم الكمبيوتر، يُعرف (Insertion Sort) باسم “خوارزمية عبر الإنترنت“، مما يعني أنه يمكنه معالجة المدخلات قطعة تلو الأخرى بطريقة تسلسلية، أي بالترتيب الذي يتم فيه تغذية الإدخال إلى الخوارزمية، دون الحصول على كامل المدخلات المتاحة منذ البداية، مثال على ذلك هو الأشخاص الذين يرسلون البيانات إلينا مباشرة ونحتاج إلى فرز هذه البيانات في أي لحظة، سيتم بالفعل فرز الجانب الأيسر من المصفوفة بحيث يمكن لأي بيانات جديدة أن تجد مكانها بسرعة.
4. الترتيب بالدمج Merge Sort
تعد (Merge Sort) أحد أكثر خوارزميات الفرز كفاءة، حيث أنها خوارزمية الأسلوب التي تستغل حقيقة أن جميع المصفوفات التي يبلغ طولها صفرًا أو واحد مرتبة بشكل طبيعي، وتقسم (Merge Sort) أولاً مصفوفة الإدخال حتى نحصل على مصفوفات من صفر أو عنصر واحد، وهذه هي “الحالة الأساسية”.
وعلى عكس بعض خوارزميات الترتيب الأخرى، مثل: الترتيب الفقاعي أو الإدراج، لا يهتم (Merge Sort) بما إذا كانت البيانات قد تم فرزها تقريبًا أم لا، فإنها ستؤدي دائمًا نفس الأداء بغض النظر، حيث إنه سينفّذ نظام (Merge Sort) جميع الخطوات من تقسيم المصفوفة لأعلى، إلى دمجها معًا مرة أخرى، بغض النظر عما إذا كانت مصفوفة الإدخال مرتبة أم “عشوائية” أو عكسية.
5. الترتيب السريع Quick Sort
الترتيب السريع هو خوارزمية فرز شائعة وفعالة، ومع ذلك فهي أيضًا واحدة من أقل الحلول من حيث سهولة، فيما يلي نظرة عامة حول كيفية عمل “الترتيب السريع”:
- حدد المحور (pivot)، يمكن أن يكون هذا أي عنصر في المصفوفة.
- نقوم بعمل حلقة فوق المصفوفة ونضع كل الأرقام الأصغر من المحور على يسار المحور، وجميع الأرقام أكبر من المحور على يمين المحور، سيكون المحور بعد ذلك في مكانه الصحيح في المصفوفة.
- هناك بعد ذلك مصفوفة فرعية على يسار المحور، ومصفوفة فرعية على يمين المحور، نحن الآن بحاجة إلى فرز هذه المصفوفات، لذلك يتم اختيار المحور في كل من هذه المصفوفات ووضعه في مكانه الصحيح.
- تتكرر هذه العملية حتى يتم فرز المصفوفتين الفرعيتين اليمنى واليسرى، ويكون كل رقم في مكانه الصحيح.
يعتبر “الترتيب السريع” جيدًا جدًا في فرز المصفوفات الكبيرة، ولكن غالبًا ما يكون “الترتيب بالإدراج” خيارًا أفضل للمصفوفات الصغيرة، بمعرفة ذلك يمكنك إجراء تحسين، حيث يمكن التحقق من طول مصفوفة الإدخال قبل الفرز؛ إذا كانت المصفوفة صغيرة، فقم بإجراء “الترتيب بالإدراج”؛ إذا كان المصفوفة كبيرة، فقم بإجراء “الترتيب السريع”.
6. الترتيب بالجذر Radix Sort
(Radix Sort) هي خوارزمية فرز فريدة، حيث تقوم بفرز مصفوفة دون إجراء أي مقارنات بين العناصر، كما يستغل (Radix Sort) حقيقة أن حجم الرقم مشفر بعدد الأرقام، فكلما زاد عدد الأرقام يعني عددًا أكبر، حيث يمكن أن يكون كل رقم في أي رقم واحدًا من عشر قيم: (0-9)، لذلك، نحتاج إلى إنشاء عشر مجموعات، واحدة لكل قيمة.
ومع ذلك، فإن (Radix Sort) ليس شائعًا مثل: الترتيب بالدمج أو الترتيب السريع نظرًا لكونه أكثر “تخصصًا”، حيث يمكنك التعامل مع الأعداد الصحيحة والعائمة والأرقام في (Merge / Quick Sort) وسيقومون بفرزها بدون مشكلة، لكن يجب تعديل ترتيب (Radix Sort) إذا أردنا.
