[Powered by Google Translate] TOMMY: دعونا نلقي نظرة على نوع الاختيار، خوارزمية
لأخذ قائمة من الأرقام والفرز لهم.
خوارزمية، تذكر، هو مجرد خطوة بخطوة
الإجراء لإنجاز المهمة.
الفكرة الأساسية وراء اختيار نوع هو تقسيم
لدينا قائمة إلى جزئين -
جزء مصنفة وجزء لم يتم فرزها.
في كل خطوة من خطوات الخوارزمية، يتم نقل عدد من
لم يتم فرزها جزء إلى جزء مصنفة حتى النهاية
يتم فرز القائمة بأكملها.
حتى هنا قائمة من ستة أرقام -
23، 42، 4، 16، 8، و 15.
الآن لم يتم فرزها يعتبر القائمة بأكملها.
حتى ولو قد مثل 16 عدد تكون بالفعل في الصحيح لها
الموقع، خوارزمية لديها أي وسيلة لمعرفة ذلك حتى
يتم فرز القائمة بأكملها.
لذلك نحن سنعتبر كل عدد إلى أن لم يتم فرزها حتى نحصل فرز
ذلك بأنفسنا.
ونحن نعلم أننا نريد أن تكون قائمة في ترتيب تصاعدي.
وهكذا لن نريد لبناء جزء من قائمتنا مصنفة
من اليسار إلى اليمين، من الأصغر إلى الأكبر.
للقيام بذلك، وسوف نحتاج إلى العثور على العنصر الحد الأدنى التي لم يتم فرزها
ووضعها في نهاية الجزء فرزها.
لأن غير مصنفة هذه القائمة، والطريقة الوحيدة لذلك هي ان
ننظر في كل عنصر في جزء لم يتم فرزها، وتذكر
العنصر الذي هو أدنى ومقارنة
كل عنصر على ذلك.
ولذا فإننا سوف ننظر أولا إلى 23.
هذا هو العنصر الأول رأيناه، لذلك علينا أن نتذكر سوف
على أنها الحد الأدنى.
القادم سوف نبحث في 42.
42 هو أكبر من 23، حتى 23 هو لا يزال الحد الأدنى.
التالي هو (4) الذي هو أقل من 23، لذلك نحن سوف نتذكر 4
باعتبارها تمثل الحد الأدنى الجديد.
القادم هو 16 وهو أكبر من 4، SO 4
لا يزال الحد الأدنى.
8 هو أكبر من 4، و 15 أكبر من 4، 4 يجب أن يكون ذلك
أصغر عنصر لم يتم فرزها.
على الرغم من ذلك كبشر يمكننا أن نرى على الفور أن 4 هو
العنصر الحد الأدنى، خوارزمية لدينا يحتاج إلى النظر في
كل عنصر لم يتم فرزها حتى بعد وجدنا أن 4 -
الحد الأدنى عنصر.
حتى الآن بعد أن وجدنا أن الحد الأدنى عنصر، 4، سوف نريد
لنقلها إلى الجزء مصنفة من القائمة.
حيث أن هذه هي الخطوة الأولى، وهذا يعني أننا نريد ان نضع 4 في
بداية القائمة.
الآن 23 هو في بداية قائمة، لذلك
دعونا مبادلة 4 و 23 و.
حتى الآن لدينا قائمة يبدو مثل هذا.
ونحن نعلم أن 4 يجب أن يكون في موقعه النهائي، لأنه
كل من أصغر عنصر والعنصر في بداية
من القائمة.
ولذلك فإن هذا يعني أننا لسنا في حاجة من أي وقت مضى للانتقال مرة أخرى.
لذلك دعونا كرر هذه العملية لإضافة عنصر آخر إلى
فرز جزء من القائمة.
ونحن نعلم أننا لسنا في حاجة للنظر في 4، لأنه
فرز بالفعل.
حتى نتمكن من البدء في ال 42، والتي سنقوم كما تذكر
الحد الأدنى عنصر.
حتى القادم سوف نبحث في ال 23 وهو أقل من 42 عاما، لذلك نحن
تذكر 23 هو الحد الأدنى الجديد.
المقبل نرى ال 16 التي هي أقل من 23، لذلك
16 هو الحد الأدنى الجديد.
الآن ننظر إلى 8 التي هي أقل من 16، لذلك
8 هو الحد الأدنى الجديد.
وأخيرا 8 هو أقل من 15، لذلك نحن نعلم أن 8 هو الحد الأدنى
لم يتم فرزها عنصر.
وهذا يعني أننا يجب أن إلحاق 8 للفرز
جزء من القائمة.
الآن 4 هو العنصر مصنفة فقط، لذلك نحن نريد لوضع
التالي من 8 إلى 4.
منذ 42 هو العنصر الأول في جزء لم يتم فرزها من
القائمة، سوف نريد أن مبادلة 42 و (8) و.
حتى الآن لدينا قائمة يبدو مثل هذا.
4 و 8 تمثل جزء من فرز القائمة، وعلى
الأرقام المتبقية التي لم يتم فرزها تمثل
جزء من القائمة.
لذلك دعونا مواصلة التكرار آخر.
نبدأ مع 23 هذه المرة، لأننا لسنا في حاجة للنظر في
و4 و ال 8 بعد الآن لأنهم
بالفعل تم فرزها.
16 هو أقل من 23، لذلك علينا أن نتذكر سوف
16 والحد الأدنى الجديد.
16 هو أقل من 42، ولكن 15 هو أقل من 16، يجب أن تكون الآن 15
العنصر الحد الأدنى التي لم يتم فرزها.
حتى الآن نحن نريد لمبادلة ال 15 و23 إلى
تعطينا هذه القائمة.
الجزء مصنفة من قائمة تتألف من 8 و 4 و 15، و
ومازال لم يتم فرزها هذه العناصر.
ولكن مجرد أن ذلك يحدث العنصر التالي لم يتم فرزها، 16،
يتم فرز بالفعل.
ومع ذلك، ليس هناك طريقة لمعرفة خوارزمية لدينا أن 16
هو بالفعل في موقعه الصحيح، لذلك نحن بحاجة إلى
كرر نفس العملية بالضبط.
لذلك نرى أن 16 أقل من 42 عاما، و 16 أقل من 23، حتى
يجب أن تكون 16 عنصر كحد أدنى.
انه من المستحيل لمبادلة هذا العنصر مع نفسه، حتى نتمكن من
ببساطة ترك في هذا الموقع.
لذلك نحن بحاجة تمريرة واحدة أكثر من أنظمتنا.
42 هو أكبر من 23، لذلك يجب أن يكون 23
لم يتم فرزها العنصر الحد الأدنى.
وبمجرد أن مبادلة 23 و 42، ونحن في نهاية المطاف مع النهائي لدينا
فرز قائمة -
4، 8، 15، 16، 23، 42.
42 ونحن نعلم يجب أن تكون في المكان الصحيح لأنه هو
ترك العنصر الوحيد، وهذا نوع الاختيار.
دعونا الآن إضفاء الطابع الرسمي على خوارزمية لدينا مع بعض
شبة الكود.
على سطر واحد، يمكننا أن نرى أننا في حاجة إلى دمج أكثر من
كل عنصر من عناصر القائمة.
ما عدا العنصر الأخير، منذ العنصر 1
يتم فرز قائمة بالفعل.
على السطر الثاني، نرى أن العنصر الأول من لم يتم فرزها
جزء من القائمة أن تكون الحد الأدنى، كما فعلنا مع شركائنا
سبيل المثال، لذلك لدينا شيء للمقارنة.
السطر الثالث يبدأ حلقة الثانية التي نحن iterate عبر
كل عنصر لم يتم فرزها.
ونحن نعلم أن بعد أن التكرار، الجزء مصنفة
يجب أن يكون لدينا قائمة من العناصر أنا فيه منذ كل خطوة
أنواع عنصر واحد.
لذا يجب أن يكون العنصر الأول التي لم يتم فرزها في المركز الأول بالإضافة إلى 1.
على خط الأربعة، قارنا العنصر الحالي إلى الحد الأدنى
العنصر الذي رأيناه حتى الآن.
إذا كان العنصر الحالي هو أصغر من الحد الأدنى
العنصر، ثم علينا أن نتذكر العنصر الحالي والجديد
الحد الأدنى على السطر الخامس.
وأخيرا، على خطوط ستة وسبعة، ونحن مبادلة الحد الأدنى
عنصر مع العنصر لم يتم فرزها أولا، وبالتالي
بإضافته إلى جزء من فرز القائمة.
مرة واحدة لدينا خوارزمية، سؤال مهم أن نسأل
عن انفسنا والمبرمجين ومتى لم تأخذ؟
سنطلب للمرة الأولى مسألة كم من الوقت يستغرق لهذا
خوارزمية لتشغيل في أسوأ الأحوال؟
أذكر أننا نمثل هذا التشغيل
الوقت مع تدوين O كبيرة.
من أجل تحديد العنصر الحد الأدنى التي لم يتم فرزها، ونحن
كان أساسا لمقارنة كل عنصر في القائمة ل
كل عنصر آخر في القائمة.
حدسي، وهذا يبدو وكأنه عملية من O ن المربعة.
أبحث في شبة الكود لدينا، لدينا أيضا حلقة متداخلة داخل
آخر حلقة، الذي يبدو في الواقع وكأنه O
ن عملية المربعة.
ومع ذلك، تذكر أننا لم تكن في حاجة للنظر على مدى
قائمة كاملة عند تحديد العنصر الحد الأدنى التي لم يتم فرزها؟
مرة كنا نعرف أن فرز 4، على سبيل المثال، لم نكن
بحاجة الى ان ننظر في الامر مرة اخرى.
فهل هذا أقل وقت التشغيل؟
لدينا قائمة من طول 6، نحن في حاجة لجعل 5
مقارنات للعنصر الأول، وأربعة للمقارنات
والعنصر الثاني، وهلم جرا.
وهذا يعني أن العدد الإجمالي للخطوات هو مجموع
الأعداد الصحيحة من 1 إلى طول قائمة ناقص 1.
يمكننا تمثيل هذا مع الجمع.
ونحن لن نذهب إلى summations هنا.
ولكن تبين أن هذا الجمع يساوي أضعاف ن
ن ناقص 1 أكثر من 2.
أو مكافئ، N تربيع ناقص أكثر من 2 ن أكثر من 2.
عندما نتحدث عن وقت مقارب، وهذا المصطلح ن التربيعية
سوف تهيمن على هذا المصطلح ن.
ذلك النوع من الاختيار هو O ن المربعة.
أذكر أنه في مثالنا، نوع لا تزال هناك حاجة لاختيار
معرفة ما إذا كان الرقم الذي تم فرز بالفعل
تحتاج إلى نقلها.
بحيث يعني أنه إذا ركضنا نوع الاختيار بالفعل على مدى
فرز قائمة، فإن ذلك يتطلب نفس العدد من الخطوات لأنها
متى بصدم قائمة لم يتم فرزها تماما.
ذلك نوع الاختيار لديه أداء أفضل حالة ن مربع،
التي نمثلها مع أوميغا ن المربعة.
وهذا كل شيء عن نوع الاختيار.
مجرد واحدة من العديد من الخوارزميات وسعنا
استخدامها لفرز قائمة.
اسمي تومي، وهذا هو CS50.