[เล่นเพลง] DOUG LLOYD: เรียงลำดับการคัดเลือกเป็น อัลกอริทึมที่เป็นคุณอาจคาดหวัง เรียงลำดับชุดขององค์ประกอบ และขั้นตอนวิธีการเรียกคืน เป็นขั้นตอนโดยขั้นตอนการตั้งค่า คำแนะนำสำหรับการงาน 

เรียงลำดับในการเลือก แนวคิดพื้นฐานคือนี้ หาองค์ประกอบไม่ได้เรียงลำดับและมีขนาดเล็กที่สุด เพิ่มไปยังจุดสิ้นสุดของรายการที่เรียงลำดับ ได้อย่างมีประสิทธิภาพสิ่งนี้จะสร้าง รายการที่เรียงลำดับองค์ประกอบหนึ่งที่เวลา ทำลายมันลงไป pseudocode เราสามารถระบุขั้นตอนวิธีนี้ ดังต่อไปนี้ให้ทำซ้ำเช่นนี้จนกว่า ไม่มีองค์ประกอบไม่ได้เรียงลำดับยังคงอยู่ ค้นหาผ่านบ้านทั่วไป ข้อมูลเพื่อหาค่าที่น้อยที่สุด แล้วสลับค่าที่น้อยที่สุดด้วย องค์ประกอบแรกของส่วนที่ไม่ได้เรียงลำดับ 

มันอาจช่วยให้เห็นภาพนี้ ดังนั้นลองมาดูที่นี้ ดังนั้นนี้ผมยืนยันการเป็น อาเรย์ไม่ได้เรียงลำดับและฉันได้ ระบุว่าโดยระบุว่าทั้งหมด ขององค์ประกอบที่มีสีแดง พวกเขาจะไม่เรียงยัง นี่คือทั้งหมด ส่วนที่ไม่ได้เรียงลำดับของอาร์เรย์ 

ถ้าอย่างนั้นเราไปผ่านขั้นตอนของ เลือกการเรียงลำดับการจัดเรียงอาร์เรย์นี้ ดังนั้นอีกครั้งเราจะทำซ้ำ จนไม่ได้เรียงลำดับองค์ประกอบยังคงไม่มี เราจะค้นหาผ่าน ข้อมูลเพื่อหาค่าที่น้อยที่สุด แล้วสลับค่าที่กับ องค์ประกอบแรกของส่วนที่ไม่ได้เรียงลำดับ 

ตอนนี้อีกทั้ง อาร์เรย์เป็นส่วนที่ไม่ได้เรียงลำดับ ทุกองค์ประกอบสีแดงที่มีการเรียงลำดับ ดังนั้นเราค้นหาผ่านและ เราพบว่าค่าที่น้อยที่สุด เราเริ่มต้นที่จุดเริ่มต้น เราไปที่ท้ายที่สุด เราพบว่าค่าที่น้อยที่สุดคือหนึ่ง เพื่อให้เป็นส่วนหนึ่ง และจากนั้นส่วนที่สองสลับค่าที่มี องค์ประกอบแรกของส่วนที่ไม่ได้เรียงลำดับ, หรือองค์ประกอบสีแดงเป็นครั้งแรก 

ในกรณีนี้ที่จะเป็น ห้าดังนั้นเราจึงสลับหนึ่งในห้า เมื่อเราทำเช่นนี้เราสามารถ สายตาเห็นว่าเราได้ ย้ายที่เล็กที่สุดองค์ประกอบมูลค่า ของอาร์เรย์ที่จะเริ่มต้น การเรียงลำดับได้อย่างมีประสิทธิภาพในสภาพแวดล้อมที่ 

และเพื่อให้เราสามารถยืนยันได้แน่นอน และรัฐที่หนึ่งจะเรียงลำดับ และเพื่อให้เราจะแสดงให้เห็นส่วนที่เรียง ของอาร์เรย์ของเราด้วยการระบายสีมันสีฟ้า 

ตอนนี้เราก็ทำซ้ำขั้นตอนอีกครั้ง เราค้นหาผ่านส่วนที่ไม่ได้เรียงลำดับของ อาเรย์เพื่อหาองค์ประกอบที่เล็กที่สุด ในกรณีนี้ก็สอง 

เราสลับกับครั้งแรก องค์ประกอบของส่วนที่ไม่ได้เรียงลำดับ ในกรณีนี้ทั้งสองยังเกิดขึ้นเป็น องค์ประกอบแรกของส่วนที่ไม่ได้เรียงลำดับ ดังนั้นเราจึงสลับสองกับตัวเอง ซึ่งจริงๆเพียงใบสอง มันอยู่ที่ไหนและจะเรียง อย่างต่อเนื่องในวันที่เราค้นหาผ่าน เพื่อหาองค์ประกอบที่เล็กที่สุด มันเป็นสาม เราสลับกับครั้งแรก องค์ประกอบซึ่งเป็นห้า และตอนนี้สามจะถูกจัดเรียง 

เราค้นหาผ่านอีกครั้งและเรา หาองค์ประกอบที่เล็กที่สุดคือสี่ เราสลับกับองค์ประกอบแรกของ ส่วนที่ไม่ได้เรียงลำดับและตอนนี้ทั้งสี่จะถูกจัดเรียง 

เราพบว่าห้าคือ องค์ประกอบที่เล็กที่สุด เราสลับกับครั้งแรก องค์ประกอบของส่วนที่ไม่ได้เรียงลำดับ และตอนนี้จะถูกจัดเรียงห้า 

และแล้วในที่สุดของเรา ส่วนที่ไม่ได้เรียงลำดับประกอบด้วย เพียงองค์ประกอบเดียว เพื่อให้เราค้นหาผ่าน และเราพบว่าหกเป็น ที่เล็กที่สุดและในความเป็นจริงเพียงส่วนประกอบ และจากนั้นเราสามารถระบุว่ามันจะถูกจัดเรียง และตอนนี้เราได้เปลี่ยนอาร์เรย์ของเรา จากการไม่ได้เรียงลำดับได้อย่างสมบูรณ์ สีแดงที่จะเรียงอย่างสมบูรณ์ สีฟ้าโดยใช้การเลือกการจัดเรียง 

ดังนั้นสิ่งที่สถานการณ์กรณีที่เลวร้ายที่สุดที่นี่? ได้ดีในที่เลวร้ายที่สุดแน่นอน กรณีที่เราจะต้องดูมากกว่า ทุกองค์ประกอบของอาร์เรย์จะ หาองค์ประกอบไม่ได้เรียงลำดับที่เล็กที่สุด และเราจะต้องทำซ้ำ กระบวนการนี​​้ครั้ง n ครั้งเดียวสำหรับแต่ละองค์ประกอบของอาร์เรย์ เพราะเราเพียง แต่ในขั้นตอนวิธีนี้ การจัดเรียงองค์ประกอบหนึ่งในเวลา 

สถานการณ์กรณีที่ดีที่สุดคืออะไร? ดีมันเหมือนกันใช่มั้ย? เราจริงยังคงต้องก้าวผ่าน ทุกองค์ประกอบหนึ่งของอาร์เรย์ เพื่อยืนยันว่ามันคือ ในความเป็นจริงองค์ประกอบที่เล็กที่สุด 

ดังนั้นรันไทม์กรณีที่เลวร้ายเรา ต้องทำซ้ำกระบวนการ n ครั้ง ครั้งเดียวสำหรับแต่ละองค์ประกอบ n และในกรณีที่ดีที่สุด เราจะต้องทำเช่นเดียวกัน 

ดังนั้นคิดกลับไปของเรา กล่องคอมพิวเตอร์ที่ซับซ้อน, สิ่งที่คุณคิดว่าเป็นที่เลวร้ายที่สุด รันไทม์กรณีสำหรับการจัดเรียงการเลือก? อะไรที่คุณคิดว่าดีที่สุด รันไทม์กรณีสำหรับการจัดเรียงการเลือก? 

คุณคิดว่า Big O ของ n ยืด, และบิ๊กโอเมก้าสี่เหลี่ยมของ n? คุณจะได้รับสิทธิ เหล่านี้คือในความเป็นจริง กรณีที่เลวร้ายที่สุดและกรณีการทำงานที่ดีที่สุด ครั้งสำหรับการจัดเรียงการเลือก 

ฉันลอยด์ดั๊ก นี่คือ CS50