>> [เล่นเพลง]
>> DOUG LLOYD: ตกลงดังนั้นผสาน การจัดเรียงเป็นอีกขั้นตอนวิธีการอื่น
ที่เราสามารถใช้การจัดเรียงออก องค์ประกอบของอาร์เรย์
แต่ที่เราจะเห็นก็มี ความแตกต่างพื้นฐานมาก
จากการเรียงลำดับการเลือกฟอง เรียงลำดับและการจัดเรียงแทรก
ที่ทำให้มันสวยจริงๆฉลาด
>> ความคิดพื้นฐานหลังผสาน การเรียงลำดับการจัดเรียงเป็นอาร์เรย์ที่มีขนาดเล็ก
แล้วรวมอาร์เรย์เหล่านั้น ร่วมกันหรือรวม them--
จึง name-- เพื่อเรียงลำดับ
วิธีการที่ผสานการเรียงลำดับไม่ นี้โดยใช้ประโยชน์จากเครื่องมือ
ที่เรียกว่าการเรียกซ้ำซึ่งเป็นสิ่งที่ ที่เรากำลังจะพูดคุยเกี่ยวกับในเร็ว ๆ นี้
แต่เรายังไม่ได้คุยมากเกี่ยวกับยัง
>> นี่คือความคิดพื้นฐานที่อยู่เบื้องหลังการจัดเรียงผสาน
เรียงครึ่งซ้ายของอาร์เรย์ สมมติว่า n มากกว่า 1
และสิ่งที่ผมหมายถึงเมื่อฉันพูด สมมติว่า n มากกว่า 1 คือ
ผมคิดว่าเราสามารถตกลงว่าถ้าอาร์เรย์ เพียงประกอบด้วยองค์ประกอบเดียว
มันเรียง
เราไม่จำเป็นต้องจริง ที่จะทำอะไรกับมัน
เราก็สามารถประกาศให้มีการเรียง
มันเป็นเพียงองค์ประกอบหนึ่ง
>> ดังนั้น pseudocode อีกครั้งเป็น เรียงลำดับครึ่งด้านซ้ายของอาร์เรย์
แล้วเรียงครึ่งขวาอาร์เรย์ แล้วรวมทั้งสองส่วนเข้าด้วยกัน
ตอนนี้แล้วคุณอาจจะ คิดชนิดของมันเพียง
เสียงเหมือนคุณกำลังวางปิด the-- คุณไม่ได้จริงทำอะไร
คุณกำลังจะบอกว่าการจัดเรียงซ้าย ครึ่งเรียงลำดับครึ่งขวา
แต่คุณไม่ได้บอก ฉันว่าคุณกำลังทำมัน
>> แต่จำไว้ว่าตราบใดที่ อาร์เรย์เป็นองค์ประกอบเดียว
เราสามารถประกาศเรียง
จากนั้นเราก็สามารถรวมเข้าด้วยกัน
และที่จริง ความคิดพื้นฐานที่อยู่เบื้องหลังการจัดเรียงผสาน
คือการทำลายมันลงเพื่อให้ อาร์เรย์ของคุณมีขนาดหนึ่ง
และจากนั้นคุณสร้างจากที่นั่น
>> ผสานการเรียงลำดับแน่นอน อัลกอริทึมที่มีความซับซ้อน
และก็ยังเล็ก ๆ น้อย ๆ ที่มีความซับซ้อนที่จะเห็นภาพ
ดังนั้นหวังว่าการสร้างภาพว่าเราคือ มีที่นี่จะช่วยให้คุณทำตาม
และผมจะพยายามทำให้ดีที่สุดที่จะเล่าสิ่งที่ และดำเนินการผ่านเล็ก ๆ น้อย ๆ นี้
ช้ากว่าคนอื่น ๆ เพียงเพื่อหวังว่าจะได้รับหัวของคุณ
ความคิดที่อยู่เบื้องหลังรอบจัดเรียงผสาน
>> ดังนั้นเราจึงมีอาร์เรย์เช่นเดียวกับ วิดีโอขั้นตอนวิธีการเรียงลำดับอื่น ๆ
ถ้าคุณเคยเห็น them-- อาร์เรย์องค์ประกอบหก
และรหัส pseudocode ของเราที่นี่คือการจัดเรียง ครึ่งซ้ายจัดเรียงครึ่งขวา
รวมทั้งสองส่วนเข้าด้วยกัน
ดังนั้นลองมาสีแดงอิฐสีเข้มมากนี้ อาร์เรย์และเรียงลำดับครึ่งซ้ายของมัน
>> ดังนั้นในขณะนี้เรากำลังจะ ที่จะไม่สนใจสิ่งที่อยู่บนด้านขวา
ก็มี แต่เรา ไม่ได้อยู่ที่ขั้นตอนที่ยัง
เราไม่ได้อยู่ที่การจัดเรียง ครึ่งขวาของอาร์เรย์
เราที่จัดเรียงซ้าย ครึ่งหนึ่งของอาร์เรย์
และเพียงเพื่อประโยชน์ ของการเป็นเล็ก ๆ น้อย ๆ
ที่ชัดเจนเพื่อให้สามารถดู กับสิ่งที่ขั้นตอนที่เราอยู่
ฉันจะเปลี่ยน สีของชุดนี้เป็นสีส้ม
ตอนนี้เราก็ยังคงพูดคุยเกี่ยวกับ ครึ่งซ้ายเดียวกันของอาร์เรย์เดิม
แต่ฉันหวังว่าด้วยความสามารถในการ หมายถึงสีของรายการต่างๆ
มันจะทำให้มันเล็ก ๆ น้อย ๆ ที่ชัดเจนสิ่งที่เกิดขึ้นที่นี่
>> ตกลงดังนั้นตอนนี้เรามี สามองค์ประกอบอาร์เรย์
ทำอย่างไรเราจะเรียงลำดับในช่วงครึ่งปีที่เหลือนี้ อาร์เรย์ซึ่งยังคงเป็นขั้นตอนนี้?
เรากำลังพยายามที่จะเรียงลำดับซ้าย ครึ่งหนึ่งของสีแดงอิฐ array--
ครึ่งซึ่งทางด้านซ้ายของ ฉันได้สีส้มในขณะนี้
>> ดีเราอาจจะลองและ ทำซ้ำขั้นตอนนี้อีกครั้ง
ดังนั้นเรายังคงอยู่ใน ตรงกลางของความพยายามในการจัดเรียง
ครึ่งซ้ายของมากมายเต็ม
ครึ่งซ้ายของ อาร์เรย์ฉันแค่ไป
ไปโดยพลการตัดสินใจว่าครึ่งซ้าย จะมีขนาดเล็กกว่าครึ่งหนึ่งที่เหมาะสม
เพราะนี้เกิดขึ้นกับ ประกอบด้วยสามองค์ประกอบ
>> และเพื่อที่ฉันจะบอกว่า ครึ่งซ้ายของครึ่งซ้ายอาร์เรย์
เป็นเพียงองค์ประกอบห้า
ห้าเป็นองค์ประกอบหนึ่ง อาร์เรย์เรารู้วิธีการจัดเรียง
และเพื่อให้ห้าเรียง
เรากำลังจะประกาศว่า
มันเป็นองค์ประกอบหนึ่งอาร์เรย์
>> ดังนั้นเราจึงได้เรียงตอนนี้ ครึ่งซ้ายของ half-- ซ้าย
หรือมากกว่าที่เราเคยเรียง ครึ่งซ้ายของสีส้ม
ดังนั้นตอนนี้เพื่อที่จะยังคงสมบูรณ์ ครึ่งซ้ายอาร์เรย์โดยรวมของ
เราจำเป็นต้องเรียงลำดับครึ่งหนึ่งที่เหมาะสม สีส้มหรือสิ่งนี้
เราจะทำอย่างนั้นได้อย่างไร?
ดีที่เรามีอาร์เรย์องค์ประกอบที่สอง
ดังนั้นเราจึงสามารถจัดเรียงครึ่งซ้าย ของอาเรย์ซึ่งเป็นสอง
สองเป็นองค์ประกอบเดียว
ดังนั้นจึงเรียงตามค่าเริ่มต้น จากนั้นเราก็สามารถจัดเรียงครึ่งหนึ่งที่เหมาะสม
จากส่วนของอาร์เรย์ที่หนึ่ง
นั่นคือการจัดเรียงของโดยค่าเริ่มต้น
>> นี่คือตอนนี้เป็นครั้งแรก เราได้มาถึงขั้นตอนการผสาน
เราได้เสร็จสิ้นแม้ว่า เรากำลังซ้อนกันในขณะนี้ชนิดของ down--
และนั่นคือการจัดเรียงของหากิน สิ่งที่มีการเรียกซ้ำคือ
คุณจะต้องให้คุณ หัวเกี่ยวกับการที่เรามี
ดังนั้นเราจึงได้จัดเรียงของด้านซ้าย ครึ่งหนึ่งของส่วนสีส้ม
>> และตอนนี้เรากำลังอยู่ในช่วงกลางของการเรียงลำดับ ครึ่งขวาของส่วนสีส้ม
และในกระบวนการที่เรามี ขณะนี้เกี่ยวกับที่จะอยู่ในขั้นตอน
รวมทั้งสองส่วนเข้าด้วยกัน
เมื่อเรามองที่ทั้งสองส่วน ของอาร์เรย์ที่เราเห็นสองและเป็นหนึ่งใน
ซึ่งองค์ประกอบที่มีขนาดเล็ก?
หนึ่ง
>> จากนั้นองค์ประกอบที่มีขนาดเล็ก?
ดีก็สองหรืออะไร
ดังนั้นจึงเป็นที่สอง
ดังนั้นตอนนี้เพียงเพื่อให้กรอบอีกครั้ง ที่เรามีในบริบท
เราได้เรียง ครึ่งซ้ายของสีส้ม
และอีกครึ่งหนึ่งที่เหมาะสมของแหล่งกำเนิด
ฉันรู้ว่าฉันได้เปลี่ยนสี อีกครั้ง แต่นั่นคือสิ่งที่เราเป็น
และเหตุผลที่ฉันทำอย่างนี้ เป็นเพราะกระบวนการนี​​้คือ
จะให้ไปทำซ้ำลง
เราได้เรียงซ้าย ครึ่งหนึ่งของส้มอดีต
และอีกครึ่งหนึ่งขวาของส้มอดีต
>> ตอนนี้เราต้องการที่จะรวมเหล่านั้น สองส่วนด้วยกันเกินไป
นั่นเป็นขั้นตอนที่เราอยู่บน
ดังนั้นเราจึงพิจารณาทั้งหมดของ องค์ประกอบที่มีตอนนี้สีเขียว
ครึ่งซ้ายของแถวเดิม
และเรารวมเหล่านั้น โดยใช้กระบวนการเดียวกัน
เราไม่ได้สำหรับการรวมสอง และเป็นหนึ่งในเพียงครู่ที่ผ่านมา
>> ครึ่งซ้ายที่เล็กที่สุด องค์ประกอบครึ่งซ้ายเป็นห้า
องค์ประกอบที่เล็กที่สุดใน ครึ่งขวาเป็นหนึ่ง
ซึ่งในนั้นคือเล็ก?
หนึ่ง
>> องค์ประกอบที่เล็กที่สุดใน ครึ่งซ้ายเป็นห้า
องค์ประกอบที่เล็กที่สุดใน ครึ่งขวาสอง
ที่เล็กที่สุดคืออะไร?
สอง
และแล้วในที่สุดห้า ไม่มีอะไรที่เราสามารถพูดได้ห้า
>> ตกลงภาพใหญ่เพื่อขอ ใช้เวลาพักเป็นครั้งที่สอง
และคิดออกว่าเราอยู่ที่ไหน
ถ้าเราเริ่มต้นจาก จุดเริ่มต้นมากเรา
ได้เสร็จสิ้นในขณะนี้สำหรับ อาร์เรย์โดยรวมเพียง
หนึ่งในขั้นตอนของรหัส pseudocode ที่นี่
เราได้เรียง ครึ่งซ้ายของอาร์เรย์
>> จำได้ว่าเดิม เพื่อเป็นห้าสองหนึ่ง
โดยจะผ่านขั้นตอนนี้ และทำรังลงและทำซ้ำ
อย่างต่อเนื่องที่จะทำลายปัญหา ลงไปในชิ้นส่วนที่มีขนาดเล็กและขนาดเล็ก
เราได้เสร็จสิ้นในขณะนี้ ขั้นตอนที่หนึ่ง pseudocode
สำหรับอาร์เรย์เริ่มต้นทั้งหมด
เราได้เรียงครึ่งซ้าย
>> ดังนั้นตอนนี้เรามีการแช่แข็ง
และตอนนี้เรามาเรียงลำดับที่ถูกต้อง ครึ่งหนึ่งของอาร์เรย์เดิม
และเรากำลังจะทำด้วย จะผ่านเดียวกันซ้ำแล้วซ้ำอีก
กระบวนการของการทำลายสิ่งที่ลง และจากนั้นการรวมเข้าด้วยกัน
>> ดังนั้นในช่วงครึ่งซ้ายของ สีแดงหรือครึ่งซ้าย
ในช่วงครึ่งขวาของเดิม อาร์เรย์ฉันจะบอกก็คือสาม
อีกครั้งฉันมีความสอดคล้องกันที่นี่
หากคุณมีความแปลก จำนวนขององค์ประกอบมัน
ไม่ได้เรื่องจริงๆไม่ว่าจะเป็น คุณทำให้คนที่เหลือที่มีขนาดเล็ก
หรือขวาหนึ่งที่มีขนาดเล็ก
>> สิ่งที่สำคัญคือว่าเมื่อใดก็ตามที่คุณ พบปัญหานี้ในการดำเนินการ
ผสานคุณจะต้องมีความสอดคล้อง
คุณอาจจำเป็นต้อง ทำให้ด้านซ้ายที่มีขนาดเล็ก
หรือมักจะต้องทำให้ ด้านขวาที่มีขนาดเล็ก
ที่นี่ผมได้เลือกที่จะเสมอ ทำให้ด้านซ้ายที่มีขนาดเล็ก
เมื่ออาเรย์ของฉันหรือของฉัน อาร์เรย์ย่อยคือมีขนาดที่แปลก
>> สามเป็นองค์ประกอบเดียว และดังนั้นจึงจะถูกจัดเรียง
เราได้ยกระดับสมมติฐานที่ว่า ตลอดกระบวนการทั้งหมดของเราเพื่อให้ห่างไกล
ดังนั้นตอนนี้เรามาเรียงลำดับที่ถูกต้อง ครึ่งหนึ่งของครึ่งขวา
หรือครึ่งขวาของสีแดง
>> อีกครั้งที่เราต้องแบ่งนี้ลง
นี้ไม่ได้เป็นอาร์เรย์องค์ประกอบหนึ่ง
เราไม่สามารถประกาศเรียง
และเป็นครั้งแรกดังนั้นเราจะ การจัดเรียงครึ่งซ้าย
>> ครึ่งซ้ายเป็นองค์ประกอบเดียว ดังนั้นจึงเป็นเรื่องของการจัดเรียงโดยค่าเริ่มต้น
จากนั้นเราจะเรียงลำดับที่ถูกต้อง ครึ่งซึ่งเป็นองค์ประกอบหนึ่ง
มันเรียงตามค่าเริ่มต้น และตอนนี้, เราสามารถผสานทั้งสองเข้าด้วยกัน
สี่มีขนาดเล็กและ จากนั้นหกมีขนาดเล็ก
>> อีกครั้งสิ่งที่เราทำในตอนนี้?
เราได้เรียงซ้าย ครึ่งหนึ่งของครึ่งที่เหมาะสม
หรือจะกลับไปที่เดิม สีที่อยู่ที่นั่น
เราได้เรียงซ้าย ครึ่งหนึ่งของสีแดงนุ่ม
แต่เดิมมันเป็นอิฐที่มืด สีแดงและตอนนี้ก็เป็นสีแดงอ่อน
หรือมันเป็นสีแดงนุ่ม
>> และจากนั้นเราได้เรียง ครึ่งขวาของสีแดงนุ่ม
ตอนนี้ดีที่พวกเขากำลังสีเขียวอีกครั้งเพียง เพราะเรากำลังจะผ่านกระบวนการ
และเราจะต้องทำซ้ำ นี้ซ้ำแล้วซ้ำอีก
>> ดังนั้นตอนนี้เราสามารถผสานเหล่านั้น ทั้งสองส่วนเข้าด้วยกัน
และนั่นคือสิ่งที่เราทำที่นี่
ดังนั้นเส้นสีดำเพียง แบ่งครึ่งซ้าย
และอีกครึ่งหนึ่งทางด้านขวาของส่วนการจัดเรียงนี้
>> เราเปรียบเทียบค่าที่น้อยที่สุด ที่ด้านซ้ายของ array--
หรือขอโทษนะที่มีขนาดเล็กที่สุด ค่าของครึ่งซ้าย
ค่าที่เล็กที่สุดของที่เหมาะสม ช่วงครึ่งปีและพบว่าทั้งสามมีขนาดเล็ก
และตอนนี้บิตของการเพิ่มประสิทธิภาพใช่มั้ย?
ไม่มีอะไรที่เป็นจริง ที่เหลืออยู่บนด้านซ้าย
>> ไม่มีอะไรที่เหลืออยู่คือ ที่ด้านข้างซ้าย
เพื่อให้เราสามารถได้อย่างมีประสิทธิภาพ เพียง move-- เราสามารถประกาศ
ส่วนที่เหลือของมันเป็นจริง เรียงตะปูและเพียงแค่มัน
บนเพราะไม่มีอะไร อื่นที่จะเปรียบเทียบกับ
และเรารู้ว่าด้านขวา ของทางด้านขวาจะถูกจัดเรียง
>> ตกลงดังนั้นตอนนี้ขอหยุดอีกครั้งและ คิดออกว่าเราอยู่ในเรื่อง
ในอาร์เรย์โดยรวม สิ่งที่เราประสบความสำเร็จ?
เราได้ประสบความสำเร็จจริง ขณะนี้ขั้นตอนที่หนึ่งและสองขั้นตอน
เราเรียงครึ่งซ้ายและ เราเรียงครึ่งหนึ่งที่เหมาะสม
>> ดังนั้นตอนนี้ทุกคนที่ยังคงเป็นสำหรับเรา ที่จะรวมทั้งสองส่วนเข้าด้วยกัน
ดังนั้นเราจึงเปรียบเทียบมูลค่าต่ำสุด องค์ประกอบของแต่ละครึ่งของอาร์เรย์
ในการเปิดและดำเนินการต่อ
หนึ่งคือน้อยกว่าสามดังนั้นหนึ่งไป
>> สองคือน้อยกว่าสามเพื่อให้ทั้งสองไป
สามคือน้อยกว่า 5 ดังนั้นสามไป
สี่คือน้อยกว่า 5 ดังนั้นสี่ไป
จากนั้นห้าน้อยกว่าหก และหกเป็นสิ่งที่ยังคงอยู่
>> ตอนนี้ฉันรู้ว่าเป็นจำนวนมากของขั้นตอน
และเราได้ทิ้งเป็นจำนวนมาก ของหน่วยความจำในการปลุกของเรา
และนั่นคือสิ่งสี่เหลี่ยมสีเทาผู้ที่มี
และมันอาจจะรู้สึกเหมือนที่เอา มากเกินกว่าการจัดเรียงแทรกฟอง
เรียงลำดับหรือการเรียงลำดับการเลือก
>> แต่จริงๆแล้วเพราะ จำนวนมากของกระบวนการเหล่านี้
จะเกิดขึ้นที่ time-- เดียวกัน ซึ่งเป็นสิ่งที่เราจะอีกครั้ง
พูดคุยเกี่ยวกับเมื่อเราพูดคุยเกี่ยวกับ เรียกซ้ำในอนาคต video--
ขั้นตอนวิธีนี้จริง เห็นได้ชัดว่าเป็นพื้นฐาน
ที่แตกต่างกันกว่าสิ่งใด เราได้เห็นมาก่อน
แต่ก็ยังเป็นอย่างมีนัยสำคัญ มีประสิทธิภาพมากขึ้น
>> ว่าเป็นเพราะเหตุใด
ทั้งในที่เลวร้ายที่สุด กรณีที่เรามี
การแยกองค์ประกอบ n ขึ้น และจากนั้นพวกเขา recombine
แต่เมื่อเรา recombine พวกเขาสิ่งที่เรากำลังทำ
เป็นพื้นสองเท่า ขนาดของอาร์เรย์ที่มีขนาดเล็ก
เรามีพวงของหนึ่งในองค์ประกอบ อาร์เรย์ที่เราได้อย่างมีประสิทธิภาพ
รวมเป็นสองอาร์เรย์องค์ประกอบ
และจากนั้นเราใช้เวลาเหล่านั้น สองอาร์เรย์องค์ประกอบ
และรวมเข้าด้วยกันเป็น สี่อาร์เรย์องค์ประกอบและอื่น ๆ
และอื่น ๆ และอื่น ๆ จนเรา มีอาร์เรย์องค์ประกอบ n เดียว
>> แต่กี่ doublings มันจะใช้เวลาที่จะได้รับ n?
คิดว่ากลับไปเช่นสมุดโทรศัพท์
กี่ครั้งแล้วที่เราจะต้องฉีก สมุดโทรศัพท์ในช่วงครึ่งปีวิธีการอื่น ๆ อีกมากมาย
ครั้งเราจะต้องฉีกสมุดโทรศัพท์ ในช่วงครึ่งปีถ้าขนาดของสมุดโทรศัพท์
สองเท่า?
มีเพียงหนึ่งเป็นใช่มั้ย?
>> ดังนั้นจึงมีการจัดเรียงของบางอย่าง องค์ประกอบลอการิทึมที่นี่
แต่เราก็ยังคงมีอย่างน้อย ดูทุกองค์ประกอบที่ n
ดังนั้นในสถานการณ์กรณีที่เลวร้ายที่สุด ผสานการจัดเรียงทำงานใน n ล็อก n
เราต้องมองไปที่ ทุกองค์ประกอบ n ที่
และเราจะต้องรวมพวกเขา ร่วมกันในชุด n เข้าสู่ระบบของขั้นตอน
ในกรณีที่ดีที่สุด อาร์เรย์จะถูกจัดเรียงอย่างสมบูรณ์แบบ
นั่นวิเศษมาก
แต่ขึ้นอยู่กับขั้นตอนวิธีการที่เรามีที่นี่ เรายังคงต้องแยกและ recombine
ถึงแม้ว่าในกรณีนี้ recombining เป็นชนิดของการไม่ได้ผล
มันไม่จำเป็นต้อง
แต่เรายังคงผ่านไป กระบวนการทั้งหมดอยู่แล้ว
>> ดังนั้นในกรณีที่ดีที่สุด และในกรณีที่เลวร้ายที่สุด
ขั้นตอนวิธีการนี​​้จะทำงานในบันทึก n n เวลา
ผสานการเรียงลำดับแน่นอนบิต trickier กว่าขั้นตอนวิธีการเรียงลำดับหลักอื่น ๆ
เราได้พูดคุยเกี่ยวกับ CS50 แต่ อย่างมีนัยสำคัญมีประสิทธิภาพมากขึ้น
>> ดังนั้นถ้าคุณเคยพบ โอกาสที่จะจำเป็นต้องใช้มัน
หรือเพื่อใช้ในการเรียงลำดับ ชุดข้อมูลขนาดใหญ่ที่ได้รับ
หัวของรอบความคิดของการเรียกซ้ำตัวเอง เป็นไปได้ที่มีประสิทธิภาพจริงๆ
และมันจะทำให้คุณ โปรแกรมมากจริงๆมีประสิทธิภาพมากขึ้น
โดยใช้การผสานการเรียงลำดับเมื่อเทียบกับสิ่งอื่น
ฉันลอยด์ดั๊ก
นี่คือ CS50