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