تحديد سريع

في علوم الحاسوب ، تُعدّ خوارزمية الاختيار السريع (Quickselect) خوارزمية اختيار لإيجاد العنصر الأصغر رقم k في قائمة غير مرتبة، والمعروف أيضًا باسم إحصائية الترتيب رقم k . ومثل خوارزمية الفرز السريع (Quicksort) ذات الصلة ، طُوّرت هذه الخوارزمية على يد توني هوار ، ولذا تُعرف أيضًا باسم خوارزمية اختيار هوار . ^{[ 1 ]} وكما هو الحال مع الفرز السريع، تتميز خوارزمية الاختيار السريع بالكفاءة العملية والأداء الجيد في المتوسط، ولكنها تُظهر أداءً ضعيفًا في أسوأ الحالات. وتُعدّ خوارزمية الاختيار السريع ومشتقاتها من أكثر خوارزميات الاختيار استخدامًا في التطبيقات العملية الفعّالة.

تستخدم خوارزمية Quickselect نفس النهج العام لخوارزمية Quicksort، حيث تختار عنصرًا واحدًا كعنصر محوري وتقسم البيانات إلى قسمين بناءً على هذا العنصر، إما أصغر من العنصر المحوري أو أكبر منه. مع ذلك، بدلًا من التكرار في كلا الجانبين، كما هو الحال في Quicksort، فإن Quickselect تتكرر في جانب واحد فقط - الجانب الذي يحتوي على العنصر المطلوب البحث عنه. هذا يقلل من متوسط ​​التعقيد من${\displaystyle O(n\log n)}$ل${\displaystyle O(n)}$، مع أسوأ حالة من${\displaystyle O(n^{2})}$.

كما هو الحال مع خوارزمية الفرز السريع، تُنفَّذ خوارزمية الاختيار السريع عادةً كخوارزمية داخلية ، وإلى جانب اختيار العنصر رقم k ، فإنها تُرتِّب البيانات جزئيًا. راجع خوارزمية الاختيار لمزيد من التفاصيل حول العلاقة بالفرز.

في خوارزمية الفرز السريع، توجد دالة فرعية تُسمى تُسمى partitionتُمكن من تقسيم قائمة (تتراوح فهارسها من 1 leftإلى 2 right) إلى جزأين في وقت خطي: ​​العناصر الأصغر من عنصر معين، والعناصر الأكبر من أو تساوي هذا العنصر. إليك شيفرة زائفة تُجري عملية التقسيم بناءً على العنصر 1 list[pivotIndex]:

دالة التقسيم (القائمة، اليسار، اليمين، فهرس المحور) هي pivotValue := list[pivotIndex] تبديل list[pivotIndex] و list[right] // نقل المحور إلى النهاية storeIndex := left لكل i من اليسار إلى اليمين - 1، إذا كان list [i] <= pivotValue ثم قم بتبديل القائمة[storeIndex] والقائمة[i] زيادة فهرس المتجر تبديل list[right] و list[storeIndex] // نقل المحور إلى مكانه النهائي إرجاع storeIndex

يُعرف هذا باسم مخطط تقسيم لوموتو ، وهو أبسط ولكنه أقل كفاءة من مخطط تقسيم هوار الأصلي .

في خوارزمية الفرز السريع، نقوم بفرز كلا الفرعين بشكل متكرر، مما يؤدي إلى أفضل حالة.${\displaystyle O(n\log n)}$مع ذلك، عند إجراء عملية التحديد، نعرف مسبقًا القسم الذي يقع فيه العنصر المطلوب، لأن العنصر المحوري يكون في موضعه النهائي المُرتب، بينما تكون جميع العناصر التي تسبقه والعناصر التي تليه غير مُرتبة. لذا، تُحدد استدعاءات متكررة واحدة موقع العنصر المطلوب في القسم الصحيح، ونعتمد على ذلك في التحديد السريع.

// تُعيد أصغر عنصر في القائمة (العنصر رقم k) ضمن النطاق من اليسار إلى اليمين (أي left ≤ k ≤ right). // (أي left ≤ k ≤ right). function select(list, left, right, k) is if left = right then // إذا كانت القائمة تحتوي على عنصر واحد فقط، تُعيد list[left] // تُعيد هذا العنصر pivotIndex := ... // تُحدد قيمة pivotIndex بين left و right، // على سبيل المثال، left + floor(rand() % (right − left + 1)) pivotIndex := partition(list, left, right, pivotIndex) // يكون العنصر المحوري في موضعه النهائي بعد الترتيب إذا كان k = pivotIndex ، فأرجع list[k] ، وإلا إذا كان k < pivotIndex ، فأرجع select (list, left, pivotIndex − 1, k)، وإلا فأرجع select(list, pivotIndex + 1, right, k).

وكما أن خوارزمية الاختيار القائمة على الحد الأدنى هي فرز اختيار جزئي ، فإن هذه خوارزمية فرز سريع جزئية، تقوم فقط بتوليد وتقسيم${\displaystyle O(\log n)}$من${\displaystyle O(n)}$التقسيمات. يتميز هذا الإجراء البسيط بأداء خطي متوقع، ومثل خوارزمية الفرز السريع، يتمتع بأداء جيد جدًا في التطبيق العملي. كما أنه خوارزمية تعمل في مكانها ، ولا تتطلب سوى زيادة ثابتة في الذاكرة إذا كان تحسين استدعاء الذيل متاحًا، أو إذا تم التخلص من استدعاء الذيل باستخدام حلقة تكرارية.

دالة select(list, left, right, k) هي حلقة تكرارية إذا كان left = right ثم أعد list[left] pivotIndex := ... // تحديد pivotIndex بين اليسار واليمين pivotIndex := partition(list, left, right, pivotIndex) إذا كان k يساوي pivotIndex، فأرجع list [k]، وإلا إذا كان k أقل من pivotIndex ، يمين := مؤشر المحور - 1 وإلا، اليسار := مؤشر المحور + 1

selectتعمل هذه الدالة فقط مع مخطط تقسيم لوموتو . وذلك لأنها selectتفترض أن القيمة المُعادة من دالة التقسيم هي موضع العنصر المحوري. هذا صحيح بالنسبة لمخطط تقسيم لوموتو ، ولكنه غير صحيح بالنسبة لمخطط تقسيم هوار . في مخطط هوار، القيمة المُعادة هي الفهرس الأخير للقسم "الأيسر"، ولا يُضمن أن يكون العنصر المحوري "بين" الأقسام.

إن التكرار، كما هو معروض، يعمل فقط مع مخطط لوموتو، لأنه يفترض أن القسم الأيمن يبدأ بـ pivotIndex +1، بينما عند استخدام مخطط هوار، يبدأ القسم الأيمن عند pivotIndex.

على غرار خوارزمية الفرز السريع، تتمتع خوارزمية الاختيار السريع بأداء متوسط ​​جيد، لكنها حساسة للعنصر المحوري المُختار. إذا تم اختيار عناصر محورية جيدة، أي تلك التي تُقلل مجموعة البحث باستمرار بنسبة مُحددة، فإن حجم مجموعة البحث يتناقص أُسّيًا، وبالاستقراء (أو بجمع المتسلسلة الهندسية ) يتضح أن الأداء خطي، حيث أن كل خطوة خطية والوقت الإجمالي ثابت مضروبًا في هذا (بحسب سرعة تناقص مجموعة البحث). مع ذلك، إذا تم اختيار عناصر محورية سيئة باستمرار، مثل تقليل حجم مجموعة البحث بعنصر واحد فقط في كل مرة، فإن أسوأ أداء يكون تربيعيًا.${\displaystyle O(n^{2}).}$يحدث هذا، على سبيل المثال، عند البحث عن أكبر عنصر في مجموعة، باستخدام العنصر الأول كعنصر محوري، مع وجود بيانات مرتبة. ومع ذلك، بالنسبة للعناصر المحورية المختارة عشوائيًا، فإن هذه الحالة الأسوأ نادرة جدًا: احتمال استخدام أكثر من${\displaystyle Cn}$المقارنات، لأي ثابت كبير بما فيه الكفاية${\displaystyle C}$، صغيرة بشكل فائق الأسي كدالة لـ${\displaystyle C}$[ ^{2 ]​}

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

يمكن ضمان أداء خطي حتى في أسوأ الحالات باستخدام استراتيجية محورية أكثر تطورًا؛ ويتم ذلك في خوارزمية وسيط الوسائط . مع ذلك، فإن تكلفة حساب المحور مرتفعة، ولذا لا يُستخدم هذا الأسلوب عمليًا. يمكن دمج الاختيار السريع الأساسي مع وسيط الوسائط كحل بديل للحصول على أداء سريع في المتوسط ​​وأداء خطي في أسوأ الحالات؛ ويتم ذلك في خوارزمية introselect .

تؤدي الحسابات الأكثر دقة لمتوسط ​​التعقيد الزمني إلى أسوأ حالة من${\displaystyle n(2+2\log 2+o(1))\leq 3.4n+o(n)}$بالنسبة للمحاور العشوائية (في حالة الوسيط؛ قيم k الأخرى أسرع). ^{[ 3 ]} يمكن تحسين الثابت إلى 3/2 باستخدام استراتيجية محور أكثر تعقيدًا، مما ينتج عنه خوارزمية فلويد-ريفست ، التي يبلغ متوسط ​​تعقيدها 3/2.${\displaystyle 1.5n+O(n^{1/2})}$بالنسبة للوسيط، مع كون قيم k الأخرى أسرع.

• خوارزمية فلويد-ريفست
• إنتروسليكت
• وسيط الوسائط

• " qselect "، خوارزمية الاختيار السريع في ماتلاب، مانوليس لوراكيس