تصنيف دمجي

تصنيف دمجي هي إحدى خوارزميات التصنيف أو ترتيب مجموعة من عناصر الرقمية تصاعديا، طورها العالم الألماني فون نيومان، تعتمد هذه الخوارزمية على مبدء «فرق تسد» ، عدد الخطوات اللازمة للخوارزمية لإنجاز المعالجة على مجموعة من مدخلات تقاس بـ N*Log N.
خطوات الخوارزمية
مفهوم خوارزمية التصنيف الدمجي يقوم على خطوات التالية:
إذا كانت المصفوفة تحتوي على عنصر واحد أو أقل فإن المصفوفه مصنفة، لأنها تحتوي على عنصر واحد وبالتالي هو مصنف.
قْسِّم كل مصفوفة غير مصنفة - أي تحتوي على أكثر من عنصر - إلى مصفوفتين.
أعد ترتيب كل مصفوفة بطريقة الاستدعاء الذاتي recursively.
ادمج كل مصفوتين (التي تم تريبها) إلى مصفوفة واحدة.
تعتمد الخوارزمية بشكل أساسي على مفهومين رئيسيين:
المفهوم الأول: هو أن المصفوفات التي تحتوي على أقل عناصر يمكن ترتيبها بشكل أسرع وتحتاج إلى خطوات أقل.
المفهوم الثاني: هو عملية دمج المصفوفات الصغيرة التي تحتوي على عناصر قليلة المرتبة لتشكيل مصفوفات أكبر مرتبة أيضا.
تطبيق من الأعلى إلى الأسفل (Top-down)
function merge_sort(list m)
// if list size is 1, consider it sorted and return it
if length(m) <= 1
return m
// else list size is > 1, so split the list into two sublists
var list left, right
var integer middle = length(m) / 2
for each x in m up to middle
add x to left
for each x in m after or equal middle
add x to right
// recursively call merge_sort() to further split each sublist
// until sublist size is 1
left = merge_sort(left)
right = merge_sort(right)
// merge the sublists returned from prior calls to merge_sort()
// and return the resulting merged sublist
return merge(left, right)
في هذا المثال، الدالة merge تدمج المجموعتين الجزئيتين اليسرى واليمنى:
function merge(left, right)
var list result
while length(left) > 0 or length(right) > 0
if length(left) > 0 and length(right) > 0
if first(left) <= first(right)
append first(left) to result
left = rest(left)
else
append first(right) to result
right = rest(right)
else if length(left) > 0
append first(left) to result
left = rest(left)
else if length(right) > 0
append first(right) to result
right = rest(right)
end while
return result
تطبيق من الأسفل إلى الأعلى (Bottom-up)
/* array A[] has the items to sort; array B[] is a work array */
BottomUpSort(int n, array A[n], array B[n])
{
int width;
/* each 1-element run in A is already "sorted". */
/* Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted */
for (width = 1; width < n; width = 2 * width)
{
int i;
/* array A is full of runs of length width */
for (i = 0; i < n; i = i + 2 * width)
{
/* merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[] */
/* or copy A[i:n-1] to B[] (if(i+width >= n) ) */
BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
}
/* now work array B is full of runs of length 2*width */
/* copy array B to array A for next iteration */
/* a more efficient implementation would swap the roles of A and B */
CopyArray(A, B, n);
/* now array A is full of runs of length 2*width */
}
}
BottomUpMerge(array A[], int iLeft, int iRight, int iEnd, array B[])
{
int i0 = iLeft;
int i1 = iRight;
int j;
/* while there are elements in the left or right lists */
for (j = iLeft; j < iEnd; j++)
{
/* if left list head exists and is <= existing right list head */
if (i0 < iRight && (i1 >= iEnd || A[i0] <= A[i1]))
{
B[j] = A[i0];
i0 = i0 + 1;
}
else
{
B[j] = A[i1];
i1 = i1 + 1;
}
}
}
مراجع
حوسبة
خوارزميات ترتيب