3 اتجاه سريع ، سؤال
سؤال
أحاول أن أفهم Quicksort 3-Way Radix ، ولا أفهم لماذا المتغير المتغير هناك؟ وطريقة الإدراج؟
public class Quick3string {
private static final int CUTOFF = 15; // cutoff to insertion sort
// sort the array a[] of strings
public static void sort(String[] a) {
// StdRandom.shuffle(a);
sort(a, 0, a.length-1, 0);
assert isSorted(a);
}
// return the dth character of s, -1 if d = length of s
private static int charAt(String s, int d) {
assert d >= 0 && d <= s.length();
if (d == s.length()) return -1;
return s.charAt(d);
}
// 3-way string quicksort a[lo..hi] starting at dth character
private static void sort(String[] a, int lo, int hi, int d) {
// cutoff to insertion sort for small subarrays
if (hi <= lo + CUTOFF) {
insertion(a, lo, hi, d);
return;
}
int lt = lo, gt = hi;
int v = charAt(a[lo], d);
int i = lo + 1;
while (i <= gt) {
int t = charAt(a[i], d);
if (t < v) exch(a, lt++, i++);
else if (t > v) exch(a, i, gt--);
else i++;
}
// a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi].
sort(a, lo, lt-1, d);
if (v >= 0) sort(a, lt, gt, d+1);
sort(a, gt+1, hi, d);
}
// sort from a[lo] to a[hi], starting at the dth character
private static void insertion(String[] a, int lo, int hi, int d) {
for (int i = lo; i <= hi; i++)
for (int j = i; j > lo && less(a[j], a[j-1], d); j--)
exch(a, j, j-1);
}
// exchange a[i] and a[j]
private static void exch(String[] a, int i, int j) {
String temp = a[i];
a[i] = a[j];
a[j] = temp;
}
// is v less than w, starting at character d
private static boolean less(String v, String w, int d) {
assert v.substring(0, d).equals(w.substring(0, d));
return v.substring(d).compareTo(w.substring(d)) < 0;
}
// is the array sorted
private static boolean isSorted(String[] a) {
for (int i = 1; i < a.length; i++)
if (a[i].compareTo(a[i-1]) < 0) return false;
return true;
}
public static void main(String[] args) {
// read in the strings from standard input
String[] a = StdIn.readAll().split("\\s+");
int N = a.length;
// sort the strings
sort(a);
// print the results
for (int i = 0; i < N; i++)
StdOut.println(a[i]);
}
}
من عند http://www.cs.princeton.edu/algs4/51Radix/quick3string.java.html
المحلول
يبدو أنه يتم استخدامه من أجل استدعاء نوع الإدراج للحصول على صفيف صغير بما فيه الكفاية (الحجم <= 15). من المرجح أن تسريع الفرز.
نصائح أخرى
إنه تحسين بسيط لخوارزمية Quicksort. تكلفة المكالمات العودية في Quicksort مرتفعة للغاية ، لذا فإن نوع الإدراج في المصفوفات الصغيرة يعمل بشكل أفضل. لذا ، فإن الفكرة هي أنه إذا تم فرز طول جهاز التشغيل الفرعي لنظام التشغيل أدناه ، فمن الأفضل فرزه باستخدام نوع الإدراج من Quicksort. في مثالك ، يحدد متغير Cutoff تلك العتبة ، أي إذا تم ترك أقل من 15 عنصرًا ، يتم فرزها باستخدام نوع الإدراج بدلاً من Quicksort.
طريقة الفرز أعلاه هي طريقة متكررة. ويجب أن يكون لكل طريقة متكررة نوعًا من الحالات الأساسية (وإلا فإنها ستستمر في الاتصال بنفسها ، مما يؤدي في النهاية إلى فائض مكدس).
جزء الإدراج هو الحالة الأساسية في هذه الطريقة ، لأنه في كل خطوة متكررة ، يستمر اختلاف HI-LO في الانخفاض ، وعندما يكون أقل من القطع ، سيتم تشغيل نوع الإدراج في النهاية ، مما يجبر العودية على التوقف.
if (hi <= lo + CUTOFF) { // base case
insertion(a, lo, hi, d);
return;
}
الآن ، لماذا الإدراج؟ لأنه يعمل بشكل جيد للمصفوفات الصغيرة. المزيد عن الفرز هنا: http://www.sorting-algorithms.com/
هذه الفكرة تأتي من روبرت سيدجويك ، الذي يعرف المزيد عن Quicksort أكثر من أي رجل على قيد الحياة. تم الاستشهاد به في Donald E. Knuth ، فن برمجة الكمبيوتر، المجلد الثالث ، حيث يظهر ذلك للصغر م ، نوع الإدراج أسرع من Quicksort ، لذلك يوصي بعدم فرز الأقسام الصغيرة م على الإطلاق وتركه إلى نوع إدخال نهائي واحد على مجموعة البيانات بأكملها في النهاية. Knuth يعطي وظيفة للحساب م (اي منهم يخصك CUTOFF
) والتي هي 9 له MIX
الحاسوب الزائف.