شرح خوارزمية الفرز بالعد
الفرز بالعد هي خوارزمية فرز غير مقارنة تقوم بترتيب الأعداد الصحيحة عن طريق عد عدد مرات ظهور كل قيمة في مصفوفة الإدخال. بدلاً من مقارنة العناصر ببعضها البعض، تستخدم مصفوفة عد لتسجيل التكرارات ثم تعيد بناء النتيجة المرتبة.
يمكن أن يكون الفرز بالعد سريعًا جدًا عندما لا يكون نطاق القيم كبيرًا جدًا. تعقيدها الزمني هو O(n + k)، حيث n هو عدد العناصر و k هو نطاق القيم المحتملة. هذا يجعلها مختلفة عن الخوارزميات القائمة على المقارنة مثل الفرز الفقاعي (Bubble Sort)، وفرز التحديد (Selection Sort)، وفرز الإدراج (Insertion Sort)، وفرز الدمج (Merge Sort)، والفرز السريع (Quicksort).
مقدمة
تعمل معظم خوارزميات الفرز للمبتدئين عن طريق مقارنة القيم. الفرز الفقاعي يقارن العناصر المتجاورة، فرز التحديد يبحث عن أصغر قيمة، فرز الإدراج يقارن القيمة الحالية بالقيم السابقة، والفرز السريع يقارن العناصر بمحور.
يستخدم الفرز بالعد فكرة مختلفة. إنه لا يسأل ما إذا كان عنصر ما أكبر أو أصغر من عنصر آخر عدة مرات. بدلاً من ذلك، فإنه يعد عدد مرات ظهور كل قيمة، ثم يستخدم تلك الأعداد لوضع القيم بترتيب فرز.
وهذا يجعل الفرز بالعد مفيدًا بشكل خاص عند فرز الأعداد الصحيحة ضمن نطاق محدود، مثل درجات الامتحانات من 0 إلى 100، الأعمار، المعرفات الصغيرة، التقييمات، أو الفئات الرقمية المتكررة.
ما هو الفرز بالعد؟
الفرز بالعد هي خوارزمية فرز مصممة للقيم الصحيحة. تعمل عن طريق إنشاء مصفوفة إضافية تسمى مصفوفة العد أو مصفوفة التكرار. يمثل كل فهرس في مصفوفة العد هذه قيمة محتملة من مصفوفة الإدخال.
لكل رقم في مصفوفة الإدخال، تزيد الخوارزمية عد هذا الرقم. بعد عد جميع القيم، تعيد الخوارزمية بناء المصفوفة المرتبة عن طريق وضع كل قيمة وفقًا لعدد مرات ظهورها.
الفكرة الرئيسية بسيطة:
العثور على نطاق القيم في المصفوفة.
إنشاء مصفوفة عد.
عد عدد مرات ظهور كل قيمة.
استخدام مصفوفة العد لإعادة بناء الناتج المرتب.
يطلق على الفرز بالعد اسم “العد” لأن عد التكرارات هو العملية الرئيسية للخوارزمية.
لماذا الفرز بالعد مختلف؟
يختلف الفرز بالعد عن العديد من خوارزميات الفرز الشائعة لأنه لا يعتمد على المقارنة. هذا يعني أنه لا يقوم بالفرز عن طريق مقارنة أزواج من العناصر بشكل متكرر.
على سبيل المثال، يطرح الفرز السريع أسئلة مثل:
Is this value less than or equal to the pivot?يطرح فرز الإدراج أسئلة مثل:
Is the previous value greater than the current value?يطرح الفرز بالعد سؤالاً مختلفًا:
How many times did this value appear?يسمح هذا الاختلاف للفرز بالعد بتحقيق أداء شبيه بالخطي عندما يكون نطاق القيم صغيرًا بما فيه الكفاية.
متى يعمل الفرز بالعد بشكل أفضل؟
يعمل الفرز بالعد بشكل أفضل عندما تكون قيم الإدخال أعدادًا صحيحة ونطاق القيم المحتملة محدودًا.
على سبيل المثال، الفرز بالعد مناسب لـ:
فرز درجات الامتحانات بين 0 و 100.
فرز الأعمار ضمن نطاق صغير.
فرز تقييمات المنتجات من 1 إلى 5.
فرز معرفات الفئات الصغيرة.
فرز القيم الصحيحة المتكررة.
الفرز بالعد غير مناسب عندما يكون النطاق كبيرًا جدًا مقارنة بعدد العناصر. على سبيل المثال، فرز 10 أرقام فقط حيث يمكن أن تتراوح القيم بين 0 و 1,000,000 قد يهدر الكثير من الذاكرة.
كيف يعمل الفرز بالعد خطوة بخطوة
يمكن شرح الفرز بالعد باستخدام نسخة بسيطة أولاً. هذه النسخة تعد التكرارات ثم تعيد بناء المصفوفة المرتبة مباشرة.
تتبع الخوارزمية هذه الخطوات:
ابحث عن القيمة القصوى في مصفوفة الإدخال.
أنشئ مصفوفة عد بحجم أقصى + 1.
قم بتهيئة جميع قيم العد إلى الصفر.
تصفح مصفوفة الإدخال وقم بعد كل قيمة.
تصفح مصفوفة العد واكتب كل قيمة مرة أخرى وفقًا لتكرارها.
هذه النسخة البسيطة سهلة الفهم وتعمل جيدًا عندما نحتاج فقط إلى أرقام مرتبة. تستخدم نسخة مستقرة أعدادًا تراكمية ومصفوفة إخراج، والتي سنشرحها لاحقًا.
مثال التشغيل اليدوي
دعنا نرتب المصفوفة التالية يدويًا باستخدام الفرز بالعد:
[4, 2, 2, 8, 3, 3, 1]أصغر قيمة هي 1 وأكبر قيمة هي 8. للنسخة البسيطة، ننشئ مصفوفة عد من الفهرس 0 إلى 8.
Value: 0 1 2 3 4 5 6 7 8
Count: 0 0 0 0 0 0 0 0 0الخطوة 1: عد التكرارات
الآن نقرأ كل قيمة من مصفوفة الإدخال ونزيد عددها.
القيمة الأولى هي 4:
Value: 0 1 2 3 4 5 6 7 8
Count: 0 0 0 0 1 0 0 0 0القيمة التالية هي 2:
Value: 0 1 2 3 4 5 6 7 8
Count: 0 0 1 0 1 0 0 0 0القيمة التالية هي 2 مرة أخرى:
Value: 0 1 2 3 4 5 6 7 8
Count: 0 0 2 0 1 0 0 0 0القيمة التالية هي 8:
Value: 0 1 2 3 4 5 6 7 8
Count: 0 0 2 0 1 0 0 0 1القيمة التالية هي 3:
Value: 0 1 2 3 4 5 6 7 8
Count: 0 0 2 1 1 0 0 0 1القيمة التالية هي 3 مرة أخرى:
Value: 0 1 2 3 4 5 6 7 8
Count: 0 0 2 2 1 0 0 0 1القيمة النهائية هي 1:
Value: 0 1 2 3 4 5 6 7 8
Count: 0 1 2 2 1 0 0 0 1هذا يعني:
القيمة 1 تظهر مرة واحدة.
القيمة 2 تظهر مرتين.
القيمة 3 تظهر مرتين.
القيمة 4 تظهر مرة واحدة.
القيمة 8 تظهر مرة واحدة.
الخطوة 2: إعادة بناء المصفوفة المرتبة
الآن نقرأ مصفوفة العد من اليسار إلى اليمين. لكل فهرس، نكتب هذا الفهرس في النتيجة بعدد مرات تكراره.
الفهرس 0 له عد 0، لذا لا نكتب شيئًا.
الفهرس 1 له عد 1، لذا نكتب 1:
[1]الفهرس 2 له عد 2، لذا نكتب 2 مرتين:
[1, 2, 2]الفهرس 3 له عد 2، لذا نكتب 3 مرتين:
[1, 2, 2, 3, 3]الفهرس 4 له عد 1، لذا نكتب 4:
[1, 2, 2, 3, 3, 4]الفهارس 5، 6، و 7 لها عد 0، لذا لا نكتب شيئًا.
الفهرس 8 له عد 1، لذا نكتب 8:
[1, 2, 2, 3, 3, 4, 8]المصفوفة النهائية المرتبة
[1, 2, 2, 3, 3, 4, 8]يوضح هذا التشغيل اليدوي الفكرة الأساسية للفرز بالعد. قامت الخوارزمية بفرز المصفوفة عن طريق عد القيم، وليس عن طريق مقارنتها ببعضها البعض.
خطوات خوارزمية الفرز بالعد
يمكن وصف خوارزمية الفرز بالعد البسيطة كالتالي:
ابحث عن القيمة القصوى في المصفوفة.
أنشئ مصفوفة عد من 0 إلى القيمة القصوى.
عد تكرارات كل قيمة إدخال.
أنشئ مصفوفة نتائج فارغة.
لكل قيمة في مصفوفة العد، ألحق القيمة وفقًا لعددها.
أعد النتيجة المرتبة.
هذه النسخة سهلة التنفيذ، لكنها ليست مستقرة دائمًا عند فرز الكائنات أو السجلات. للفرز المستقر، نحتاج إلى أعداد تراكمية.
شفرة زائفة للفرز بالعد البسيط
countingSort(array):
max = find maximum value in array
count = array of size max + 1 filled with 0
for each value in array:
count[value] = count[value] + 1
result = empty array
for value from 0 to max:
while count[value] > 0:
append value to result
count[value] = count[value] - 1
return resultتعمل هذه الشفرة الزائفة للأعداد الصحيحة غير السالبة. إذا كانت المصفوفة تحتوي على أعداد سالبة، فنحتاج إلى استخدام إزاحة (offset)، والتي سيتم شرحها لاحقًا.
مثال الفرز بالعد في PHP
فيما يلي تطبيق PHP بسيط للفرز بالعد للأعداد الصحيحة غير السالبة:
<?php
function countingSort(array $numbers): array
{
if ($numbers === []) {
return [];
}
$max = max($numbers);
$count = array_fill(0, $max + 1, 0);
foreach ($numbers as $number) {
$count[$number]++;
}
$sorted = [];
for ($value = 0; $value <= $max; $value++) {
while ($count[$value] > 0) {
$sorted[] = $value;
$count[$value]--;
}
}
return $sorted;
}
$numbers = [4, 2, 2, 8, 3, 3, 1];
print_r(countingSort($numbers));سيكون الناتج:
Array
(
[0] => 1
[1] => 2
[2] => 2
[3] => 3
[4] => 3
[5] => 4
[6] => 8
)هذا التنفيذ مباشر وسهل القراءة. يقوم بعد كل رقم، ثم ينشئ النتيجة المرتبة بناءً على مصفوفة التكرار.
مثال الفرز بالعد في JavaScript
فيما يلي نفس الخوارزمية مطبقة في JavaScript:
function countingSort(numbers) {
if (numbers.length === 0) {
return [];
}
const max = Math.max(...numbers);
const count = new Array(max + 1).fill(0);
for (const number of numbers) {
count[number]++;
}
const sorted = [];
for (let value = 0; value <= max; value++) {
while (count[value] > 0) {
sorted.push(value);
count[value]--;
}
}
return sorted;
}
const numbers = [4, 2, 2, 8, 3, 3, 1];
console.log(countingSort(numbers));سيكون الناتج:
[1, 2, 2, 3, 3, 4, 8]تتبع نسخة JavaScript نفس المنطق المستخدم في نسخة PHP. تخزن مصفوفة العد التكرارات، ويتم إعادة بناء المصفوفة المرتبة من قيم العد.
الفرز بالعد المستقر
النسخة البسيطة من الفرز بالعد كافية لفرز الأرقام العادية. ومع ذلك، عند فرز السجلات أو الكائنات، تصبح الاستقرارية مهمة.
تحافظ خوارزمية الفرز المستقرة على الترتيب النسبي للعناصر المتساوية. على سبيل المثال، تخيل أن لدينا طلابًا بدرجات:
Ali: 90
Sara: 80
Omar: 90
Lina: 70إذا قمنا بالفرز حسب الدرجة وكانت الخوارزمية مستقرة، فيجب أن يظهر علي قبل عمر لأن كلاهما لديه نفس الدرجة وظهر علي أولاً في القائمة الأصلية.
يستخدم الفرز بالعد المستقر أعدادًا تراكمية لتحديد الموضع النهائي لكل عنصر.
ما هو العد التراكمي؟
يخبرنا العد التراكمي بعدد العناصر التي هي أقل من أو تساوي قيمة معينة. يتم إنشاؤه عن طريق إضافة كل قيمة عد إلى قيمة العد السابقة.
لننظر إلى مصفوفة التكرار من المثال اليدوي:
Value: 0 1 2 3 4 5 6 7 8
Count: 0 1 2 2 1 0 0 0 1الآن نحولها إلى عد تراكمي:
Value: 0 1 2 3 4 5 6 7 8
Cumulative: 0 1 3 5 6 6 6 6 7هذا يعني:
يوجد عنصر واحد أقل من أو يساوي 1.
يوجد 3 عناصر أقل من أو تساوي 2.
يوجد 5 عناصر أقل من أو تساوي 3.
يوجد 7 عناصر أقل من أو تساوي 8.
يساعد العد التراكمي الخوارزمية في معرفة الموضع النهائي الصحيح لكل قيمة في مصفوفة الإخراج.
تشغيل يدوي للفرز بالعد المستقر
دعنا نستخدم نفس الإدخال:
[4, 2, 2, 8, 3, 3, 1]عدد التكرار هو:
Value: 0 1 2 3 4 5 6 7 8
Count: 0 1 2 2 1 0 0 0 1العد التراكمي هو:
Value: 0 1 2 3 4 5 6 7 8
Cumulative: 0 1 3 5 6 6 6 6 7الآن ننشئ مصفوفة إخراج بنفس حجم الإدخال:
Output: [_, _, _, _, _, _, _]للحفاظ على استقرار الفرز، نقوم بمعالجة المصفوفة الأصلية من اليمين إلى اليسار.
القيمة الأخيرة هي 1. العد التراكمي للقيمة 1 هو 1، لذا تذهب 1 إلى الفهرس 0. ثم نقلل عد 1.
Output: [1, _, _, _, _, _, _]القيمة التالية من اليمين هي 3. العد التراكمي للقيمة 3 هو 5، لذا تذهب 3 إلى الفهرس 4. ثم نقلل عد 3.
Output: [1, _, _, _, 3, _, _]القيمة التالية هي 3 مرة أخرى. العد التراكمي للقيمة 3 الآن هو 4، لذا تذهب هذه القيمة 3 إلى الفهرس 3.
Output: [1, _, _, 3, 3, _, _]القيمة التالية هي 8. العد التراكمي للقيمة 8 هو 7، لذا تذهب 8 إلى الفهرس 6.
Output: [1, _, _, 3, 3, _, 8]القيمة التالية هي 2. العد التراكمي للقيمة 2 هو 3، لذا تذهب 2 إلى الفهرس 2.
Output: [1, _, 2, 3, 3, _, 8]القيمة التالية هي 2 مرة أخرى. العد التراكمي للقيمة 2 الآن هو 2، لذا تذهب هذه القيمة 2 إلى الفهرس 1.
Output: [1, 2, 2, 3, 3, _, 8]القيمة النهائية هي 4. العد التراكمي للقيمة 4 هو 6، لذا تذهب 4 إلى الفهرس 5.
Output: [1, 2, 2, 3, 3, 4, 8]نتيجة الفرز بالعد المستقر هي:
[1, 2, 2, 3, 3, 4, 8]بالنسبة للأرقام العادية، تبدو النتيجة هي نفسها النسخة البسيطة. يصبح الاختلاف مهمًا عندما تنتمي القيم المتساوية إلى سجلات أو كائنات أكبر.
شفرة زائفة للفرز بالعد المستقر
stableCountingSort(array):
max = find maximum value in array
count = array of size max + 1 filled with 0
output = array of same size as input
for each value in array:
count[value] = count[value] + 1
for i from 1 to max:
count[i] = count[i] + count[i - 1]
for i from length(array) - 1 down to 0:
value = array[i]
position = count[value] - 1
output[position] = value
count[value] = count[value] - 1
return outputهذه النسخة مستقرة لأنها تعالج الإدخال من اليمين إلى اليسار وتستخدم العد التراكمي لوضع القيم بشكل صحيح.
الفرز بالعد المستقر في PHP
فيما يلي تطبيق PHP مستقر:
<?php
function stableCountingSort(array $numbers): array
{
if ($numbers === []) {
return [];
}
$max = max($numbers);
$count = array_fill(0, $max + 1, 0);
$output = array_fill(0, count($numbers), 0);
foreach ($numbers as $number) {
$count[$number]++;
}
for ($i = 1; $i <= $max; $i++) {
$count[$i] += $count[$i - 1];
}
for ($i = count($numbers) - 1; $i >= 0; $i--) {
$value = $numbers[$i];
$position = $count[$value] - 1;
$output[$position] = $value;
$count[$value]--;
}
return $output;
}
$numbers = [4, 2, 2, 8, 3, 3, 1];
print_r(stableCountingSort($numbers));تستخدم هذه النسخة مصفوفة إخراج وأعدادًا تراكمية. وهي أكثر ملاءمة عندما يكون ترتيب العناصر المتساوية مهمًا.
الفرز بالعد المستقر في JavaScript
function stableCountingSort(numbers) {
if (numbers.length === 0) {
return [];
}
const max = Math.max(...numbers);
const count = new Array(max + 1).fill(0);
const output = new Array(numbers.length);
for (const number of numbers) {
count[number]++;
}
for (let i = 1; i <= max; i++) {
count[i] += count[i - 1];
}
for (let i = numbers.length - 1; i >= 0; i--) {
const value = numbers[i];
const position = count[value] - 1;
output[position] = value;
count[value]--;
}
return output;
}
const numbers = [4, 2, 2, 8, 3, 3, 1];
console.log(stableCountingSort(numbers));سيكون الناتج:
[1, 2, 2, 3, 3, 4, 8]هذا التنفيذ مفيد لفهم كيفية تحكم الأعداد التراكمية في المواقع النهائية.
التعامل مع الأرقام السالبة
يفترض تطبيق الفرز بالعد الأساسي أن جميع القيم هي أعداد صحيحة غير سالبة. وذلك لأن فهارس المصفوفة تبدأ عادةً من 0، ونحن نستخدم القيمة نفسها كفهرس.
إذا كان الإدخال يحتوي على أرقام سالبة، يمكننا حل المشكلة باستخدام إزاحة (offset).
على سبيل المثال:
[-3, -1, 2, 0, -1]القيمة الدنيا هي -3. يمكننا إزاحة كل قيمة عن طريق طرح القيمة الدنيا:
index = value - minإذن:
-3 يصبح الفهرس 0.
-1 يصبح الفهرس 2.
0 يصبح الفهرس 3.
2 يصبح الفهرس 5.
عند إعادة بناء النتيجة المرتبة، نحول الفهرس مرة أخرى إلى القيمة الأصلية:
value = index + minالفرز بالعد مع الأرقام السالبة في PHP
<?php
function countingSortWithNegativeNumbers(array $numbers): array
{
if ($numbers === []) {
return [];
}
$min = min($numbers);
$max = max($numbers);
$range = $max - $min + 1;
$count = array_fill(0, $range, 0);
foreach ($numbers as $number) {
$count[$number - $min]++;
}
$sorted = [];
for ($i = 0; $i < $range; $i++) {
while ($count[$i] > 0) {
$sorted[] = $i + $min;
$count[$i]--;
}
}
return $sorted;
}
$numbers = [-3, -1, 2, 0, -1];
print_r(countingSortWithNegativeNumbers($numbers));سيكون الناتج:
Array
(
[0] => -3
[1] => -1
[2] => -1
[3] => 0
[4] => 2
)تجعل تقنية الإزاحة هذه الفرز بالعد يعمل مع الأعداد الصحيحة السالبة مع الحفاظ على نفس فكرة العد.
التعقيد الزمني للفرز بالعد
يصف التعقيد الزمني كيف ينمو وقت تشغيل الخوارزمية مع زيادة حجم الإدخال. يمتلك الفرز بالعد تعقيدًا زمنيًا مختلفًا عن الخوارزميات القائمة على المقارنة لأنه يعتمد على كل من عدد العناصر ونطاق القيم.
التعقيد الزمني للفرز بالعد هو:
O(n + k)حيث:
n هو عدد العناصر في مصفوفة الإدخال.
k هو نطاق القيم المحتملة.
على سبيل المثال، إذا قمنا بفرز 1000 درجة امتحان بين 0 و 100، فإن n هو 1000 و k هو 101. هذا فعال جداً.
لماذا التعقيد الزمني للفرز بالعد هو O(n + k)
يؤدي الفرز بالعد عدة خطوات خطية:
يقوم بمسح مصفوفة الإدخال لعد القيم. تكلفة هذه العملية هي O(n).
يقوم بمسح مصفوفة العد. تكلفة هذه العملية هي O(k).
يقوم ببناء مصفوفة الإخراج. تكلفة هذه العملية هي O(n) أو O(n + k)، اعتمادًا على التنفيذ.
عند دمج هذه الخطوات، تكون النتيجة:
O(n + k)هذا أسرع من O(n log n) عندما تكون k صغيرة أو قريبة من n. ولكن إذا كانت k كبيرة جدًا، قد يصبح الفرز بالعد غير فعال.
التعقيد الزمني في أفضل الحالات
التعقيد الزمني في أفضل حالات الفرز بالعد هو:
O(n + k)لا يزال الفرز بالعد يحتاج إلى عد العناصر ومعالجة مصفوفة العد، حتى لو كان الإدخال مرتبًا بالفعل. على عكس فرز الإدراج، فإنه لا يصبح O(n) فقط لأن المصفوفة مرتبة بالفعل.
التعقيد الزمني في الحالة المتوسطة
التعقيد الزمني في الحالة المتوسطة هو أيضًا:
O(n + k)تتبع الخوارزمية نفس خطوات العد وإعادة البناء بغض النظر عن الترتيب الأصلي للإدخال.
التعقيد الزمني في أسوأ الحالات
التعقيد الزمني في أسوأ الحالات هو:
O(n + k)ومع ذلك، تصبح التكلفة العملية عالية عندما تكون k كبيرة جدًا. على سبيل المثال، فرز 10 أرقام تتراوح قيمها من 0 إلى 1,000,000 يتطلب مصفوفة عد تحتوي على 1,000,001 موضعًا.
لهذا السبب يكون الفرز بالعد فعالاً فقط عندما يكون نطاق القيم معقولاً.
التعقيد المكاني للفرز بالعد
يتطلب الفرز بالعد ذاكرة إضافية لمصفوفة العد. يتطلب الفرز بالعد المستقر أيضًا مصفوفة إخراج.
التعقيد المكاني عادةً هو:
O(n + k)حيث n هو حجم الإدخال و k هو نطاق القيم.
تحتاج مصفوفة العد إلى مساحة O(k)، وتحتاج مصفوفة الإخراج إلى مساحة O(n) في النسخة المستقرة. يمكن للنسخة البسيطة تجنب مصفوفة إخراج منفصلة في بعض التطبيقات، لكنها لا تزال تحتاج إلى مصفوفة العد.
هل الفرز بالعد مستقر؟
يمكن أن يكون الفرز بالعد مستقرًا، لكن ليس كل تطبيق مستقرًا.
النسخة البسيطة التي تعد القيم فقط وتعيد بناء المصفوفة المرتبة جيدة للأرقام العادية، لكنها لا تحافظ على ترتيب السجلات المتساوية لأنها لا تتتبع المواضع الأصلية.
تستخدم النسخة المستقرة الأعداد التراكمية وتعالج الإدخال من اليمين إلى اليسار. هذا يحافظ على الترتيب النسبي للعناصر المتساوية.
إذن الإجابة الصحيحة هي:
الفرز بالعد البسيط للأرقام: الاستقرارية ليست واضحة جدًا.
الفرز بالعد المستقر مع العد التراكمي: مستقر.
الفرز بالعد بدون تحديد موضع تراكمي للسجلات: ليس مستقرًا بالضرورة.
هل الفرز بالعد في مكانه (In-Place)؟
لا يعتبر الفرز بالعد عمومًا خوارزمية فرز في مكانه (in-place) لأنه يتطلب ذاكرة إضافية لمصفوفة العد. يتطلب الفرز بالعد المستقر أيضًا مصفوفة إخراج.
هذا يختلف عن خوارزميات مثل فرز الإدراج أو الفرز السريع في مكانه، والتي يمكنها الفرز باستخدام كمية صغيرة فقط من الذاكرة الإضافية.
يوازن الفرز بالعد بين الذاكرة والسرعة. يمكن أن يكون سريعًا جدًا، لكنه يحتاج إلى تخزين إضافي يتناسب مع نطاق القيم.
الفرز بالعد مقابل الفرز القائم على المقارنة
تقوم الخوارزميات القائمة على المقارنة بالفرز عن طريق مقارنة العناصر. تتضمن الأمثلة الفرز الفقاعي، وفرز التحديد، وفرز الإدراج، وفرز الدمج، وفرز الكومة (Heap Sort)، والفرز السريع.
يتجنب الفرز بالعد المقارنات المباشرة بين العناصر. بدلاً من ذلك، يستخدم القيم كفهارس في مصفوفة عد.
هذا الاختلاف مهم لأن خوارزميات الفرز القائمة على المقارنة لها حد أدنى نظري O(n log n) للفرز العام. يمكن أن يكون الفرز بالعد أسرع من ذلك في ظروف معينة لأنه يستخدم معلومات حول نطاق القيم.
ومع ذلك، ليس الفرز بالعد بديلاً عالميًا للفرز القائم على المقارنة. إنه يعمل بشكل جيد فقط عندما تكون البيانات قائمة على الأعداد الصحيحة والنطاق ليس كبيرًا جدًا.
الفرز بالعد مقابل الفرز السريع (Quicksort)
الفرز السريع هو خوارزمية فرز عامة قائمة على المقارنة. يمكنها فرز العديد من أنواع البيانات القابلة للمقارنة، مثل الأرقام والسلاسل النصية والتواريخ والكائنات ذات قواعد المقارنة المخصصة.
الفرز بالعد أكثر تخصصًا. يعمل بشكل أفضل للأعداد الصحيحة ضمن نطاق محدود.
التعقيد الزمني المتوسط للفرز السريع هو O(n log n).
التعقيد الزمني للفرز بالعد هو O(n + k).
الفرز السريع عادةً ما يكون في مكانه (in-place).
الفرز بالعد يحتاج إلى ذاكرة إضافية.
الفرز السريع يعمل مع القيم القابلة للمقارنة بشكل عام.
الفرز بالعد يعمل بشكل أساسي مع نطاقات الأعداد الصحيحة.
إذا كانت k صغيرة، يمكن أن يكون الفرز بالعد أسرع. إذا كانت k ضخمة أو القيم ليست أعدادًا صحيحة، فإن الفرز السريع أو وظائف الفرز المضمنة عادةً ما تكون أفضل.
الفرز بالعد مقابل فرز الأساس (Radix Sort)
يُستخدم الفرز بالعد غالبًا كروتين فرعي داخل فرز الأساس. يقوم فرز الأساس بفرز الأرقام رقمًا رقمًا، ويُستخدم الفرز بالعد عادةً لفرز كل موقع رقم بطريقة مستقرة.
هذا أحد الأسباب التي تجعل الفرز بالعد المستقر مهمًا. إذا لم يكن الفرز بالعد مستقرًا، فلن يعمل فرز الأساس بشكل صحيح في العديد من التطبيقات.
يقوم الفرز بالعد بالفرز بناءً على القيمة الكاملة عندما يكون النطاق قابلاً للإدارة. يقسم فرز الأساس الأرقام الكبيرة إلى أرقام أو أحرف ويقوم بفرزها خطوة بخطوة.
متى يجب على المطورين استخدام الفرز بالعد؟
يجب على المطورين استخدام الفرز بالعد عندما تتطابق البيانات مع نقاط قوة الخوارزمية.
الفرز بالعد مفيد عندما:
القيم هي أعداد صحيحة.
نطاق القيم صغير أو معقول.
عدد العناصر كبير مقارنة بالنطاق.
الفرز بزمن خطي مرغوب فيه.
البيانات تحتوي على العديد من القيم المتكررة.
الفرز المستقر مطلوب ويمكن استخدام العد التراكمي.
على سبيل المثال، فرز آلاف درجات الطلاب من 0 إلى 100 هو حالة استخدام قوية للفرز بالعد.
متى يجب عدم استخدام الفرز بالعد؟
لا يجب استخدام الفرز بالعد عندما يكون نطاق القيم كبيرًا جدًا مقارنة بحجم الإدخال.
على سبيل المثال، هذا الإدخال ليس حالة استخدام جيدة:
[5, 900000, 42]تحتوي المصفوفة على ثلاث قيم فقط، لكن النطاق ضخم. إنشاء مصفوفة عد تصل إلى 900000 سيهدر الذاكرة.
الفرز بالعد غير مناسب أيضًا لـ:
الأرقام العشرية (floating-point numbers) بدون تحويل.
السلاسل النصية (strings) بدون ربطها بمفاتيح عددية صحيحة.
الكائنات (objects) بدون مفتاح رقمي.
النطاقات المتفرقة الكبيرة.
الحالات التي يجب أن يكون فيها استخدام الذاكرة منخفضًا جدًا.
في هذه الحالات، يجب على المطورين عادةً استخدام وظائف الفرز المضمنة أو خوارزميات مثل الفرز السريع، وفرز الدمج، أو TimSort.
مثال عملي: فرز درجات الامتحانات
الفرز بالعد مناسب طبيعيًا لفرز درجات الامتحانات لأن الدرجات عادة ما تكون ضمن نطاق محدود، مثل 0 إلى 100.
<?php
$scores = [85, 70, 100, 70, 90, 85, 60];
$sortedScores = countingSort($scores);
print_r($sortedScores);سيكون الناتج:
Array
(
[0] => 60
[1] => 70
[2] => 70
[3] => 85
[4] => 85
[5] => 90
[6] => 100
)هذا فعال لأن النطاق من 0 إلى 100 صغير ويمكن التنبؤ به.
مثال عملي: فرز تقييمات المنتجات
حالة استخدام جيدة أخرى هي فرز تقييمات المنتجات من 1 إلى 5.
Ratings: [5, 3, 4, 5, 2, 1, 4, 3]القيم المحتملة هي فقط 1، 2، 3، 4، و 5. هذا يجعل الفرز بالعد فعالًا جدًا لأن مصفوفة العد صغيرة جدًا.
Sorted ratings: [1, 2, 3, 3, 4, 4, 5, 5]عندما يكون عدد القيم المحتملة صغيرًا، يمكن أن يكون الفرز بالعد بسيطًا وسريعًا.
أخطاء شائعة عند تطبيق الفرز بالعد
غالبًا ما يرتكب المبتدئون أخطاءً مع الفرز بالعد لأنه يستخدم فهارس المصفوفة بطريقة خاصة.
تشمل الأخطاء الشائعة ما يلي:
استخدام الفرز بالعد مع قيم غير صحيحة مباشرة.
النسيان التعامل مع المصفوفات الفارغة.
إنشاء مصفوفة عد دون التحقق من القيمة القصوى.
تجاهل الأرقام السالبة.
استخدام الكثير من الذاكرة لنطاق قيم ضخم.
الخلط بين عد التكرار والعد التراكمي.
وصف الخوارزمية بأنها مستقرة بينما لا يحافظ التطبيق على الترتيب.
أهم خطأ عملي هو استخدام الفرز بالعد عندما تكون k كبيرة جدًا. في هذه الحالة، قد تهدر الخوارزمية الذاكرة وتصبح غير فعالة.
قائمة تحقق عملية قبل استخدام الفرز بالعد
قبل اختيار الفرز بالعد، يمكن للمطورين طرح هذه الأسئلة:
هل جميع القيم أعداد صحيحة؟
ما هي القيمة الدنيا؟
ما هي القيمة القصوى؟
هل النطاق صغير بما يكفي؟
هل الإدخال كبير بما يكفي للاستفادة من الفرز بالعد؟
هل أحتاج إلى فرز مستقر؟
هل ستستخدم مصفوفة العد ذاكرة مقبولة؟
هل سيكون الفرز المضمن أبسط وأكثر أمانًا؟
إذا كان النطاق صغيرًا والقيم قائمة على الأعداد الصحيحة، يمكن أن يكون الفرز بالعد خيارًا ممتازًا. وإلا، فقد تكون خوارزمية فرز أخرى أفضل.
مزايا الفرز بالعد
يمتلك الفرز بالعد عدة مزايا عند استخدامه في الوضع الصحيح.
يمكن أن يعمل في زمن O(n + k).
لا يعتمد على مقارنات العناصر.
إنه فعال جدًا لنطاقات الأعداد الصحيحة الصغيرة.
يتعامل مع القيم المتكررة بشكل جيد.
يمكن أن يكون مستقرًا عند تنفيذه باستخدام العد التراكمي.
إنه مفيد كجزء من فرز الأساس.
تجعل هذه المزايا الفرز بالعد مهمًا في كل من تعليم الخوارزميات ومشاكل الفرز المتخصصة العملية.
عيوب الفرز بالعد
الفرز بالعد له قيود أيضًا.
إنه غير مناسب لنطاقات القيم الكبيرة.
يتطلب ذاكرة إضافية.
إنه مصمم بشكل أساسي للأعداد الصحيحة.
لا يقوم بفرز السلاسل النصية أو الأرقام العشرية أو الكائنات المعقدة مباشرة بدون ربط.
قد يهدر الذاكرة عندما يكون الإدخال متناثرًا.
إنه ليس خوارزمية فرز عامة عالمية.
الفرز بالعد قوي، ولكن فقط عندما تتناسب البيانات مع افتراضاته.
الخاتمة
الفرز بالعد هو خوارزمية فرز غير مقارنة تقوم بترتيب القيم الصحيحة عن طريق عد عدد مرات ظهور كل قيمة. تستخدم مصفوفة تكرار لتخزين الأعداد ثم تعيد بناء المصفوفة المرتبة من تلك الأعداد.
تمتلك الخوارزمية تعقيدًا زمنيًا يبلغ O(n + k)، حيث n هو عدد العناصر و k هو نطاق القيم المحتملة. هذا يجعل الفرز بالعد فعالًا جدًا عندما تكون k صغيرة أو قريبة من n.
يستخدم الفرز بالعد المستقر أعدادًا تراكمية ومصفوفة إخراج للحفاظ على الترتيب النسبي للعناصر المتساوية. هذه النسخة المستقرة مهمة بشكل خاص عند فرز السجلات أو عندما يتم استخدام الفرز بالعد داخل فرز الأساس.
الفرز بالعد ليس الخيار الأفضل لكل مشكلة فرز. يتطلب ذاكرة إضافية ويعمل بشكل أفضل مع الأعداد الصحيحة في نطاق محدود. ومع ذلك، في حالات مثل درجات الامتحانات، والتقييمات، والمعرفات الصغيرة، والفئات الرقمية المتكررة، يمكن أن يكون بسيطًا وسريعًا وفعالًا للغاية.
بالنسبة للمطورين الذين يتعلمون هياكل البيانات والخوارزميات، فإن الفرز بالعد هو خوارزمية مهمة لأنه يقدم طريقة جديدة للتفكير في الفرز. بدلاً من مقارنة العناصر، فإنه يستخدم العد، ومصفوفات التكرار، والمواقع التراكمية، والمنطق القائم على النطاق لتحقيق فرز فعال في الظروف المناسبة.
