فرز سريع:اختيار المحور

Question

عند تنفيذ الفرز السريع، أحد الأشياء التي يتعين عليك القيام بها هو اختيار محور.ولكن عندما أنظر إلى الكود الزائف مثل الموجود أدناه، فليس من الواضح كيف يجب أن أختار المحور.العنصر الأول من القائمة؟شيء آخر؟

 function quicksort(array)
     var list less, greater
     if length(array) ≤ 1  
         return array  
     select and remove a pivot value pivot from array
     for each x in array
         if x ≤ pivot then append x to less
         else append x to greater
     return concatenate(quicksort(less), pivot, quicksort(greater))

هل يمكن لأي شخص أن يساعدني في فهم مفهوم اختيار المحور وما إذا كانت السيناريوهات المختلفة تتطلب استراتيجيات مختلفة أم لا.

Answer 1

يؤدي اختيار محور عشوائي إلى تقليل احتمالية مواجهة أسوأ حالة O(n²) الأداء (قد يؤدي اختيار الأول أو الأخير دائمًا إلى أداء أسوأ حالة للبيانات التي تم فرزها تقريبًا أو التي تم فرزها بشكل عكسي تقريبًا).كما أن اختيار العنصر الأوسط سيكون مقبولاً في معظم الحالات.

وأيضًا، إذا كنت تقوم بتنفيذ ذلك بنفسك، فهناك إصدارات من الخوارزمية تعمل في مكانها (على سبيل المثال.دون إنشاء قائمتين جديدتين ثم ربطهما).

Answer 2

ذلك يعتمد على الاحتياجات الخاصة بك.يؤدي اختيار المحور عشوائيًا إلى زيادة صعوبة إنشاء مجموعة بيانات تولد أداء O(N^2)."الوسيط من الثلاثة" (الأول، الأخير، الأوسط) هو أيضًا وسيلة لتجنب المشاكل.ولكن احذر من الأداء النسبي للمقارنات؛إذا كانت مقارناتك مكلفة، فإن Mo3 يقوم بإجراء مقارنات أكثر من اختيار (قيمة محورية واحدة) بشكل عشوائي.يمكن أن تكون مقارنة سجلات قاعدة البيانات مكلفة.

---

تحديث:سحب التعليقات إلى الإجابة.

com.mdkess أكد:

"الوسيط 3" ليس أول وسط وأخير.اختر ثلاثة فهارس عشوائية، وخذ القيمة الوسطى من هذا.بيت القصيد هو التأكد من أن اختيارك للمحاور ليس حتميًا - إذا كان الأمر كذلك، فيمكن إنشاء بيانات الحالة الأسوأ بسهولة تامة.

والذي أجبت عليه:

• تحليل خوارزمية بحث هور مع قسم متوسط ​​من ثلاثة (1997) بقلم P Kirschenhofer ، H Prodinger ، C Martínez يدعم خلافك (أن "متوسط ​​ثلاثة" هو ثلاثة عناصر عشوائية).

• هناك مقال موصوف في Portal.acm.org يدور هذا حول "أسوأ حالة التقليب للفرز السريع لمتوسط ​​من ثلاثة" بقلم هانو إركيو، المنشور في مجلة الكمبيوتر، المجلد 27، العدد 3، 1984.[تحديث 2012/02/26:حصلت على النص ل شرط.يبدأ القسم 2 "الخوارزمية":'باستخدام متوسط ​​العناصر الأولى والمتوسطة والأخيرة من A[L:R]، يمكن تحقيق التقسيم الفعال إلى أجزاء ذات أحجام متساوية إلى حد ما في معظم المواقف العملية.'وهكذا، فهو يناقش نهج Mo3 الأول والأوسط والأخير.]

• مقالة قصيرة أخرى مثيرة للاهتمام كتبها M.د.ماكلروي, "الخصم القاتل للفرز السريع", ، نشرت في ممارسة البرمجيات والخبرة، المجلد.29(0)، 1–4 (0 1999).وهو يشرح كيفية جعل أي فرز سريع تقريبًا يتصرف بطريقة تربيعية.

• مجلة AT&T Bell Labs التقنية، أكتوبر 1984 تنص "النظرية والتطبيق في إنشاء روتين فرز العمل" على أن "Hoare اقترح التقسيم حول متوسط ​​عدة خطوط مختارة عشوائيًا.أوصى Sedgewick [...] باختيار الوسيط الأول [...] والأخير [...] والوسطى".يشير هذا إلى أن كلا الأسلوبين لـ "الوسيط من الثلاثة" معروفان في الأدبيات.(تحديث 23/11/2014:يبدو أن المقالة متاحة على آي إي إي إكسبلور او من وايلي - إذا كان لديك عضوية أو كنت على استعداد لدفع رسوم.)

• "هندسة وظيفة الفرز" بواسطة J L Bentley وMD McIlroy، المنشور في Software Practice and Experience، المجلد 23 (11)، نوفمبر 1993، دخل في مناقشة مستفيضة للقضايا، واختاروا خوارزمية تقسيم تكيفية تعتمد جزئيًا على حجم مجموعة البيانات.هناك الكثير من المناقشات حول المقايضات لمختلف الأساليب.

• يعمل بحث Google عن "متوسط ​​الثلاثة" بشكل جيد لمزيد من التتبع.

اشكرك على المعلومات؛لقد واجهت فقط "الوسيط الحتمي من ثلاثة" من قبل.

Answer 3

وهيه، أنا فقط تدريس هذه الفئة.

وهناك العديد من الخيارات.
بسيطة: اختيار العنصر الأول أو الأخير من النطاق. (سيئة على مدخلات فرز جزئي) أفضل: اختيار هذا البند في منتصف النطاق. (أفضل على مدخلات فرزها جزئيا)

ولكن، واختيار أي عنصر التعسفي ينطوي على خطر ضعيف تقسيم مجموعة من حجم ن إلى قسمين صفائف حجم 1 و n-1. إذا كنت تفعل ذلك في كثير من الأحيان بما فيه الكفاية، فرز سريع الخاص بك يعمل من خطر أن تصبح O (ن ^ 2).

وتحسين واحدة رأيت هو اختيار الوسيط (الأول، الماضي، منتصف)؛ في أسوأ الحالات، يمكن أن لا يزالون يذهبون إلى O (ن ^ 2)، ولكن احتماليا، وهذا هو حالة نادرة.

لمعظم البيانات، واختيار أول أو آخر غير كافية. ولكن، إذا وجدت أنك تعمل في أسوأ السيناريوهات في كثير من الأحيان (المدخلات فرز جزئي)، الخيار الأول سيكون لاختيار القيمة المركزية (والذي هو محور جيد إحصائية للبيانات التي تم فرزها جزئيا).

إذا كنت لا تزال الوقوع في المشاكل، ثم انتقل الطريق المتوسط.

Answer 4

لا تختر أبدًا محورًا ثابتًا - يمكن مهاجمته لاستغلال أسوأ حالة تشغيل للخوارزمية O(n^2)، والتي لا تتطلب سوى المتاعب.تحدث أسوأ حالات تشغيل Quicksort عندما يؤدي التقسيم إلى صفيف واحد من عنصر واحد، وصفيف واحد من عناصر n-1.لنفترض أنك اخترت العنصر الأول ليكون القسم الخاص بك.إذا قام شخص ما بتغذية خوارزمية بمصفوفة بترتيب تنازلي، فسيكون المحور الأول هو الأكبر، لذلك سينتقل كل شيء آخر في المصفوفة إلى يساره.ثم عندما تتكرر، سيكون العنصر الأول هو الأكبر مرة أخرى، لذا مرة أخرى تضع كل شيء على يساره، وهكذا.

الأسلوب الأفضل هو أسلوب الوسيط من 3، حيث تختار ثلاثة عناصر بشكل عشوائي، ثم تختار الوسط.أنت تعلم أن العنصر الذي تختاره لن يكون الأول أو الأخير، ولكن أيضًا، وفقًا لنظرية الحد المركزي، سيكون توزيع العنصر الأوسط طبيعيًا، مما يعني أنك ستميل نحو الوسط (وبالتالي ، ن إل جي ن الوقت).

إذا كنت تريد تمامًا ضمان وقت تشغيل O(nlgn) للخوارزمية، فإن طريقة الأعمدة من 5 للعثور على متوسط ​​المصفوفة تعمل في وقت O(n)، مما يعني أن معادلة التكرار للفرز السريع في أسوأ الحالات سوف يكون T(n) = O(n) (ابحث عن الوسيط) + O(n) (القسم) + 2T(n/2) (العودة لليسار واليمين.) وفقًا للنظرية الرئيسية، هذا هو O(n lg n) .ومع ذلك، فإن العامل الثابت سيكون ضخمًا، وإذا كان الأداء الأسوأ هو شاغلك الأساسي، فاستخدم فرز الدمج بدلاً من ذلك، وهو أبطأ قليلاً من الفرز السريع في المتوسط، ويضمن وقت O(nlgn) (وسيكون أسرع بكثير من هذا الفرز السريع المتوسط ​​​​العرجاء).

شرح خوارزمية الوسيط للمتوسطات

Answer 5

لا تحاول أن تكون ذكيًا جدًا وتجمع بين استراتيجيات التمحور.إذا قمت بدمج الوسيط 3 مع المحور العشوائي عن طريق اختيار متوسط ​​الأول والأخير ومؤشر عشوائي في المنتصف، فستظل عرضة للعديد من التوزيعات التي ترسل متوسط ​​3 من الدرجة الثانية (لذا فهو في الواقع أسوأ من محور عشوائي عادي)

على سبيل المثال، توزيع أعضاء الأنابيب (1,2,3...N/2..3,2,1) الأول والأخير سيكونان 1 وسيكون المؤشر العشوائي رقمًا أكبر من 1، مع أخذ الوسيط يعطي 1 ( إما الأول أو الأخير) وستحصل على تقسيم غير متوازن تمامًا.

Answer 6

وهو يعتمد كليا على كيف يتم فرز البيانات الخاصة بك لتبدأ. إذا كنت تعتقد أنه سيكون شبه عشوائي ثم أفضل رهان هو إما اختيار مجموعة عشوائية أو اختيار الوسط.

Answer 7

إذا كنت فرز مجموعة العشوائي الوصول إليها (مثل مجموعة)، انها العام الأفضل لاختيار هذا البند الأوسط البدني. مع ذلك، إذا كان الصفيف هو كل شيء جاهزا مرتبة (أو فرزها تقريبا)، وقسمين سوف تكون قريبة من ذلك، وستحصل على أفضل سرعة.

إذا كنت فرز شيء مع وصول الخطية فقط (مثل القائمة ربط)، ثم أنه من الأفضل لاختيار العنصر الأول، لأنه أسرع البند الوصول إليها. هنا، ومع ذلك، إذا تم فرز القائمة بالفعل، وأنت ثمل - وقسم واحد يكون دائما لاغية، والآخر أن يكون كل شيء، وإنتاج أسوأ وقت

ولكن، عن قائمة مرتبطة، واختيار أي شيء إلى جانب أول، وجعل مجرد الأمور سوءا. ذلك اختيار هذا البند المتوسطة في القائمة المذكورة، وكنت قد لخطوة من خلال ذلك على كل خطوة التقسيم - إضافة O (/ 2 N) العملية التي تتم مرة logN يجعل مجموع O الوقت (1.5 N * تسجيل N) وهذا إذا عرفنا متى القائمة قبل أن نبدأ - عادة نحن لا حتى أن علينا أن خطوة على طول الطريق من خلال الاعتماد عليها، ثم خطوة في منتصف الطريق من خلال العثور على الوسط ثم خطوة من خلال المرة الثالثة للقيام التقسيم الفعلي: O (2.5N * تسجيل N)

Answer 8

من الأسهل تقسيم الفرز السريع إلى ثلاثة أقسام عند القيام بذلك

1. وظيفة تبادل أو تبديل عنصر البيانات
2. وظيفة التقسيم
3. معالجة الأقسام

إنها أقل كفاءة قليلاً من وظيفة واحدة طويلة ولكنها أسهل بكثير في الفهم.

الكود يلي:

/* This selects what the data type in the array to be sorted is */

#define DATATYPE long

/* This is the swap function .. your job is to swap data in x & y .. how depends on
data type .. the example works for normal numerical data types .. like long I chose
above */

void swap (DATATYPE *x, DATATYPE *y){  
  DATATYPE Temp;

  Temp = *x;        // Hold current x value
  *x = *y;          // Transfer y to x
  *y = Temp;        // Set y to the held old x value
};


/* This is the partition code */

int partition (DATATYPE list[], int l, int h){

  int i;
  int p;          // pivot element index
  int firsthigh;  // divider position for pivot element

  // Random pivot example shown for median   p = (l+h)/2 would be used
  p = l + (short)(rand() % (int)(h - l + 1)); // Random partition point

  swap(&list[p], &list[h]);                   // Swap the values
  firsthigh = l;                                  // Hold first high value
  for (i = l; i < h; i++)
    if(list[i] < list[h]) {                 // Value at i is less than h
      swap(&list[i], &list[firsthigh]);   // So swap the value
      firsthigh++;                        // Incement first high
    }
  swap(&list[h], &list[firsthigh]);           // Swap h and first high values
  return(firsthigh);                          // Return first high
};



/* Finally the body sort */

void quicksort(DATATYPE list[], int l, int h){

  int p;                                      // index of partition 
  if ((h - l) > 0) {
    p = partition(list, l, h);              // Partition list 
    quicksort(list, l, p - 1);        // Sort lower partion
    quicksort(list, p + 1, h);              // Sort upper partition
  };
};

Answer 9

وبشكل مثالي المحور يجب أن تكون القيمة المتوسطة في مجموعة كاملة. وهذا سوف يقلل من فرص الحصول على أسوأ أداء القضية.

Answer 10

وتعقيد نوع سريع وبشكل كبير مع اختيار قيمة المحور. على سبيل المثال إذا كنت دائما اختيار العنصر الأول باعتباره محور، يصبح تعقيد الخوارزمية كما أسوأ كما O (ن ^ 2). هنا هو طريقة ذكية لاختيار element- محور 1. اختيار أول، منتصف، العنصر الأخير للصفيف. 2. مقارنة هذه الأرقام الثلاثة والعثور على عدد الذي هو أكبر من واحد وأصغر من الآخر أي الوسيط. 3. جعل هذا العنصر كعنصر محوري.

واختيار محور من هذه الطريقة يقسم مجموعة في ما يقرب من نصف وبالتالي تعقيد يقلل إلى O (nlog (ن)).

Answer 11

في المتوسط، متوسط ​​3 جيد لـ n الصغيرة.الوسيط 5 أفضل قليلاً بالنسبة إلى n الأكبر.التاسع، وهو "الوسيط لثلاثة متوسطات لثلاثة" هو أفضل بالنسبة لـ n الكبيرة جدًا.

كلما ارتفعت في أخذ العينات، كلما حصلت على نتائج أفضل مع زيادة n، لكن التحسن يتباطأ بشكل كبير مع زيادة العينات.وتتحمل أنت النفقات العامة لأخذ العينات وفرز العينات.

Answer 12

وأوصي باستخدام مؤشر الأوسط، كما أنه يمكن أن تحسب بسهولة.

ويمكنك حساب من قبل التقريب (array.length / 2).

Answer 13

في التنفيذ الأمثل حقا، وطريقة لاختيار المحور يجب أن تعتمد على حجم مجموعة - لمجموعة كبيرة، فإنه يؤتي ثماره لقضاء المزيد من الوقت في اختيار محور جيد. دون أن تفعل تحليل كامل، اعتقد ان "منتصف O (سجل (ن)) عناصر" هو بداية جيدة، وهذا له مكافأة إضافية لا تتطلب أي ذاكرة إضافية: استخدام الذيل دعوة على القسم الأكبر وفي- مكان التقسيم، ونحن نستخدم نفس O (تسجيل (ن)) ذاكرة إضافية تقريبا في كل مرحلة من مراحل الخوارزمية.