[Powered by Google Translate] [ترتيب BUBBLE] [JACKSON STEINKAMP جامعة هارفارد] [هذا CS50. CS50TV] فرز الفقاعة هو مثال على خوارزمية الفرز - وهذا هو، إجراء لفرز مجموعة من العناصر في تصاعدي أو تنازلي. على سبيل المثال، إذا أردت لفرز مجموعة تتألف من الأرقام [3، 5، 2، 9]، فإن التنفيذ الصحيح للفرز الفقاعة إرجاع فرز مجموعة [2، 3، 5، 9] في ترتيب تصاعدي. الآن، انا ذاهب الى شرح كيفية شبة الكود في الخوارزمية يعمل. 

دعونا نقول اننا فرز قائمة أعداد صحيحة من 5 - 3، 2، 9، 6، و 5. الخوارزمية يبدأ من خلال النظر في العناصر الأولين و 3 و 2، وفحص اذا كانا لا يزالان خارج الترتيب بالنسبة لبعضها البعض. فهي - 3 أكبر من 2. ليكون في ترتيب تصاعدي، ينبغي أن يكون العكس. لذلك، فإننا مقايضتهم. الآن لائحة يبدو مثل هذا: [2، 3، 9، 6، 5]. 

المقبل، ونحن ننظر إلى العناصر الثانية والثالثة و 3 و 9. انهم في الترتيب الصحيح بالنسبة لبعضها البعض. وهذا هو، 3 هو أقل من 9 حتى الخوارزمية لا مقايضتهم. المقبل، ونحن ننظر في 9 و 6. انهم خارج الترتيب. 

لذلك، نحن بحاجة إلى لمقايضتهم 9 هو أكبر من 6. وأخيرا، فإننا ننظر إلى أعداد صحيحة الماضيين، 9 و 5. انهم خارج الترتيب، لذلك يجب أن مقايضتهم. بعد مرور الكاملة الأولى من خلال القائمة، يبدو مثل هذا: [2، 3، 6، 5، 9]. ليس سيئا. يتم فرز ما يقرب من ذلك. ولكننا بحاجة إلى تشغيل من خلال قائمة مرة أخرى للحصول عليه مصنفة تماما. الاثنين هو أقل من 3، لذلك نحن لا مقايضتهم. 

ثلاثة هي أقل من 6، لذلك نحن لا مقايضتهم. ستة أكبر من 5. تبادلت نحن. ستة هو أقل من 9. نحن لا تبديل. بعد مرور الثاني من خلال، يبدو مثل هذا: [2، 3، 5، 6، 9]. الكمال. الآن، دعونا الكتابة في شبة الكود. في الأساس، ولكل عنصر في القائمة، ونحن بحاجة الى ان ننظر الى الامر والعنصر مباشرة من اليمين. إذا كانت خارج الترتيب بالنسبة لبعضها البعض - وهذا هو، إذا كان العنصر على اليسار أكبر من واحد على حق - يجب علينا مبادلة العنصرين. 

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

هذا هو الذهاب الى اتخاذ مرور واحد من خلال لفرز بشكل صحيح. [3، 2، 1] - والأسوأ هو أنه مع 3 عناصر مصنفة إلى الوراء، انه سيكون لاتخاذ 2 تكرار للترتيب. بعد واحد التكرار، انها [2، 1، 3]. عائدات الثاني مجموعة مصنفة [1، 2، 3]. حتى تعرف أنك لن تضطر للذهاب من خلال مجموعة، بشكل عام، أكثر من N-1 مرات، حيث n هو عدد العناصر في الصفيف. انه دعا فرز الفقاعة أكبر لأن العناصر تميل إلى "فقاعة المتابعة ' إلى اليمين بسرعة كبيرة. في الواقع، هذه الخوارزمية لديه السلوك مثيرة جدا للاهتمام. 

بعد تكرار م من خلال مجموعة كاملة، ويضمن أقصى اليمين عناصر م يمكن فرز في مكانها الصحيح. إذا كنت تريد أن ترى هذا لنفسك، يمكننا محاولة على قائمة الوراء تماما [9، 6، 5، 3، 2]. بعد مرور واحد من خلال القائمة بأكملها، [صوت الكتابة] [6، 9، 5، 3، 2]، [6، 5، 9، 3، 2]، [6، 5، 3، 9، 2]، [6، 5، 3، 2، 9] العنصر 9 هو أقصى اليمين في مكانها الصحيح. بعد الثانية المار، وسوف يكون ال 6 'فقاعات المتابعة "إلى أقصى اليمين المركز الثاني. العناصر اثنين على اليمنى - 6 و 9 - سيكون في أماكنهم الصحيحة بعد الأولين الاقدام مرور. 

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

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

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

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

فرز الفقاعة ليست بأي حال خوارزمية الفرز فعالة جدا أو سريع. في أسوأ الحالات وقت كبير O ² ن لأن لديك لجعل التكرار ن خلال قائمة التحقق من جميع العناصر ن كل تمريري، nxn = ن ². هذا يعني أن وقت التشغيل حيث وصل عدد من العناصر كنت الفرز الزيادات، وقت التشغيل يزيد quadratically. 

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