++C برمجة خوارزميات هياكل بيانات

الفرز في لغة ++C (Sort (C++

- C#, STL, خوارزمية, فرز

مقدمة إلى دالة الفرز

تعتبر دالة sort أداة قوية للمطورين، إذ تسهل عملية ترتيب البيانات بكفاءة عالية. يمكن استخدامها مع أنواع البيانات المختلفة، سواء كانت أنواع بيانات مدمجة (built-in data types) مثل الأعداد الصحيحة والأرقام العشرية، أو أنواع بيانات معرفة من قبل المستخدم (user-defined data types). بالإضافة إلى ذلك، يمكن تخصيص سلوك الفرز عن طريق تمرير دالة مقارنة (comparison function) أو كائن دالة (function object) لتحديد كيفية مقارنة العناصر ببعضها البعض.

بناء الجملة

تأخذ دالة sort بشكل أساسي مُدخلين (inputs):

  1. المؤشر الأول (First Iterator): يشير إلى بداية النطاق (range) الذي سيتم فرزه.
  2. المؤشر الثاني (Second Iterator): يشير إلى نهاية النطاق الذي سيتم فرزه.

هناك أيضًا نسخة أخرى من الدالة تأخذ مُدخلاً ثالثًا اختياريًا:

  1. دالة المقارنة (Comparison Function): دالة تحدد ترتيب العناصر.

إليك مثال على بناء الجملة الأساسي:


#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9, 4};

    // فرز الأرقام بترتيب تصاعدي
    std::sort(numbers.begin(), numbers.end());

    // ...
    return 0;
}

كيفية عمل دالة الفرز

تستخدم دالة sort في ++C خوارزمية هجينة تسمى IntroSort. هذه الخوارزمية تجمع بين ثلاث خوارزميات فرز مختلفة لضمان الأداء الأمثل في جميع الظروف:

  • الفرز السريع (Quicksort): هي خوارزمية فعالة جدًا في المتوسط، ولكنها قد تتدهور إلى أداء O(n^2) في أسوأ الحالات.
  • الفرز التراكمي (Heapsort): هي خوارزمية تضمن أداء O(n log n) في جميع الحالات، ولكنها قد تكون أبطأ من الفرز السريع في المتوسط.
  • الفرز بالإدراج (Insertion Sort): هي خوارزمية فعالة للمجموعات الصغيرة أو المجموعات شبه المرتبة.

تعمل IntroSort عن طريق البدء بالفرز السريع. إذا تجاوز عمق الاستدعاء العودي (recursion depth) حدًا معينًا، فإنها تنتقل إلى الفرز التراكمي لمنع أسوأ الحالات من الفرز السريع. بمجرد أن يصبح حجم القسم صغيرًا بما فيه الكفاية، فإنها تستخدم الفرز بالإدراج لتحسين الأداء.

استخدامات دالة الفرز

تستخدم دالة sort في مجموعة واسعة من التطبيقات، بما في ذلك:

  • ترتيب البيانات في قاعدة البيانات: يمكن استخدام sort لترتيب سجلات قاعدة البيانات بناءً على معيار معين.
  • البحث عن العناصر: يمكن استخدام sort لترتيب قائمة من العناصر قبل البحث عنها باستخدام خوارزميات بحث فعالة مثل البحث الثنائي (binary search).
  • تحسين الأداء: في بعض الحالات، يمكن أن يؤدي ترتيب البيانات إلى تحسين أداء الخوارزميات الأخرى.
  • تطبيقات الرسوميات: تستخدم في ترتيب الأشكال الهندسية بناءً على العمق أو المسافة من الكاميرا.
  • تطبيقات الذكاء الاصطناعي: تستخدم في ترتيب البيانات قبل تدريب نماذج التعلم الآلي.

أمثلة عملية

مثال 1: فرز متجه من الأعداد الصحيحة


#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9, 4};

    std::cout << "قبل الفرز: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    std::sort(numbers.begin(), numbers.end());

    std::cout << "بعد الفرز: ";
    for (int num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

مثال 2: فرز مصفوفة من السلاسل النصية


#include <iostream>
#include <algorithm>
#include <vector>
#include <string>

int main() {
    std::vector<std::string> names = {"Charlie", "Alice", "Bob", "David"};

    std::cout << "قبل الفرز: ";
    for (const std::string& name : names) {
        std::cout << name << " ";
    }
    std::cout << std::endl;

    std::sort(names.begin(), names.end());

    std::cout << "بعد الفرز: ";
    for (const std::string& name : names) {
        std::cout << name << " ";
    }
    std::cout << std::endl;

    return 0;
}

مثال 3: استخدام دالة مقارنة مخصصة لفرز كائنات


#include <iostream>
#include <algorithm>
#include <vector>

struct Person {
    std::string name;
    int age;
};

bool compareByAge(const Person& a, const Person& b) {
    return a.age < b.age;
}

int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35}
    };

    std::cout << "قبل الفرز: " << std::endl;
    for (const Person& person : people) {
        std::cout << person.name << ": " << person.age << std::endl;
    }

    std::sort(people.begin(), people.end(), compareByAge);

    std::cout << "بعد الفرز: " << std::endl;
    for (const Person& person : people) {
        std::cout << person.name << ": " << person.age << std::endl;
    }

    return 0;
}

دوال المقارنة المخصصة

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

  1. دالة عادية (Regular Function): كما رأينا في المثال السابق.
  2. كائن دالة (Function Object) أو Functor: وهو كائن من فئة تقوم بتحميل عامل التشغيل ().

مثال على استخدام كائن دالة:


#include <iostream>
#include <algorithm>
#include <vector>

struct Person {
    std::string name;
    int age;
};

struct ComparePeopleByAge {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age;
    }
};

int main() {
    std::vector<Person> people = {
        {"Alice", 30},
        {"Bob", 25},
        {"Charlie", 35}
    };

    std::sort(people.begin(), people.end(), ComparePeopleByAge());

    // ...
    return 0;
}

التعقيد الزمني والمكاني

  • التعقيد الزمني (Time Complexity): متوسط وأسوأ حالة هو O(n log n).
  • التعقيد المكاني (Space Complexity): عادةً ما يكون O(log n) بسبب الاستدعاء العودي، ولكن يمكن أن يكون O(1) في بعض التنفيذات.

اعتبارات الأداء

لتحقيق أفضل أداء باستخدام دالة sort، ضع في اعتبارك ما يلي:

  • اختر دالة مقارنة فعالة: إذا كنت تستخدم دالة مقارنة مخصصة، فتأكد من أنها فعالة قدر الإمكان. يمكن أن تؤثر دالة المقارنة البطيئة بشكل كبير على أداء الفرز.
  • تجنب الفرز غير الضروري: لا تفرز البيانات إلا إذا كان ذلك ضروريًا. يمكن أن يكون الفرز عملية مكلفة.
  • استخدم الحاويات المناسبة: يمكن أن يؤثر نوع الحاوية التي تستخدمها على أداء الفرز. على سبيل المثال، عادةً ما يكون الفرز في std::vector أسرع من الفرز في std::list.

بدائل لدالة الفرز

على الرغم من أن دالة sort هي أداة قوية، إلا أن هناك بدائل أخرى يمكنك استخدامها، اعتمادًا على احتياجاتك:

  • std::stable_sort: تحافظ على الترتيب النسبي للعناصر المتساوية.
  • std::partial_sort: تقوم بفرز عدد معين فقط من العناصر في النطاق.
  • std::nth_element: تضع العنصر النوني في مكانه الصحيح في النطاق الذي تم فرزه.
  • خوارزميات الفرز المخصصة: إذا كان لديك متطلبات أداء محددة جدًا، فقد تحتاج إلى تنفيذ خوارزمية الفرز الخاصة بك.

أفضل الممارسات

  • استخدم std::sort بشكل افتراضي: إنها عادةً الخيار الأفضل لفرز البيانات في ++C.
  • فكر في استخدام std::stable_sort إذا كان الحفاظ على الترتيب النسبي للعناصر المتساوية أمرًا مهمًا.
  • استخدم std::partial_sort أو std::nth_element إذا كنت بحاجة فقط إلى فرز جزء من البيانات.
  • قم بتحليل أداء الفرز الخاص بك بعناية إذا كان الأداء مهمًا.

الأخطاء الشائعة

  • تمرير مؤشرات غير صالحة إلى sort: تأكد من أن المؤشرات التي تمررها إلى sort صالحة وتشير إلى نطاق صالح من البيانات.
  • استخدام دالة مقارنة غير متناسقة: يجب أن تكون دالة المقارنة الخاصة بك متناسقة، مما يعني أنه إذا كانت compare(a, b) تُرجع true، فلا يجب أن تُرجع compare(b, a) أيضًا true.
  • محاولة الفرز في حاوية غير قابلة للتعديل: لا يمكنك الفرز في حاوية غير قابلة للتعديل، مثل std::array التي تم تعريفها على أنها const.

خاتمة

تُعد دالة sort أداة أساسية في ++C لفرز البيانات بكفاءة ومرونة. فهم كيفية عملها وكيفية استخدامها بشكل صحيح يمكن أن يحسن بشكل كبير من أداء تطبيقاتك. من خلال تخصيص دالة المقارنة، يمكنك تكييفها مع أنواع بيانات مختلفة ومتطلبات فرز محددة. تذكر دائمًا مراعاة اعتبارات الأداء واختيار البديل المناسب إذا لزم الأمر.

المراجع

مقالات مرتبطة