>> [เล่นเพลง]
DOUG LLOYD: สิทธิทั้งหมดเพื่อ การจัดเรียงฟองเป็นอัลกอริทึม
คุณสามารถใช้ในการจัดเรียงชุดขององค์ประกอบ
ลองมาดูที่วิธีการทำงาน
>> ดังนั้นความคิดพื้นฐานที่อยู่เบื้องหลัง การจัดเรียงฟองนี้
โดยทั่วไปเราต้องการที่จะย้ายที่สูงขึ้น องค์ประกอบโดยทั่วไปจะมีมูลค่าที่เหมาะสม
และลดองค์ประกอบมูลค่าทั่วไป ไปทางซ้ายในขณะที่เราคาดว่าจะได้
เราต้องการสิ่งที่ต่ำกว่าจะเป็นที่ จุดเริ่มต้นและสิ่งที่สูงขึ้น
จะเป็นที่สิ้นสุด
>> เราจะทำเช่นนี้ได้อย่างไร?
ดีในรหัส pseudocode, เราอาจจะบอกว่าขอ
ตั้งเคาน์เตอร์แลกเปลี่ยนที่ไม่ใช่ศูนย์ค่า
เราจะเห็นว่าทำไมเราทำอย่างนั้นในครั้งที่สอง
แล้วเราทำซ้ำดังต่อไปนี้ กระบวนการจนกว่าเคาน์เตอร์แลกเปลี่ยนเป็น 0
หรือจนกว่าเราทำสัญญาแลกเปลี่ยนที่ไม่ทั้งหมด
>> รีเซ็ตเคาน์เตอร์แลกเปลี่ยนไป 0 ถ้ามันไม่ได้ 0
แล้วมองไปที่ทุก คู่ที่อยู่ติดกันขององค์ประกอบ
หากทั้งสององค์ประกอบ ไม่ได้อยู่ในการสั่งซื้อสลับพวกเขา
และเพิ่ม 1 ถึงเคาน์เตอร์แลกเปลี่ยน
หากคุณกำลังคิดเกี่ยวกับ ก่อนที่คุณจะเห็นภาพนั้น
สังเกตเห็นว่าเรื่องนี้จะย้ายที่ต่ำกว่า องค์ประกอบมูลค่าไปทางซ้าย
และองค์ประกอบที่มีมูลค่าสูงขึ้นไปทางขวา ได้อย่างมีประสิทธิภาพทำสิ่งที่เราต้องการจะทำ
ซึ่งเป็นกลุ่มผู้ที่ย้าย ขององค์ประกอบในทางที่
ขอเห็นภาพว่านี้ อาจมีลักษณะการใช้อาร์เรย์ของเรา
ที่เราใช้ในการทดสอบ จากขั้นตอนวิธีการเหล่านี้
เรามีอาร์เรย์ที่ไม่ได้เรียงลำดับนี่อีกครั้ง ระบุโดยทุกองค์ประกอบ
อยู่ในสีแดง
และเราจะตั้งเคาน์เตอร์แลกเปลี่ยนของฉัน เป็นค่าที่ไม่ใช่ศูนย์
ฉันเลือกโดยพลการ 1- เชิงลบก็ไม่ได้ 0
เราต้องการที่จะทำซ้ำขั้นตอนนี้ จนกว่าเคาน์เตอร์แลกเปลี่ยนเป็น 0
นี่คือเหตุผลที่ผมตั้งการแลกของฉัน สวนทางกับค่าบางอย่างที่ไม่ใช่ศูนย์
เพราะมิฉะนั้น แลกเปลี่ยนเคาน์เตอร์จะเป็น 0
เราจะไม่ได้เริ่มต้น กระบวนการของขั้นตอนวิธี
ดังนั้นอีกครั้งขั้นตอน are-- รีเซ็ตเคาน์เตอร์แลกเปลี่ยน
0 แล้วมองไปที่ทุกคนที่อยู่ติดกัน คู่และถ้าพวกเขากำลังออกคำสั่ง
สลับพวกเขาและเพิ่ม 1 ไปที่เคาน์เตอร์แลกเปลี่ยน
ดังนั้นขอเริ่มต้นกระบวนการนี​​้
ดังนั้นสิ่งแรกที่เราทำคือ เราตั้งเคาน์เตอร์แลกเปลี่ยนเป็น 0
และจากนั้นเราเริ่มมองหา ในแต่ละคู่ที่อยู่ติดกัน
>> ดังนั้นเราจึงเริ่มมองหาที่ 5 และ 2
เรามาดูกันว่าพวกเขาจะออกจาก สั่งซื้อและเพื่อให้เราสลับพวกเขา
และเราเพิ่ม 1 ไปที่เคาน์เตอร์แลกเปลี่ยน
ดังนั้นตอนนี้เคาน์เตอร์แลกเปลี่ยนของเราคือ 1, และ 2 และ 5 ได้รับการเปลี่ยน
ตอนนี้เราทำซ้ำขั้นตอนอีกครั้ง
>> เรามองไปที่คู่ที่อยู่ติดกันต่อไป 1- 5 และพวกเขายังออกคำสั่ง
ดังนั้นเราจึงสลับพวกเขาและเพิ่ม 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
>> ถ้าเราไม่ต้องเปลี่ยน องค์ประกอบใด ๆ แล้วพวกเขา
จะต้องอยู่ในคำสั่งโดย อาศัยอำนาจตามความในขั้นตอนนี้
และเพื่อประสิทธิภาพของแปลก, ที่เรารักนักวิทยาศาสตร์คอมพิวเตอร์,
คือตอนนี้เราสามารถประกาศ อาร์เรย์ทั้งหมดต้อง
จัดเรียงเพราะเราไม่ได้ ต้องสลับองค์ประกอบใด ๆ
นั่นคือที่ดีงาม
>> ดังนั้นสิ่งที่เป็นกรณีที่เลวร้ายที่สุด สถานการณ์ที่มีการจัดเรียงฟอง?
ในกรณีที่เลวร้ายที่สุดคืออาร์เรย์ ในการสั่งซื้อกลับอย่างสมบูรณ์
และเพื่อให้เรามีฟองแต่ละ ขององค์ประกอบที่มีขนาดใหญ่ทั้งหมด
วิธีที่ทั่วอาร์เรย์
และเราได้อย่างมีประสิทธิภาพนอกจากนี้ยังต้อง ฟองทั้งหมดขององค์ประกอบเล็ก ๆ ด้านหลัง
ทุกทางทั่วอาร์เรย์เกินไป
ดังนั้นแต่ละองค์ประกอบ n ที่มีการย้าย ในทุกองค์ประกอบ n อื่น ๆ
เพื่อให้เป็นสถานการณ์กรณีที่เลวร้าย
ในกรณีที่ดีที่สุด สถานการณ์ที่ว่านี้คือ
แตกต่างจากการจัดเรียงตัวเลือก
อาร์เรย์ที่มีอยู่แล้ว เรียงเมื่อเราไปใน
เราไม่ได้มีเพื่อให้การใด ๆ แลกเปลี่ยนในวันแรกผ่านไป
ดังนั้นเราอาจจะต้องมอง องค์ประกอบน้อยลงใช่มั้ย?
เราไม่ได้มีการทำซ้ำนี้ ประมวลผลจำนวนครั้งมากกว่า
>> ดังนั้นสิ่งที่หมายความว่า?
ดังนั้นสิ่งที่สถานการณ์กรณีที่เลวร้ายที่สุด สำหรับการจัดเรียงฟองและสิ่งที่
สถานการณ์กรณีที่ดีที่สุดสำหรับการจัดเรียงฟอง?
คุณคิดว่านี้หรือไม่?
ในกรณีที่เลวร้ายที่สุดที่คุณจะต้องย้ำ ในทุกองค์ประกอบ n n ครั้ง
ดังนั้นกรณีที่เลวร้ายที่สุดคือการยกกำลังสอง n
>> ถ้าอาร์เรย์เป็นอย่างดี เรียงลำดับแม้ว่าคุณเท่านั้น
ต้องมองไปที่แต่ละ ขององค์ประกอบหนึ่งครั้ง
และถ้าเคาน์เตอร์แลกเปลี่ยนยังคงเป็น 0, ที่คุณสามารถพูดอาร์เรย์นี้จะถูกจัดเรียง
และในกรณีที่ดีที่สุดนี้เป็น จริงดีกว่าเลือก
sort-- ก็โอเมก้าของ n
>> ฉันลอยด์ดั๊ก
นี่คือ CS50