مقدمة
يعد الفرز عملية أساسية في علوم الكمبيوتر تتضمن ترتيب العناصر في ترتيب معين، مثل الترتيب العددي أو الأبجدي. وقد تم تطوير خوارزميات فرز مختلفة، ولكل منها مؤشرات الوقت والكفاءة. الفرز الزمني الخطي هو مجموعة فرعية من خوارزميات الفرز ذات ميزة كبيرة: يمكنها فرز مجموعة معينة من العناصر في وقت خطي، ويزداد وقت التشغيل خطيًا مع حجم الإدخال.
أشهر خوارزميات فرز الوقت الخطي هي الفرز التنازلي. يكون الفرز الحسابي فعالاً بشكل خاص عندما يكون نطاق عناصر الإدخال معروفًا وصغيرًا نسبيًا. وهذا يلغي الحاجة إلى مقارنة العناصر، وهي العملية الرئيسية التي تستغرق وقتًا طويلاً في العديد من خوارزميات الفرز الأخرى. باستخدام المعرفة بمجال الإدخال، يحقق الفرز الحسابي تعقيدًا زمنيًا خطيًا. يقوم الفرز الرقمي أولاً بفحص مصفوفة الإدخال لتحديد عدد كل عنصر. ثم يستخدم هذه الأرقام لحساب المواضع الصحيحة للعناصر في جدول النتائج المرتب. تتكون الخوارزمية من الخطوات التالية:
- لتحديد النطاق، حدد الحد الأدنى والحد الأقصى لقيم مصفوفة الإدخال.
- قم بإنشاء ورقة عمل تمت تهيئتها بحجم النطاق والأصفار.
- قم بالتكرار على مصفوفة الإدخال وقم بزيادة كل عنصر تم العثور عليه.
- قم بتعديل ورقة العمل عن طريق حساب المجموع التراكمي للحصول على المواضع الصحيحة لكل عنصر.
- قم بإنشاء مصفوفة إخراج بنفس حجم مصفوفة الإدخال.
- قم بتحريك مصفوفة الإدخال مرة أخرى، مع وضع كل عنصر في الموضع الصحيح في مصفوفة الإخراج بناءً على ورقة العمل.
- يحتوي جدول النتائج الآن على عناصر مرتبة.
الميزة الرئيسية للفرز التنازلي هي أنه يحقق تعقيدًا زمنيًا خطيًا قدره O(n)، مما يجعله فعالًا للغاية بالنسبة لأحجام المدخلات الكبيرة. ومع ذلك، فإن إمكانية تطبيقه تقتصر على السيناريوهات التي يكون فيها اختيار عناصر المدخلات معروفًا مسبقًا وصغيرًا نسبيًا.
من المهم ملاحظة أن خوارزميات الفرز الأخرى، مثل الفرز السريع أو الدمج، عادةً ما يكون لها تعقيد زمني قدره O(n log n)، والذي يعتبر فعالاً للعديد من التطبيقات العملية. توفر خوارزميات فرز الوقت الخطي، مثل الفرز الرقمي، بديلاً عندما تسمح بعض القيود أو خصائص الإدخال باستخدام تعقيد الوقت الخطي.
تاريخ
تتمتع خوارزميات فرز الوقت الخطي بتاريخ غني في علوم الكمبيوتر. يمكن إرجاع تطور النظام الزمني الخطي إلى منتصف القرن العشرين، وكانت مساهمات العلماء وعلماء الرياضيات كبيرة. واحدة من أقدم خوارزميات الفرز الخطي للوقت هي خوارزمية فرز الجرافة، التي اقترحها Harold H. Seward في عام 1954. يقوم فرز الجرافة بتقسيم عناصر الإدخال إلى عدد محدود من الجرافات ثم فرز كل مجموعة على حدة. تتميز هذه الخوارزمية بتعقيد زمني خطي إذا كان توزيع عناصر الإدخال موحدًا نسبيًا.
في عام 1959، قدم كينيث إي. إيفرسون خوارزمية جذرية تحقق تعقيدًا زمنيًا خطيًا. يقوم Radix بفرز العناصر حسب أرقامها أو علاماتها من الأقل أهمية إلى الأكثر أهمية. ويستخدم خوارزميات فرز قوية، مثل الفرز الرقمي أو الجرافة، لفرز العناصر في كل موقع رقمي. أصبح الفرز الجذري شائعًا في عصر البطاقات المثقوبة وأنظمة الكمبيوتر المبكرة. ومع ذلك، فإن خوارزمية الفرز الخطي الأكثر شهرة هي التعداد، الذي قدمه هارولد سيوارد وبيتر إلياس في عام 1954 وأعيد اكتشافه لاحقًا بشكل مستقل بواسطة هارولد إتش. 'بوبي' جونسون في عام 1961. وقد حظي الفرز الرقمي باهتمام كبير.
يكون هذا فعالًا بشكل خاص عندما يكون نطاق عناصر الإدخال معروفًا وصغيرًا نسبيًا. استمر تاريخ فرز الوقت الخطي مع تطور خوارزميات متخصصة أخرى. على سبيل المثال، في عام 1987، اقترح حنان سامت فرز شجرة التوزيع الثنائية، وهي خوارزمية فرز زمنية خطية للبيانات متعددة الأبعاد. على مر السنين، واصل الباحثون دراسة وتحسين خوارزميات الجدولة الخطية، مع التركيز على سيناريوهات وقيود محددة. على الرغم من أن الخوارزميات مثل الفرز السريع والدمج تستخدم على نطاق أوسع لكفاءتها في المزيد من السيناريوهات، إلا أن خوارزميات الفرز الزمني الخطي توفر بدائل قيمة عندما تسمح ظروف معينة باستغلال تعقيد الوقت الخطي. بشكل عام، يتميز تاريخ الفرز الزمني الخطي بالبحث عن خوارزميات فعالة يمكنها فرز مجموعات كبيرة من البيانات في الوقت الخطي، والتغلب على قيود خوارزميات الفرز القائمة على المقارنة. مهدت مساهمات مختلف الباحثين الطريق لتطوير وفهم تقنيات الفرز المتخصصة هذه.
أنواع فرز الوقت الخطي
هناك العديد من خوارزميات فرز الوقت الخطية المختلفة. النوعان الرئيسيان هما الخوارزميات القائمة على العد والخوارزميات القائمة على الجذر. فيما يلي أكثر خوارزميات فرز الوقت الخطي شيوعًا، مصنفة بناءً على الأنواع التالية:
الخوارزميات القائمة على العد
الخوارزميات القائمة على الجذر
مزايا فرز الوقت الخطي
توفر خوارزميات فرز الوقت الخطي، مثل الفرز الرقمي، العديد من المزايا في سيناريوهات محددة.
عيوب الفرز الزمني الخطي
على الرغم من أن خوارزميات الجدولة الخطية لها مزاياها، إلا أن لها أيضًا بعض القيود والعيوب:
عند اختيار خوارزمية الفرز، من الضروري النظر بعناية في تفاصيل البيانات المدخلة ومتطلبات مشكلة الفرز. في حين أن خوارزميات الجدولة الخطية توفر مزايا في سيناريوهات محددة، إلا أنها في بعض الأحيان تكون الخيار الأكثر ملاءمة أو كفاءة.
755 شمود
تطبيقات خوارزميات الفرز الزمني الخطي
تتميز خوارزميات الفرز الزمني الخطي بالكفاءة ولها العديد من التطبيقات في مختلف المجالات. فيما يلي بعض التطبيقات النموذجية للنظام الزمني الخطي:
تنفيذ الفرز الزمني الخطي في C++
فيما يلي مثال لبرنامج يقوم بتنفيذ فرز العد، وهو عبارة عن خوارزمية فرز خطية للوقت:
#include #include using namespace std; void countingSort(vector& arr) { // Find the maximum element in the array int max_val = *max_element(arr.begin(), arr.end()); // Create a count array to store the count of each element vector count(max_val + 1, 0); // Count the occurrences of each element for (int num : arr) { count[num]++; } // Compute the prefix sum for (int i = 1; i <count.size(); i++) { count[i] +="count[i" - 1]; } create a sorted output array vector output(arr.size()); place the elements in order for (int i="arr.size()" 1;>= 0; i--) { output[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } // Copy the sorted elements back to the original array for (int i = 0; i <arr.size(); i++) { arr[i]="output[i];" } int main() vector arr="{4," 2, 8, 3, 1}; sort the array using counting countingsort(arr); print sorted cout << 'sorted array: '; for (int num : arr) ' endl; return 0; < pre> <p> <strong>Sample Output</strong> </p> <pre> Sorted array: 1 2 2 3 3 4 8 </pre> <p>This indicates that the input array has been sorted in ascending order using the Counting Sort algorithm, resulting in the sorted array [1, 2, 2, 3, 3, 4, 8].</p> <p>In this C++ program, the counting sort function takes a reference to the vector arr and runs the counting sort routine. It finds the table's maximum value to determine the worksheet's size. It then counts each element's occurrence and calculates the worksheet's prefix sum. Then, it creates a result vector and puts the elements in order according to the worksheet. Finally, it copies the sorted elements back into the original array. In the primary function, the example array {4, 2, 2, 8, 3, 3, 1} is sorted by the enumeration sort algorithm and printed as a sorted matrix. Note that the program uses libraries to work with vectors and find the maximum element of an array using the max_element function.</p> <hr></arr.size();></count.size();> يشير هذا إلى أن مصفوفة الإدخال قد تم فرزها بترتيب تصاعدي باستخدام خوارزمية فرز العد، مما يؤدي إلى المصفوفة التي تم فرزها [1، 2، 2، 3، 3، 4، 8].
في برنامج C++ هذا، تأخذ وظيفة فرز العد مرجعًا إلى المتجه وتقوم بتشغيل روتين فرز العد. يبحث عن القيمة القصوى للجدول لتحديد حجم ورقة العمل. ثم يحسب حدوث كل عنصر ويحسب مجموع بادئة ورقة العمل. ثم يقوم بإنشاء متجه نتيجة ويرتب العناصر وفقًا لورقة العمل. وأخيرًا، يقوم بنسخ العناصر التي تم فرزها مرة أخرى إلى المصفوفة الأصلية. في الوظيفة الأساسية، يتم فرز مصفوفة المثال {4، 2، 2، 8، 3، 3، 1} بواسطة خوارزمية فرز التعداد وطباعتها كمصفوفة مرتبة. لاحظ أن البرنامج يستخدم المكتبات للعمل مع المتجهات والعثور على الحد الأقصى لعنصر المصفوفة باستخدام الدالة max_element.