>> [عزف الموسيقى]
DOUG لويد: كل الحق، لذلك فقاعة النوع هو خوارزمية
يمكنك استخدامها لفرز مجموعة من العناصر.
دعونا نلقي نظرة على كيف يعمل.
>> وبالتالي فإن الفكرة الأساسية وراء فقاعة نوع هو هذا.
نريد عموما في الارتفاع عناصر قيمتها عادة إلى اليمين،
وخفض عناصر بقيمة عموما إلى اليسار، كما نتوقع.
نريد الأشياء السفلى لتكون على بداية، والأمور العليا
أن تكون في نهاية المطاف.
>> كيف نفعل ذلك؟
حسنا في التعليمات البرمجية شبة الكود، يمكننا القول، دعونا
مجموعة عداد المبادلة إلى قيمة غير الصفر.
سنرى ماذا نفعل ذلك في الثانية.
ثم نكرر ما يلي العملية حتى العداد تبادل 0،
أو حتى نجعل أي مقايضة على الإطلاق.
>> إعادة تعيين عداد المبادلة ل 0 إذا لم تكن بالفعل 0.
ثم ننظر في كل زوج المجاور من العناصر.
إذا كانت هذه العناصر هما ليس في النظام، ومقايضتهم،
وإضافة 1 إلى العداد المبادلة.
إذا كنت تفكر في هذا قبل أن تصور ذلك،
لاحظ أن هذا سوف تتحرك أقل عناصر قيمتها إلى اليسار
والعناصر إلى اليمين أعلى الكرام، القيام بفعالية ما نريد القيام به،
وهو تحرك تلك الجماعات العناصر في هذا الطريق.
دعونا تصور كيف يمكن لهذا قد تبدو باستخدام مجموعة لدينا
التي استخدمناها لاختبار من هذه الخوارزميات.
لدينا مجموعة غير مصنفة هنا مرة أخرى، يتضح من كل عناصر
يجري في أحمر.
وأنا وضعت مكافحة مبادلة بلدي إلى قيمة غير صفرية.
أنا اختار تعسفا 1-- سلبية انها ليست 0.
نريد أن نكرر هذه العملية حتى العداد المبادلة 0.
هذا هو السبب في أنني مجموعة مبادلة بلدي مضاد لبعض قيمة غير الصفر،
لأن خلاف ذلك أن مكافحة مبادلة تكون 0.
ونحن لن حتى بدء عملية الخوارزمية.
ذلك مرة أخرى، والخطوات are-- إعادة تعيين عداد مبادلة
0، ثم ننظر في كل المتاخمة الزوج، واذا كانا لا يزالان خارج الترتيب،
مقايضتهم، وإضافة 1 إلى العداد المبادلة.
لذلك دعونا نبدأ هذه العملية.
لذا فإن أول شيء نقوم به هو وضعناها العداد مقايضة مقابل 0
وبعد ذلك تبدأ في النظر في كل زوج المجاور.
>> لذلك علينا أولا أن تبدأ في النظر في 5 و 2.
ونحن نرى أن وجودهم خارج النظام ولذا فإننا مقايضتهم.
ونضيف 1 إلى العداد المبادلة.
وحتى الآن مكافحة مبادلة لدينا 1، و2 و 5 قد تم تبديل.
الآن نكرر العملية مرة أخرى.
>> ننظر إلى الزوج المجاور المقبل، 5 و1-- انهم ايضا من النظام،
لذلك نحن مقايضتهم وإضافة 1 إلى العداد المبادلة.
ثم ننظر إلى 5 و 3.
هم خارج الترتيب، لذلك نحن مبادلة لهم ونضيف 1 إلى العداد المبادلة.
ثم ننظر في 5 و 6.
انهم في النظام، لذلك نحن لا فعلا تحتاج إلى تبديل أي شيء هذه المرة.
ثم ننظر إلى 6 و 4.
انهم ايضا من النظام، لذلك نحن مبادلة لهم ونضيف 1 إلى العداد المبادلة.
>> لاحظ الآن ما حدث.
لقد انتقلنا 6 على طول الطريق حتى النهاية.
حتى في اختيار نوع، إذا كنت قد ينظر إلى الفيديو، ما فعلناه كان
لقد انتهى الأمر تحريك أصغر العناصر في بناء
مجموعة فرزها أساسا من اليسار إلى اليمين، من الأصغر إلى الأكبر.
في حالة فقاعة النوع، إذا نحن بعد هذه الخوارزمية معينة،
نحن فعلا على وشك أن بناء مجموعة فرزها من اليمين
إلى اليسار، من الأكبر إلى الأصغر.
لقد انفجر بشكل فعال 6، أكبر قيمة، على طول الطريق حتى النهاية.
>> وهكذا يمكن أن نعلن الآن أن التي تم فرزها،
وفي المستقبل iterations-- الذهاب من خلال مجموعة again--
ليس لدينا للنظر 6 بعد الآن.
ليس لدينا سوى أن تنظر العناصر غير مصنفة
عندما كنا نبحث في أزواج المجاورة.
وبذلك نكون قد أنهى واحدة تمر عبر فقاعة النوع.
وحتى الآن نعود إلى السؤال، كرر حتى العداد تبادل 0.
حسنا العداد مبادلة هو 4، لذلك نحن ذاهبون
للحفاظ على تكرار هذه العملية مرة أخرى.
>> ونحن في طريقنا إلى إعادة تعيين العداد مبادلة 0، وإلقاء نظرة على كل زوج المجاور.
حتى نبدأ مع 2 و 1-- انهم من النظام، لذلك نحن مقايضتهم
ونضيف 1 إلى العداد المبادلة.
2 و 3، وانهم في النظام.
نحن لسنا بحاجة لفعل أي شيء.
3 و 5 في النظام.
نحن لسنا بحاجة لفعل أي شيء هناك.
>> 5 و 4، يكونون خارج من النظام، ولذا فإننا
تحتاج لمقايضتهم وإضافة 1 إلى العداد المبادلة.
ونحن الآن قد انتقلت 5، ثاني أكبر عنصر،
إلى نهاية الجزء فرزها.
لذلك يمكن أن نطلق عليه الآن أن جزء من جزء فرزها.
>> الآن كنت تبحث في الشاشة وربما يمكن أن أقول،
كما يمكنني أن مجموعة يتم فرز الآن.
ولكننا لا يمكن أن يثبت ذلك حتى الآن.
ليس لدينا ضمانة هذا ما فرزها.
ولكن هذا هو المكان الذي مقايضة مكافحة ذاهب الى حيز اللعب.
>> ولذا فإننا قد أكملت تمريرة.
العداد المبادلة هو 2.
لذلك نحن في طريقنا للتكرار هذه العملية مرة أخرى،
كرر حتى العداد تبادل 0.
إعادة تعيين عداد المبادلة ل0.
لذلك سنقوم إعادة تعيينها.
>> ننظر الآن في كل زوج المجاور.
هذا في النظام، 1 و 2.
2 و 3 في النظام.
3 و 4 في النظام.
حتى في هذه النقطة، لاحظ أننا قد أكملت أبحث في كل زوج المجاور،
ولكن العداد مبادلة ما زالت 0.
>> إذا لم يكن لدينا للتبديل أي عناصر، ثم أنها
يجب أن تكون في النظام، من قبل بموجب هذه العملية.
وهكذا كفاءة من نوع ما، أحب أن العلماء أننا الكمبيوتر،
ويمكن أن نعلن الآن مجموعة كاملة يجب
يتم فرزها، لأننا لم يجب أن مبادلة أي عناصر.
هذا لطيف جدا.
>> إذن ما هو أسوأ حالة السيناريو مع فقاعة نوع؟
في أسوأ الحالات المصفوفة هي في ترتيب عكسي تماما،
ولذا يتعين علينا أن فقاعة كل من العناصر الكبيرة فقط
على طول الطريق عبر مجموعة.
ونحن على نحو فعال أيضا ل فقاعة كل العناصر الصغيرة العودة
على طول الطريق عبر مجموعة أيضا.
لذلك كل من العناصر ن أن تتحرك عبر كل من العناصر غيرها ن.
لذلك هذا هو السيناريو الأسوأ.
في أفضل الأحوال السيناريو رغم ذلك، وهذا هو
تختلف قليلا عن اختيار نوع.
مجموعة بالفعل فرز عندما نذهب في.
ليس لدينا لجعل أي مقايضة على مرور الأول.
لذلك قد يكون لدينا للنظر في أقل العناصر، أليس كذلك؟
ليس لدينا لتكرار هذا معالجة عدد من مرات.
>> فماذا يعني ذلك؟
إذن ما هو أسوأ سيناريو لفقاعة النوع، وما هو
أفضل سيناريو عن فقاعة الفرز؟
هل تخمين هذا؟
في أسوأ حال كان لديك لتكرار في جميع العناصر ن ن مرات.
لذلك ن تربيع أسوأ الحالات.
>> إذا كان الصفيف هي تماما على الرغم من فرزها، أنت فقط
يجب أن ننظر في كل عناصر مرة واحدة.
وإذا العداد مبادلة ما زالت 0، هل يمكن القول يتم فرز هذه المجموعة.
وحتى في أفضل الأحوال، وهذا هو في الواقع أفضل من اختيار
sort-- انها أوميغا ن.
>> أنا دوغ ويد.
هذا هو CS50.