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