QuickSort Invariant 3 ظروف مع حلقة ثابتة

Question

في دراسة QuickSort باستخدام الكتاب "مقدمة في الخوارزميات" من قبل Cormen و Leiserson و Rivest و Stein، يصفون من أجل إظهار التصحيح، يجب أن يحمل الثابتة على مراحل 3 حلقة، والتهيئة، والصيانة والإنهاء من الحلقة.

بناء على الخوارزمية التالية، لا أفهم الخصائص 1 و 2 أدناه:

Answer 1

إذا كان $ p \ leq k \ leq i $ ثم $ a [k] \ leq x. $ في الخوارزمية عندما على سبيل المثال، $ P $ هو $ 1 $ ، لن $ i $ be $ 0 $ .... كيف ستعقد هذه، منذ ذلك قبل حلقة حلقة لدينا GuardacetagCode

على الرغم من ذلك، كما لوحظت، $ i $ هو دائما أصغر من $ P $ في بداية الحلقة، قد يصبح أكبر لأن العبارة " $ i= i + 1 $ يمكن تنفيذها" في الحلقة. بمجرد $ I $ قد ارتفع، ل $ k= p $ ، لدينا $ p \ le k \ le i i $ .

لاحظ أنه عندما $ p \ le i i $ لا يمسك، أي عندما لا يكون هناك $ k $ < / span> مثل هذا $ p \ le k \ le i i $ ، الحالة "إذا $ p \ leq k \ leq I $ ثم $ A [k] \ leq x $ "يحمل تلقائيا. (أذكر أن الاقتراح "إذا كان false، فإن أي شيء يمكن أن يحدث دائما" صحيحا دائما.) لزياف هذا الشرط، علينا أن نجد مثيل $ (p، k، i) $ مثل هذا $ p \ leq k \ leq i $ ولكن $ a [k] \ gt x $ < / span>.

يجب أن تكون قادرا على معرفة حالة الحلقة الثانية الثابتة الآن.

Answer 2

أنا لست في مزاجا من إيمان رمز البرمجية، لكنه أفهم أنك تبدأ ب [R]= x وتنتهي مع [i]= x

(المحور، الذي يبدو أنه يتم اختياره باعتباره العنصر الأخير $ r $ في التعليمات البرمجية المحددة، يصل إلى وضعه الصحيح مع تبادل القائمة)

-AT نظرة أولى ربما يكون الرمز يحتوي على بعض الأخطاء، لا توجد حاجة للتبادل بين الأقواس آنذاك، ويجب أن يكون التبادل الآخر أراهن [R] و A [J] داخل $ $ us $