[เล่นเพลง] 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