Tip:
Highlight text to annotate it
X
>> [เล่นเพลง]
DOUG LLOYD: เรียงลำดับการคัดเลือกเป็น อัลกอริทึมที่เป็นคุณอาจคาดหวัง
เรียงลำดับชุดขององค์ประกอบ
และขั้นตอนวิธีการเรียกคืน เป็นขั้นตอนโดยขั้นตอนการตั้งค่า
คำแนะนำสำหรับการงาน
>> เรียงลำดับในการเลือก แนวคิดพื้นฐานคือนี้
หาองค์ประกอบไม่ได้เรียงลำดับและมีขนาดเล็กที่สุด เพิ่มไปยังจุดสิ้นสุดของรายการที่เรียงลำดับ
ได้อย่างมีประสิทธิภาพสิ่งนี้จะสร้าง รายการที่เรียงลำดับองค์ประกอบหนึ่งที่เวลา
ทำลายมันลงไป pseudocode เราสามารถระบุขั้นตอนวิธีนี้
ดังต่อไปนี้ให้ทำซ้ำเช่นนี้จนกว่า ไม่มีองค์ประกอบไม่ได้เรียงลำดับยังคงอยู่
ค้นหาผ่านบ้านทั่วไป ข้อมูลเพื่อหาค่าที่น้อยที่สุด
แล้วสลับค่าที่น้อยที่สุดด้วย องค์ประกอบแรกของส่วนที่ไม่ได้เรียงลำดับ
>> มันอาจช่วยให้เห็นภาพนี้ ดังนั้นลองมาดูที่นี้
ดังนั้นนี้ผมยืนยันการเป็น อาเรย์ไม่ได้เรียงลำดับและฉันได้
ระบุว่าโดยระบุว่าทั้งหมด ขององค์ประกอบที่มีสีแดง
พวกเขาจะไม่เรียงยัง
นี่คือทั้งหมด ส่วนที่ไม่ได้เรียงลำดับของอาร์เรย์
>> ถ้าอย่างนั้นเราไปผ่านขั้นตอนของ เลือกการเรียงลำดับการจัดเรียงอาร์เรย์นี้
ดังนั้นอีกครั้งเราจะทำซ้ำ จนไม่ได้เรียงลำดับองค์ประกอบยังคงไม่มี
เราจะค้นหาผ่าน ข้อมูลเพื่อหาค่าที่น้อยที่สุด
แล้วสลับค่าที่กับ องค์ประกอบแรกของส่วนที่ไม่ได้เรียงลำดับ
>> ตอนนี้อีกทั้ง อาร์เรย์เป็นส่วนที่ไม่ได้เรียงลำดับ
ทุกองค์ประกอบสีแดงที่มีการเรียงลำดับ
ดังนั้นเราค้นหาผ่านและ เราพบว่าค่าที่น้อยที่สุด
เราเริ่มต้นที่จุดเริ่มต้น เราไปที่ท้ายที่สุด
เราพบว่าค่าที่น้อยที่สุดคือหนึ่ง
เพื่อให้เป็นส่วนหนึ่ง
และจากนั้นส่วนที่สองสลับค่าที่มี องค์ประกอบแรกของส่วนที่ไม่ได้เรียงลำดับ,
หรือองค์ประกอบสีแดงเป็นครั้งแรก
>> ในกรณีนี้ที่จะเป็น ห้าดังนั้นเราจึงสลับหนึ่งในห้า
เมื่อเราทำเช่นนี้เราสามารถ สายตาเห็นว่าเราได้
ย้ายที่เล็กที่สุดองค์ประกอบมูลค่า ของอาร์เรย์ที่จะเริ่มต้น
การเรียงลำดับได้อย่างมีประสิทธิภาพในสภาพแวดล้อมที่
>> และเพื่อให้เราสามารถยืนยันได้แน่นอน และรัฐที่หนึ่งจะเรียงลำดับ
และเพื่อให้เราจะแสดงให้เห็นส่วนที่เรียง ของอาร์เรย์ของเราด้วยการระบายสีมันสีฟ้า
>> ตอนนี้เราก็ทำซ้ำขั้นตอนอีกครั้ง
เราค้นหาผ่านส่วนที่ไม่ได้เรียงลำดับของ อาเรย์เพื่อหาองค์ประกอบที่เล็กที่สุด
ในกรณีนี้ก็สอง
>> เราสลับกับครั้งแรก องค์ประกอบของส่วนที่ไม่ได้เรียงลำดับ
ในกรณีนี้ทั้งสองยังเกิดขึ้นเป็น องค์ประกอบแรกของส่วนที่ไม่ได้เรียงลำดับ
ดังนั้นเราจึงสลับสองกับตัวเอง ซึ่งจริงๆเพียงใบสอง
มันอยู่ที่ไหนและจะเรียง
อย่างต่อเนื่องในวันที่เราค้นหาผ่าน เพื่อหาองค์ประกอบที่เล็กที่สุด
มันเป็นสาม
เราสลับกับครั้งแรก องค์ประกอบซึ่งเป็นห้า
และตอนนี้สามจะถูกจัดเรียง
>> เราค้นหาผ่านอีกครั้งและเรา หาองค์ประกอบที่เล็กที่สุดคือสี่
เราสลับกับองค์ประกอบแรกของ ส่วนที่ไม่ได้เรียงลำดับและตอนนี้ทั้งสี่จะถูกจัดเรียง
>> เราพบว่าห้าคือ องค์ประกอบที่เล็กที่สุด
เราสลับกับครั้งแรก องค์ประกอบของส่วนที่ไม่ได้เรียงลำดับ
และตอนนี้จะถูกจัดเรียงห้า
>> และแล้วในที่สุดของเรา ส่วนที่ไม่ได้เรียงลำดับประกอบด้วย
เพียงองค์ประกอบเดียว เพื่อให้เราค้นหาผ่าน
และเราพบว่าหกเป็น ที่เล็กที่สุดและในความเป็นจริงเพียงส่วนประกอบ
และจากนั้นเราสามารถระบุว่ามันจะถูกจัดเรียง
และตอนนี้เราได้เปลี่ยนอาร์เรย์ของเรา จากการไม่ได้เรียงลำดับได้อย่างสมบูรณ์
สีแดงที่จะเรียงอย่างสมบูรณ์ สีฟ้าโดยใช้การเลือกการจัดเรียง
>> ดังนั้นสิ่งที่สถานการณ์กรณีที่เลวร้ายที่สุดที่นี่?
ได้ดีในที่เลวร้ายที่สุดแน่นอน กรณีที่เราจะต้องดูมากกว่า
ทุกองค์ประกอบของอาร์เรย์จะ หาองค์ประกอบไม่ได้เรียงลำดับที่เล็กที่สุด
และเราจะต้องทำซ้ำ กระบวนการนี้ครั้ง n
ครั้งเดียวสำหรับแต่ละองค์ประกอบของอาร์เรย์ เพราะเราเพียง แต่ในขั้นตอนวิธีนี้
การจัดเรียงองค์ประกอบหนึ่งในเวลา
>> สถานการณ์กรณีที่ดีที่สุดคืออะไร?
ดีมันเหมือนกันใช่มั้ย?
เราจริงยังคงต้องก้าวผ่าน ทุกองค์ประกอบหนึ่งของอาร์เรย์
เพื่อยืนยันว่ามันคือ ในความเป็นจริงองค์ประกอบที่เล็กที่สุด
>> ดังนั้นรันไทม์กรณีที่เลวร้ายเรา ต้องทำซ้ำกระบวนการ n ครั้ง
ครั้งเดียวสำหรับแต่ละองค์ประกอบ n
และในกรณีที่ดีที่สุด เราจะต้องทำเช่นเดียวกัน
>> ดังนั้นคิดกลับไปของเรา กล่องคอมพิวเตอร์ที่ซับซ้อน,
สิ่งที่คุณคิดว่าเป็นที่เลวร้ายที่สุด รันไทม์กรณีสำหรับการจัดเรียงการเลือก?
อะไรที่คุณคิดว่าดีที่สุด รันไทม์กรณีสำหรับการจัดเรียงการเลือก?
>> คุณคิดว่า Big O ของ n ยืด, และบิ๊กโอเมก้าสี่เหลี่ยมของ n?
คุณจะได้รับสิทธิ
เหล่านี้คือในความเป็นจริง กรณีที่เลวร้ายที่สุดและกรณีการทำงานที่ดีที่สุด
ครั้งสำหรับการจัดเรียงการเลือก
>> ฉันลอยด์ดั๊ก
นี่คือ CS50