[เล่นเพลง] 

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

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

เรากำลังจะไปองค์ประกอบหนึ่งในเวลาและ สร้างมันและดังนั้นสิ่งแรกที่เราเห็น เป็นองค์ประกอบหนึ่งอาร์เรย์ และโดยความหมายหนึ่ง องค์ประกอบอาร์เรย์จะถูกจัดเรียง 

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

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

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

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

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

อีกครั้งยังคงเราได้เท่านั้นที่เคย มองไปที่หนึ่งสองและห้า เราไม่ทราบว่าสิ่งที่คนอื่นจะมา แต่เราได้เรียงทั้งสามองค์ประกอบ 

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

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

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

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

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

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

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

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

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