MARK GROZEN-SMITH: مرحبا، أنا الأقسام Grozen سميث، وهذا هو فرز سريع. تماما مثل الإدراج الفرز وفقاعة نوع، هو خوارزمية فرز سريع لل فرز قائمة أو مجموعة من الأشياء. البساطة، دعونا نفترض أن تلك الأشياء ليست سوى أعداد صحيحة، ولكن نعلم أن يعمل لفرز سريع أكثر من مجرد أرقام. التشغيل السريع هو أكثر تعقيدا نوعا ما من الإدراج أو فقاعة، ولكن هذا أيضا أكثر كفاءة بكثير في معظم الحالات. انتظر ثانية. وقال انه مجرد ويقول "معظم الحالات "، وليس" كل "؟ ومن المثير للاهتمام، لا. ليس كل الحالات هي نفسها. لا تقلق بشأن هذا التفصيل إذا كنت لم أر تدوين يا كبير حتى الآن، ولكن فرز سريع هو O (ن تربيع) خوارزمية في أسوأ الأحوال، تماما مثل الإدراج أو فقاعة الفرز. ومع ذلك، فإنه عادة ما يعمل أكثر من ذلك بكثير مثل خوارزمية م التناظرية القديمة. لماذا؟ وسوف نعود لذلك لاحقا. لكنه الآن، دعونا نتعلم فقط كيف يعمل فرز سريع. 

لذلك دعونا المشي من خلال هذا Quicksorting مجموعة من الأعداد الصحيحة من أصغر إلى أكبر. هنا لدينا الأعداد الصحيحة 6، 5، 1، 3، 8، 4، 7، 9، و 2. أولا، واختيار العنصر الأخير من هذه المجموعة - في هذه الحالة، وهما - وندعو إلى أن "المحور". المقبل، ونحن بدء النظر في أمرين: - واحد، وهو أدنى المؤشر الذي سوف أشير كما أن البقاء للحق الجدار، و، اثنان، في أقصى اليسار العنصر الذي سأتصل "الحالية العنصر. "ما نحن بصدد القيام به هو تبدو كل العناصر الأخرى، وغيرها من من محور، ووضع كل العناصر أصغر من محور ل تبقى من الجدار وجميع تلك أكبر من محور ل الأيمن من الجدار. ثم، أخيرا، سنقوم إسقاط محور الحق على هذا الجدار لوضعها بين جميع الأرقام أصغر من ذلك وجميع الأرقام الكبيرة. 

لذلك دعونا نفعل ذلك. التقط 2، ووضع الجدار في بداية، واستدعاء 6 "التيار عنصر ". لذلك نحن نريد أن ننظر إلى العنصر الحالي لدينا، و6. ونظرا لأنه أكبر من 2، ونحن نترك الامر هناك ل الأيمن من الجدار. ثم، ننتقل إلى إلقاء نظرة على 5 لدينا العنصر الحالي ونرى أن هذا هو، مرة أخرى، وأكبر من محور، لذلك نحن ترك الأمر حيث كان على حق جانب من الجدار. ونحن على هذه الخطوة. لدينا العنصر الحالي هو الآن 1، و- اه. وهذا يختلف الآن. العنصر الحالي هو الآن أصغر من محور، لذلك نحن نريد لوضعها إلى اليسار من الجدار. للقيام بذلك، دعونا التبديل فقط العنصر الحالي مع أدنى مؤشر مجرد الجلوس إلى يمين الجدار. الآن، ونحن نتحرك الجدار حتى مؤشر واحد وبالتالي فإن 1 على اليسار جانب من الجدار الآن. 

الانتظار. أنا مختلطة للتو العناصر على الجانب الأيمن من الجدار، لم أكن أنا؟ لا تقلق. هذا شيء طيب. الشيء الوحيد الذي يهمني في الوقت الراهن غير أن جميع هذه العناصر ل الأيمن من الجدار هي اكبر من محور. ويفترض أي أمر الفعلي بعد. 

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

نحن ثم كرر هذه العملية ل غادر subarrays واليمين من محور. منذ subarray الأخير هو واحد فقط عنصر طويلة، ونحن نعلم أن هذا بالفعل فرزها لأن كيف يمكنك أن تكون من النظام إذا كنت عنصر واحد فقط؟ بالنسبة للجانب الأيمن من subarray، ونحن نرى أن محور هو 5، والجدار وغادر لتوه من 6. والعنصر الحالي أيضا يبدأ باسم 6. حتى 6 أكبر من 5. نحن نترك الامر حيث كان على الجانب الأيمن من الجدار. الآن، والانتقال، 3 هو أقل من 5. لذلك نحن تشغيله مع العنصر الأول مجرد حق من الجدار. الآن، انتقلت الجدار حتى واحد. الآن، والانتقال إلى 8. 8 أكبر من 5، ولذا فإننا نترك الامر. ال 4 هو أقل من 5، لذلك نحن تشغيله. وعلى. وعلى. 

في كل مرة نكرر هذه العملية على الجانبين الأيسر والأيمن من الصفيف. نحن اختيار محور والقيام مقارنات وخلق مستوى آخر من اليسار و subarrays الحق. وسوف تستمر هذه الدعوة حتى العودية نصل إلى نهاية عندما قمنا قسمت مجموعة الشاملة في فقط subarrays من طول 1. من هناك، ونحن نعلم يتم فرز مجموعة لأن كل عنصر لديه، في مرحلة ما، كان محور. وبعبارة أخرى، لكل عنصر، كل الأرقام إلى اليسار هي أقل القيم وجميع الأرقام ل لها قيم أكبر الحق. 

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

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

اسمي مارك Grozen سميث، وهذا هو CS50. 

البساطة، دعونا نفترض أن تلك الأشياء ليست سوى أعداد صحيحة، ولكن نعلم أن Quicksert - Quicksert؟ آسف. 

هنا لدينا الأعداد الصحيحة 6، 5، 1، 3، 8، 4، 9. 

سرور 1: حقا؟ 

المتحدث 2: لا تتوقف عند هذا الحد. 

سرور 1: حقا؟