في الواقع ، بالإضافة إلى مؤشر الأداء ، هناك خصائص أخرى لا تقل أهمية في كثير من الأحيان. واحد منهم هو الطبيعة . ما هذا؟ يُطلق على الفرز اسم طبيعي إذا كان أسرع عندما يتم فرز المصفوفة تقريبًا. ما هي المصفوفة التي يمكن اعتبارها "مرتبة تقريبًا"؟ في ما يلي
مصفوفتان من نفس العناصر: {1،2،9،3،4،5،7،6،8،10} و {9،1،6،3،10،5،4،2 ، 8.7}
حتى بالعين يمكنك أن ترى أن المصفوفة الأولى مرتبة بشكل أكبر (فقط 9 و 7 "في غير مكانها"). بينما في المصفوفة الثانية يتم خلط الأرقام عشوائيًا. ما هو مقياس النظام؟ الجواب معروف - عدد الانقلابات. يشكل زوج من العناصر A [i] و A [j] لـ j> i معكوسًا إذا كان A [j] <A [i]. (في هذه الملاحظة ، يكون الغرض من الفرز دائمًا ترتيبًا تصاعديًا.)
يمكننا الآن إعطاء تعريف دقيق: يُطلق على الفرز اسم طبيعي إذا انخفضت سرعته عندما ينخفض عدد الانقلابات في المصفوفة الأصلية.
الطبيعة هي بالأحرى "فاكهة نادرة" في عالم الفرز - لا نوع QuickSort ولا نوع Shell لهما هذه الخاصية ، للأسف. لكن هناك خوارزمية واحدة يمكن القول أنها طبيعية تمامًا - إنها نوع الإدراج. على الرغم من أن هذه الخوارزمية معروفة لكل شخص مثقف ، اسمحوا لي أن أكرر جوهرها بإيجاز.
يتم فحص المصفوفة المراد فرزها مرة واحدة من البداية إلى النهاية. بمجرد اكتشاف أن العنصرين i و (i-1) يشكلان انعكاسًا ، يتم "إرجاع" العنصر الأول إلى الخلف (يتم تحقيق ذلك عن طريق إزاحة الجزء المطلوب من بداية المصفوفة إلى اليمين بمقدار موضع واحد). يتضح من هذا الوصف أنه إذا كان هناك عدد قليل من الانقلابات في المصفوفة ، فإن الخوارزمية "تطير" عبر المصفوفة بسرعة كبيرة. إذا لم تكن هناك انعكاسات على الإطلاق ، فستكتمل الخوارزمية في وقت O (n). لكن QuickSort في هذه الحالة سيكون طويلًا ومملًا لتحديد عنصر فصل ، وتقسيم مصفوفة مرتبة بالفعل إلى مقاطع ، إلخ. ولكن إذا كان هناك الكثير من الانقلابات ، فسيكون الوضع ، بالطبع ، عكس ذلك: سينخفض أداء فرز الإدراج إلى O (n ^ 2) ، وستكون QuickSort هي البطل - O (n * log (n)).
يثير هذا الموقف سؤالًا طبيعيًا من وجهة نظري: كم عدد الانقلابات التي تفوق الطبيعة وأن نوع الإدراج يعمل بشكل أسرع من QuickSort؟
للإجابة على هذا السؤال ، أجريت سلسلة من التجارب الحسابية. كان جوهرهم على النحو التالي. تم أخذ مصفوفات من الأعداد الصحيحة تتراوح من 3000 إلى 30000 عنصر ، وتم إدخال عدد من الانعكاسات فيها ، ثم تم فرز المصفوفات عن طريق الإدخالات والفرز السريع. تم قياس وقت الفرز (في علامات النظام). لحساب المتوسط ، تم تكرار كل نوع 10 مرات. كانت النتائج على النحو التالي:
توضح الصورة تبعيات وقت الفرز على عدد الانقلابات المقدمة. سلسلة التوت هي ، بالطبع ، QuickSort ، والسلسلة الزرقاء هي نوع الإدراج. لحجم مصفوفة من 30 ألف عنصر ، ما يصل إلى حوالي 400 ألف انعكاس "انتصارات طبيعية". بالنسبة إلى المصفوفات الأقل ترتيبًا ، يعد QuickSort أكثر فائدة بالفعل.
وتوضح الصورة التالية الاعتماد التجريبي للعدد الحرج للانقلابات على حجم المصفوفة.
من السهل أن نرى أنه بالنسبة لمجموعة من الحجم n ، فإن العدد الحرج للانعكاسات هو حوالي 10 * n. مع المزيد من الانقلابات ، يعد QuickSort مفيدًا. وتجدر الإشارة إلى أن الحد الأقصى لعدد الانقلابات لصفيف طوله n هو n * (n-1) / 2. القيمة 10 * n جزء ضئيل للغاية منها. وهو أمر لا يثير الدهشة.
إلى ما قيل ، يبقى أن نضيف أن نتائج مثل هذه التجارب تعتمد على العديد من العوامل (لغة البرمجة ، نوع البيانات التي يتم فرزها ، وما إلى ذلك) لأكون صادقًا ، كنت كسولًا جدًا للتحقيق في هذه المشكلات بمزيد من التفصيل. تم إجراء تجاربي في Microsoft Excel في بيئة VBA:
اختبار شفرة المصدر
Private Declare Function GetTickCount Lib "kernel32" () As Long
':::
Sub JSort(A() As Long)
n& = UBound(A, 1)
For i& = 2 To n
If A(i&) < A(i& - 1) Then
j& = i& - 1
x& = A(i&)
Do While (A(j&) > x&)
A(j& + 1) = A(j&)
j& = j& - 1
If j& = 0 Then Exit Do
Loop
A(j& + 1) = x&
End If
Next i&
End Sub
':::
Sub QSort(A() As Long, Optional b As Long = 1, Optional e As Long = 0)
If (e - b) <= 1 Then Exit Sub
i& = b
j& = e
w& = A((i& + j&) / 2)
Do While (i& < j&)
Do While (A(i&) < w&)
i& = i& + 1
Loop
Do While (A(j&) > w&)
j& = j& - 1
Loop
If i& < j& Then
tmp& = A(i&)
A(i&) = A(j&)
A(j&) = tmp&
i& = i& + 1
j& = j& - 1
End If
Loop
If j& > b Then QSort A, b, j&
If i& < e Then QSort A, i&, e
End Sub
'::: ( )
Sub InsInv(A() As Long, k As Long)
n& = UBound(A, 1)
For i& = 1 To k
Do
k1& = n& * Rnd
k2& = n& * Rnd
If (k1& <> k2&) And (k1& >= 1) And (k2& >= 1) Then Exit Do
Loop
tmp& = A(k1&)
A(k1&) = A(k2&)
A(k2&) = tmp&
Next i&
End Sub
':::
Function NumInv(A() As Long) As Long
n& = UBound(A, 1)
For i& = 1 To n& - 1
For j& = i& + 1 To n&
If A(j&) < A(i&) Then NumInv = NumInv + 1
Next j&
Next i&
End Function
':::
Sub Gtest_1()
Dim Eta() As Long
Dim Arr() As Long
Size& = CLng(InputBox("Sz="))
ReDim Eta(1 To Size&) As Long
ReDim Arr(1 To Size&) As Long
Randomize
For i& = 1 To Size&
Eta(i&) = i&
Next i&
q# = Size& * (Size& - 1) / 2
For iii% = 1 To 10
InsInv Eta, CLng(iii%)
ni# = CDbl(NumInv(Eta))
Cells(iii%, 1).Value = ni#
DoEvents
S# = 0
For l% = 1 To 10
For i& = 1 To Size&
Arr(i&) = Eta(i&)
Next i&
TBeg& = GetTickCount
JSort Arr
TEnd& = GetTickCount
S# = S# + TEnd& - TBeg&
Next l%
Cells(iii%, 2).Value = S#
DoEvents
S# = 0
For l% = 1 To 10
For i& = 1 To Size&
Arr(i&) = Eta(i&)
Next i&
TBeg& = GetTickCount
QSort Arr, 1, Size&
TEnd& = GetTickCount
S# = S# + TEnd& - TBeg&
If Not check(Arr) Then Exit Sub
Next l%
Cells(iii%, 3).Value = S#
DoEvents
Next iii%
MsgBox "OK"
End Sub
شكرا للاهتمام!
ملاحظة
وشكرًا لكل من لاحظ أخطائي! (تهجئة غير صحيحة لـ Timsort - في الإصدار الأول كان هناك "TeamSort" و "i" مفقود في QuickSort). ونعم! - (خاصة لمن ينشدون الكمال) يمكن لـ QuickSort أن "يتدهور" إلى الأداء التربيعي. لكن في هذا المنشور ، لا أفكر في الأسوأ ، ولكن أفضل حالة استخدام لـ QuickSort.