การบรรยายจากหลักสูตร Harvard เกี่ยวกับพื้นฐานการเขียนโปรแกรม CS50 การมอบหมายงาน CS50 สัปดาห์ที่ 3 ส่วนที่ 1 การมอบหมายงาน CS50 สัปดาห์ที่ 3 ส่วนที่ 2
แต่เมื่อถึงจุดหนึ่ง ฟังก์ชันกำลังสองจะแซงฟังก์ชันเชิงเส้น ไม่มีทางเลี่ยงมันได้ ความซับซ้อนเชิงซีมโทติกอีกประการหนึ่งคือเวลาลอการิทึมหรือ O(log n) เมื่อ n เพิ่มขึ้น ฟังก์ชันนี้จะเพิ่มขึ้นอย่างช้าๆ O(log n) คือเวลาทำงานของอัลกอริธึมการค้นหาไบนารีแบบคลาสสิกในอาเรย์ที่เรียงลำดับ (จำสมุดโทรศัพท์ที่ขาดในการบรรยายได้ไหม) อาร์เรย์ถูกแบ่งออกเป็นสองส่วน จากนั้นเลือกครึ่งหนึ่งซึ่งองค์ประกอบนั้นถูกเลือก ดังนั้น ทุกครั้งที่ลดพื้นที่การค้นหาลงครึ่งหนึ่ง เราจะค้นหาองค์ประกอบนั้น
จะเกิดอะไรขึ้นถ้าเราสะดุดกับสิ่งที่เรากำลังมองหาโดยแบ่งอาร์เรย์ข้อมูลของเราออกเป็นสองส่วนเป็นครั้งแรก? มีคำศัพท์สำหรับเวลาที่ดีที่สุด - Omega-large หรือ Ω(n) ในกรณีของการค้นหาแบบไบนารี = Ω(1) (ค้นหาในเวลาคงที่ โดยไม่คำนึงถึงขนาดของอาร์เรย์) การค้นหาเชิงเส้นจะทำงานในเวลา O(n) และ Ω(1) หากองค์ประกอบที่กำลังค้นหาเป็นองค์ประกอบแรก อีกสัญลักษณ์หนึ่งคือทีต้า (Θ(n)) ใช้เมื่อตัวเลือกที่ดีที่สุดและแย่ที่สุดเหมือนกัน เหมาะสำหรับตัวอย่างที่เราจัดเก็บความยาวของสตริงไว้ในตัวแปรที่แยกจากกัน ดังนั้นสำหรับความยาวใดๆ ก็เพียงพอแล้วที่จะอ้างอิงถึงตัวแปรนี้ สำหรับอัลกอริทึมนี้ กรณีที่ดีที่สุดและแย่ที่สุดคือ Ω(1) และ O(1) ตามลำดับ ซึ่งหมายความว่าอัลกอริทึมจะทำงานทันเวลา Θ(1)
ฟังก์ชั่น linearSearch รับอาร์กิวเมนต์สองตัวเป็นอินพุต - คีย์คีย์และอาร์เรย์อาร์เรย์ [] คีย์คือค่าที่ต้องการในคีย์ตัวอย่างก่อนหน้า = 0 อาร์เรย์คือรายการตัวเลขที่เรา จะมองผ่าน หากเราไม่พบสิ่งใดเลย ฟังก์ชันจะส่งกลับ -1 (ตำแหน่งที่ไม่มีอยู่ในอาร์เรย์) หากการค้นหาเชิงเส้นพบองค์ประกอบที่ต้องการ ฟังก์ชันจะส่งคืนตำแหน่งที่องค์ประกอบที่ต้องการอยู่ในอาร์เรย์ ข้อดีของการค้นหาเชิงเส้นคือ มันจะใช้ได้กับอาร์เรย์ใดๆ ก็ตาม โดยไม่คำนึงถึงลำดับขององค์ประกอบ: เราจะยังคงค้นหาทั้งอาร์เรย์ นี่คือจุดอ่อนของเขาด้วย หากคุณต้องการค้นหาตัวเลข 198 ในอาร์เรย์ที่มี 200 หมายเลขโดยเรียงลำดับตามลำดับ การวนซ้ำ for จะดำเนินการ 198 ขั้นตอน
คุณคงเดาได้แล้วว่าวิธีใดทำงานได้ดีกว่าสำหรับอาร์เรย์ที่เรียงลำดับ
ถ้าเป็นเส้นตรงก็จะใช้เวลานาน และถ้าเราใช้ "วิธีแบ่งไดเรกทอรีออกครึ่งหนึ่ง" เราจะตรงไปที่จัสมิน และเราสามารถทิ้งครึ่งแรกของรายการได้อย่างปลอดภัย โดยตระหนักว่ามิกกี้ไม่สามารถอยู่ที่นั่นได้
โดยใช้หลักการเดียวกัน เราละทิ้งคอลัมน์ที่สองไป ดำเนินกลยุทธ์นี้ต่อไป เราจะพบมิกกี้ในอีกไม่กี่ขั้นตอน
มาหาเลข 144 กัน. เราแบ่งครึ่งรายการแล้วได้เลข 13. เราประเมินว่าเลขที่ต้องการมากกว่าหรือน้อยกว่า 13. 13
< 144. เราก็จะไม่ต้องสนใจทุกอย่างทางด้านซ้ายของ 13 และหมายเลขนี้เอง ตอนนี้รายการค้นหาของเรามีลักษณะดังนี้:
มีองค์ประกอบจำนวนเท่ากัน ดังนั้นเราจึงเลือกหลักการที่เราเลือก "ตรงกลาง" (ใกล้กับจุดเริ่มต้นหรือจุดสิ้นสุดมากขึ้น) สมมติว่าเราเลือกกลยุทธ์แห่งความใกล้ชิดกับจุดเริ่มต้น ในกรณีนี้ "ตรงกลาง" ของเรา = 55.
55 < 144 เราละทิ้งครึ่งซ้ายของรายการอีกครั้ง โชคดีสำหรับเรา จำนวนเฉลี่ยถัดไปคือ 144
เราพบ 144 ในอาร์เรย์ 13 องค์ประกอบโดยใช้การค้นหาแบบไบนารีในเวลาเพียงสามขั้นตอน การค้นหาเชิงเส้นจะจัดการกับสถานการณ์เดียวกันได้มากถึง 12 ขั้นตอน เนื่องจากอัลกอริธึมนี้จะลดจำนวนองค์ประกอบในอาร์เรย์ลงครึ่งหนึ่งในแต่ละขั้นตอน จึงจะค้นหาองค์ประกอบที่ต้องการในเวลาเชิงเส้นกำกับ O(log n) โดยที่ n คือจำนวนองค์ประกอบในรายการ นั่นคือในกรณีของเรา เวลาเชิงเส้นกำกับ = O(บันทึก 13) (นี่คือมากกว่าสามเล็กน้อย) รหัสเทียมของฟังก์ชันการค้นหาแบบไบนารี:
ฟังก์ชันรับ 4 อาร์กิวเมนต์เป็นอินพุต: คีย์ที่ต้องการ, อาร์เรย์ข้อมูล [] ซึ่งอยู่ในตำแหน่งที่ต้องการ, ค่าต่ำสุดและสูงสุดเป็นตัวชี้ไปยังจำนวนสูงสุดและต่ำสุดในอาร์เรย์ซึ่ง เรากำลังดูขั้นตอนของอัลกอริทึมนี้ สำหรับตัวอย่างของเรา ในตอนแรกได้รับรูปภาพต่อไปนี้:
มาวิเคราะห์โค้ดเพิ่มเติมกัน จุดกึ่งกลางคือจุดกึ่งกลางของอาร์เรย์ของเรา ขึ้นอยู่กับจุดสุดขั้วและอยู่ตรงกลางระหว่างจุดเหล่านั้น หลังจากที่เราเจอตรงกลางแล้วให้ตรวจสอบว่าน้อยกว่าเลขคีย์ของเราหรือไม่
หากเป็นเช่นนั้น คีย์ก็จะมากกว่าตัวเลขใดๆ ทางด้านซ้ายของตรงกลาง และเราสามารถเรียกใช้ฟังก์ชันไบนารี่ได้อีกครั้ง เฉพาะตอนนี้ของเราเท่านั้น min = จุดกึ่งกลาง + 1 หากปรากฏว่าคีย์นั้น < จุดกึ่งกลาง เราก็สามารถละทิ้งได้ เลขนั้นเองและเลขทั้งหมดนอนอยู่ทางขวามือ และเราเรียกการค้นหาแบบไบนารี่ผ่านอาร์เรย์ตั้งแต่ตัวเลข min ไปจนถึงค่า (จุดกึ่งกลาง – 1)
สุดท้าย สาขาที่สาม: หากค่าในช่วงกลางไม่มากหรือน้อยกว่าคีย์ ก็ไม่มีทางเลือกอื่นนอกจากต้องเป็นตัวเลขที่ต้องการ ในกรณีนี้เราจะส่งคืนและจบโปรแกรม
สุดท้ายอาจเกิดขึ้นได้ว่าหมายเลขที่คุณกำลังมองหาไม่อยู่ในอาร์เรย์เลย เพื่อพิจารณากรณีนี้ เราจะดำเนินการตรวจสอบต่อไปนี้:
และเรากลับ (-1) เพื่อระบุว่าเราไม่พบสิ่งใดเลย คุณรู้อยู่แล้วว่าการค้นหาแบบไบนารี่จำเป็นต้องเรียงลำดับอาร์เรย์ ดังนั้น หากเรามีอาร์เรย์ที่ไม่เรียงลำดับซึ่งเราจำเป็นต้องค้นหาองค์ประกอบเฉพาะ เราก็มีสองทางเลือก:
ข้อควรสนใจ: รากของแผนผัง "โปรแกรมเมอร์" ซึ่งแตกต่างจากของจริงอยู่ที่ด้านบน แต่ละเซลล์เรียกว่าจุดยอด และจุดยอดเชื่อมต่อกันด้วยขอบ รากของต้นไม้คือเซลล์หมายเลข 13 ทรีย่อยด้านซ้ายของจุดยอด 3 จะถูกเน้นด้วยสีในภาพด้านล่าง:
ต้นไม้ของเราตรงตามข้อกำหนดทั้งหมดสำหรับต้นไม้ไบนารี ซึ่งหมายความว่าทรีย่อยด้านซ้ายแต่ละอันมีเพียงค่าที่น้อยกว่าหรือเท่ากับค่าของจุดยอด ในขณะที่ทรีย่อยด้านขวามีเพียงค่าที่มากกว่าหรือเท่ากับค่าของจุดยอดเท่านั้น ทรีย่อยทั้งซ้ายและขวาต่างก็เป็นทรีย่อยแบบไบนารี วิธีการสร้างต้นไม้ไบนารีไม่ได้เป็นเพียงวิธีเดียว: ด้านล่างในภาพที่คุณเห็นตัวเลือกอื่นสำหรับชุดตัวเลขเดียวกันและอาจมีได้มากมายในทางปฏิบัติ
โครงสร้างนี้ช่วยในการค้นหา: เราค้นหาค่าต่ำสุดโดยเลื่อนจากบนไปทางซ้ายและลงล่างในแต่ละครั้ง
หากคุณต้องการค้นหาจำนวนสูงสุด เราไปจากบนลงล่างไปทางขวา การค้นหาตัวเลขที่ไม่ใช่ค่าต่ำสุดหรือสูงสุดก็ค่อนข้างง่ายเช่นกัน เราลงมาจากรากไปทางซ้ายหรือทางขวา ขึ้นอยู่กับว่าจุดยอดของเราใหญ่กว่าหรือเล็กกว่าจุดที่เรากำลังมองหา ดังนั้นหากเราต้องการค้นหาหมายเลข 89 เราก็ใช้เส้นทางนี้:
คุณยังสามารถแสดงตัวเลขตามลำดับการจัดเรียงได้ ตัวอย่างเช่น หากเราต้องการแสดงตัวเลขทั้งหมดโดยเรียงลำดับจากน้อยไปหามาก เราจะใช้แผนผังย่อยทางซ้ายและเริ่มจากจุดยอดซ้ายสุดขึ้นไป การเพิ่มบางอย่างให้กับต้นไม้ก็เป็นเรื่องง่ายเช่นกัน สิ่งสำคัญที่ต้องจำคือโครงสร้าง สมมติว่าเราต้องเพิ่มค่า 7 ให้กับทรี ไปที่รูทและตรวจสอบกัน เลข 7 < 13 เลยไปทางซ้าย. เราเห็น 5 ตรงนั้น และไปทางขวา เนื่องจาก 7 > 5 นอกจากนี้ เนื่องจาก 7 > 8 และ 8 ไม่มีลูกหลาน เราจึงสร้างสาขาจาก 8 ไปทางซ้ายและแนบ 7 เข้าไป คุณยังสามารถลบจุดยอดออก
จาก ต้นไม้ แต่นี่ค่อนข้างซับซ้อนกว่า มีสถานการณ์การลบที่แตกต่างกันสามแบบที่เราต้องพิจารณา
ตัวเลขทั้งหมดจะถูกเพิ่มเข้าไปในสาขาที่ถูกต้องของหมายเลขก่อนหน้า หากเราต้องการค้นหาตัวเลข เราจะไม่มีทางเลือกอื่นนอกจากต้องเดินตามโซ่ลงมา
มันไม่ได้ดีไปกว่าการค้นหาเชิงเส้น มีโครงสร้างข้อมูลอื่นที่ซับซ้อนกว่า แต่เราจะไม่พิจารณาพวกเขาในตอนนี้ สมมติว่าเพื่อแก้ปัญหาในการสร้างแผนภูมิจากรายการที่เรียงลำดับ คุณสามารถผสมข้อมูลที่ป้อนเข้าแบบสุ่มได้
แนวคิดหลักคือการแบ่งรายการของเราออกเป็นสองส่วน เรียงลำดับและไม่เรียงลำดับ ในแต่ละขั้นตอนของอัลกอริทึม หมายเลขใหม่จะถูกย้ายจากส่วนที่ไม่ได้เรียงลำดับไปยังส่วนที่เรียงลำดับ และต่อไปเรื่อยๆ จนกว่าตัวเลขทั้งหมดจะอยู่ในส่วนที่เรียงลำดับ
เราค้นหาจำนวนขั้นต่ำในส่วนที่ไม่ได้เรียงลำดับของอาร์เรย์ (นั่นคือในขั้นตอนนี้ - ในอาร์เรย์ทั้งหมด) หมายเลขนี้คือ 2 ตอนนี้เราเปลี่ยนมันด้วยตัวแรกจากจำนวนที่ไม่ได้เรียงลำดับและวางไว้ที่ส่วนท้ายของอาร์เรย์ที่เรียงลำดับ (ในขั้นตอนนี้ - อันดับแรก) ในขั้นตอนนี้ นี่คือตัวเลขแรกในอาร์เรย์ ซึ่งก็คือ 3
ขั้นตอนที่สอง เราไม่ได้ดูหมายเลข 2 มันอยู่ในอาร์เรย์ย่อยที่เรียงลำดับแล้ว เราเริ่มมองหาค่าต่ำสุด โดยเริ่มจากองค์ประกอบที่สอง ซึ่งก็คือ 5 เราตรวจสอบให้แน่ใจว่า 3 เป็นค่าต่ำสุดในกลุ่มที่ไม่เรียงลำดับ และ 5 เป็นค่าแรกในกลุ่มที่ไม่ได้เรียงลำดับ เราสลับและเพิ่ม 3 ลงในอาร์เรย์ย่อยที่เรียงลำดับ
ในขั้นตอนที่สามเราจะเห็นว่าจำนวนที่น้อยที่สุดในอาร์เรย์ย่อยที่ไม่ได้เรียงลำดับคือ 4 เราเปลี่ยนมันด้วยตัวเลขแรกในบรรดาจำนวนที่ไม่เรียงลำดับ - 5
ในขั้นตอนที่สี่เราพบว่าในอาร์เรย์ที่ไม่เรียงลำดับ จำนวนที่น้อยที่สุดคือ 5 เราเปลี่ยนจาก 6 และเพิ่มลงในอาร์เรย์ย่อยที่เรียงลำดับแล้ว
เมื่อเหลือเพียงตัวเลขเดียวในกลุ่มที่ไม่ได้เรียงลำดับ (ตัวเลขที่ใหญ่ที่สุด) นั่นหมายความว่าอาร์เรย์ทั้งหมดจะถูกจัดเรียง!
นี่คือลักษณะการใช้งานอาร์เรย์ในโค้ด ลองทำด้วยตัวเอง.
ทั้งในกรณีที่ดีที่สุดและแย่ที่สุด ในการค้นหาองค์ประกอบที่ไม่เรียงลำดับขั้นต่ำ เราต้องเปรียบเทียบแต่ละองค์ประกอบกับแต่ละองค์ประกอบของอาร์เรย์ที่ไม่เรียงลำดับ และเราจะทำเช่นนี้ในการวนซ้ำแต่ละครั้ง แต่เราไม่จำเป็นต้องดูรายการทั้งหมด แต่ดูเฉพาะส่วนที่ไม่ได้เรียงลำดับเท่านั้น สิ่งนี้เปลี่ยนความเร็วของอัลกอริทึมหรือไม่ ในขั้นตอนแรก สำหรับอาร์เรย์ที่มี 5 องค์ประกอบ เราทำการเปรียบเทียบ 4 รายการ ในวินาที - 3 ในองค์ประกอบที่สาม - 2 เพื่อให้ได้จำนวนการเปรียบเทียบ เราต้องบวกตัวเลขเหล่านี้ทั้งหมด เราได้ผลรวม
ดังนั้น ความเร็วที่คาดหวังของอัลกอริทึมในกรณีที่ดีที่สุดและแย่ที่สุดคือ Θ(n 2 ) ไม่ใช่อัลกอริธึมที่มีประสิทธิภาพที่สุด! อย่างไรก็ตาม เพื่อวัตถุประสงค์ทางการศึกษาและชุดข้อมูลขนาดเล็ก วิธีนี้ค่อนข้างจะนำไปใช้ได้
ขั้นตอนที่ 1:ผ่านอาร์เรย์ อัลกอริทึมเริ่มต้นด้วยสององค์ประกอบแรก 8 และ 6 และตรวจสอบว่าอยู่ในลำดับที่ถูกต้องหรือไม่ 8 > 6, เราก็สลับมันกัน ต่อไปเราจะดูองค์ประกอบที่สองและสาม ซึ่งตอนนี้คือ 8 และ 4 ด้วยเหตุผลเดียวกัน เราจึงสลับองค์ประกอบเหล่านั้น เป็นครั้งที่สามที่เราเปรียบเทียบ 8 และ 2 โดยรวมแล้วเราทำการแลกเปลี่ยนสามครั้ง (8, 6), (8, 4), (8, 2) ค่า 8 "ลอย" ไปที่ท้ายรายการในตำแหน่งที่ถูกต้อง
ขั้นตอนที่ 2:สลับ (6,4) และ (6,2) ขณะนี้หมายเลข 6 อยู่ในตำแหน่งสุดท้าย และไม่จำเป็นต้องเปรียบเทียบกับ "ส่วนท้าย" ของรายการที่เรียงลำดับไว้แล้ว
ขั้นตอนที่ 3:สลับ 4 และ 2 ทั้งสี่ "ลอยขึ้น" ไปยังตำแหน่งที่ถูกต้อง
ขั้นตอนที่ 4:เราผ่านอาร์เรย์ แต่เราไม่มีอะไรจะเปลี่ยนแปลง นี่เป็นการส่งสัญญาณว่าอาร์เรย์ได้รับการจัดเรียงอย่างสมบูรณ์
และนี่คือรหัสอัลกอริทึม ลองนำไปใช้ใน C!
การเรียงลำดับแบบบับเบิ้ลจะใช้เวลา O(n 2 ) ในกรณีที่แย่ที่สุด (ตัวเลขทั้งหมดผิด) เนื่องจากเราจำเป็นต้องดำเนินการ n ขั้นตอนในการวนซ้ำแต่ละครั้ง ซึ่งก็มี n เช่นกัน ในความเป็นจริง เช่นเดียวกับในกรณีของอัลกอริธึมการเรียงลำดับการเลือก เวลาจะน้อยกว่าเล็กน้อย (n 2 /2 – n/2) แต่สิ่งนี้สามารถถูกละเลยได้ ในกรณีที่ดีที่สุด (หากองค์ประกอบทั้งหมดมีอยู่แล้ว) เราสามารถทำได้ใน n ขั้นตอน กล่าวคือ Ω(n) เนื่องจากเราจะต้องวนซ้ำผ่านอาร์เรย์หนึ่งครั้งและตรวจสอบให้แน่ใจว่าองค์ประกอบทั้งหมดอยู่ในตำแหน่ง (นั่นคือ แม้แต่องค์ประกอบ n-1)
มาดูกันว่าการเรียงลำดับการแทรกทำงานอย่างไรโดยใช้ตัวอย่างด้านล่าง ก่อนที่เราจะเริ่ม องค์ประกอบทั้งหมดจะถือว่าไม่เรียงลำดับ
ขั้นตอนที่ 1:นำค่าที่ไม่ได้เรียงลำดับค่าแรก (3) แล้วแทรกลงในอาร์เรย์ย่อยที่เรียงลำดับ ในขั้นตอนนี้ อาร์เรย์ย่อยที่เรียงลำดับทั้งหมด จุดเริ่มต้นและจุดสิ้นสุดจะเป็นสามอันนี้
ขั้นตอนที่ 2:เนื่องจาก 3 > 5 เราจะแทรก 5 ลงในอาร์เรย์ย่อยที่เรียงลำดับทางด้านขวาของ 3
ขั้นตอนที่ 3:ตอนนี้เรากำลังดำเนินการแทรกหมายเลข 2 ลงในอาร์เรย์ที่เรียงลำดับของเรา เราเปรียบเทียบ 2 กับค่าจากขวาไปซ้ายเพื่อค้นหาตำแหน่งที่ถูกต้อง ตั้งแต่ 2 < 5 และ 2 < 3 และเรามาถึงจุดเริ่มต้นของอาร์เรย์ย่อยที่เรียงลำดับแล้ว ดังนั้นเราจึงต้องแทรก 2 ทางด้านซ้ายของ 3 เมื่อต้องการทำเช่นนี้ ให้เลื่อน 3 และ 5 ไปทางขวาเพื่อให้มีที่ว่างสำหรับ 2 และแทรกไว้ที่จุดเริ่มต้นของอาร์เรย์
ขั้นตอนที่ 4เราโชคดี: 6 > 5 เราก็เลยใส่เลขนั้นไว้หลังเลข 5 ได้เลย
ขั้นตอนที่ 5 4 < 6 และ 4 < 5 แต่ 4 > 3 ดังนั้นเราจึงรู้ว่าต้องใส่ 4 ใน ทางขวาของ 3 อีกครั้ง เราถูกบังคับให้ย้าย 5 และ 6 ไปทางขวาเพื่อสร้างช่องว่างสำหรับ 4
เสร็จแล้ว! อัลกอริทึมทั่วไป: นำแต่ละองค์ประกอบที่ไม่เรียงลำดับของ n มาเปรียบเทียบกับค่าในอาร์เรย์ย่อยที่เรียงลำดับจากขวาไปซ้ายจนกว่าเราจะพบตำแหน่งที่เหมาะสมสำหรับ n (นั่นคือช่วงเวลาที่เราพบตัวเลขแรกที่น้อยกว่า n) . จากนั้นเราเลื่อนองค์ประกอบที่เรียงลำดับทั้งหมดที่อยู่ทางด้านขวาของตัวเลขนี้ไปทางขวาเพื่อให้มีที่ว่างสำหรับ n ของเรา และเราก็แทรกมันเข้าไปตรงนั้น เพื่อขยายส่วนที่เรียงลำดับของอาร์เรย์ สำหรับแต่ละองค์ประกอบที่ไม่ได้เรียงลำดับ คุณต้องการ:
สมมติว่าเรามีองค์ประกอบ n รายการที่จะเรียงลำดับ ถ้า n < 2 เราจะเรียงลำดับให้เสร็จสิ้น ไม่เช่นนั้นเราจะเรียงลำดับส่วนซ้ายและขวาของอาร์เรย์แยกกัน แล้วจึงรวมเข้าด้วยกัน มาจัดเรียงอาร์เรย์กันดีกว่า
แบ่งออกเป็นสองส่วน และแบ่งต่อไปจนกว่าเราจะได้อาร์เรย์ย่อยขนาด 1 ซึ่งได้รับการจัดเรียงอย่างชัดเจน
อาร์เรย์ย่อยที่เรียงลำดับสองรายการสามารถรวมเข้าด้วยกันได้ในเวลา O(n) โดยใช้อัลกอริธึมง่ายๆ: ลบตัวเลขที่น้อยกว่าที่จุดเริ่มต้นของแต่ละอาร์เรย์ย่อยแล้วแทรกลงในอาร์เรย์ที่ผสาน ทำซ้ำจนกว่าองค์ประกอบทั้งหมดจะหายไป
การเรียงลำดับแบบผสานจะใช้เวลา O(nlog n) สำหรับทุกกรณี ในขณะที่เราแบ่งอาร์เรย์ออกเป็นครึ่งหนึ่งในแต่ละระดับการเรียกซ้ำ เราจะได้รับบันทึก n จากนั้น การรวมอาร์เรย์ย่อยต้องใช้การเปรียบเทียบเพียง n รายการเท่านั้น ดังนั้น O(nlog n) กรณีที่ดีที่สุดและแย่ที่สุดสำหรับการเรียงลำดับแบบผสานจะเหมือนกัน เวลาทำงานที่คาดหวังของอัลกอริทึม = Θ(nlog n) อัลกอริทึมนี้มีประสิทธิภาพมากที่สุดในบรรดาที่พิจารณา
สัญกรณ์ซีมโทติค
การวัดความเร็วของอัลกอริทึมแบบเรียลไทม์ในหน่วยวินาทีและนาทีไม่ใช่เรื่องง่าย โปรแกรมหนึ่งอาจทำงานช้ากว่าโปรแกรมอื่นไม่ใช่เพราะความไร้ประสิทธิภาพของตัวมันเอง แต่เนื่องจากระบบปฏิบัติการช้า ความเข้ากันไม่ได้กับฮาร์ดแวร์ หน่วยความจำคอมพิวเตอร์ถูกครอบครองโดยกระบวนการอื่น... เพื่อวัดประสิทธิภาพของอัลกอริธึมจึงมีการคิดค้นแนวคิดสากลขึ้นมา เพื่อวัดประสิทธิภาพของอัลกอริธึม โดยไม่คำนึงถึงสภาพแวดล้อมที่โปรแกรมกำลังทำงานอยู่ ความซับซ้อนเชิงเส้นกำกับของปัญหาวัดโดยใช้สัญลักษณ์ Big O กำหนดให้ f(x) และ g(x) เป็นฟังก์ชันที่กำหนดไว้ในย่านใกล้เคียงที่แน่นอนของ x0 และ g จะไม่หายไปตรงนั้น จากนั้น f คือ “O” มากกว่า g สำหรับ (x -> x0) ถ้ามีค่าคงที่ C> 0 ซึ่งสำหรับ x ทั้งหมดจากย่านใกล้เคียงบางจุด x0 ความไม่เท่าเทียมกันคงอยู่|f(x)| <= C |g(x)|
เข้มงวดน้อยกว่าเล็กน้อย: f คือ “O” มากกว่า g หากมีค่าคงที่ C>0 ซึ่งสำหรับ x ทั้งหมด > x0 f(x) <= C*g(x)
อย่ากลัว คำจำกัดความอย่างเป็นทางการ! โดยพื้นฐานแล้ว มันจะกำหนดเวลาที่เพิ่มขึ้นเชิงเส้นกำกับของโปรแกรมเมื่อปริมาณข้อมูลอินพุตของคุณเพิ่มขึ้นไปสู่ระยะอนันต์ ตัวอย่างเช่น คุณกำลังเปรียบเทียบการเรียงลำดับอาร์เรย์ที่มีองค์ประกอบ 1,000 รายการและองค์ประกอบ 10 รายการ และคุณจำเป็นต้องเข้าใจว่าเวลาการทำงานของโปรแกรมจะเพิ่มขึ้นอย่างไร หรือคุณจำเป็นต้องคำนวณความยาวของสตริงอักขระโดยไปทีละอักขระและเพิ่ม 1 สำหรับแต่ละอักขระ: c - 1 a - 2 t - 3
ความเร็วเชิงเส้นกำกับ = O(n) โดยที่ n คือจำนวนตัวอักษรในคำ หากนับตามหลักการนี้ เวลาที่ใช้ในการนับทั้งบรรทัดจะเป็นสัดส่วนกับจำนวนอักขระ การนับจำนวนอักขระในสตริง 20 อักขระใช้เวลานานเป็นสองเท่าของการนับจำนวนอักขระในสตริง 10 อักขระ ลองนึกภาพว่าในตัวแปรความยาวคุณเก็บค่าเท่ากับจำนวนอักขระในสตริง ตัวอย่างเช่น ความยาว = 1,000 หากต้องการทราบความยาวของสตริง คุณเพียงแค่ต้องเข้าถึงตัวแปรนี้เท่านั้น คุณไม่จำเป็นต้องดูที่ตัวสตริงด้วยซ้ำ และไม่ว่าเราจะเปลี่ยนความยาวอย่างไร เราก็สามารถเข้าถึงตัวแปรนี้ได้เสมอ ในกรณีนี้ ความเร็วเชิงเส้นกำกับ = O(1) การเปลี่ยนข้อมูลอินพุตจะไม่เปลี่ยนความเร็วของงานดังกล่าว การค้นหาจะเสร็จสิ้นในเวลาคงที่ ในกรณีนี้ โปรแกรมจะเป็นค่าคงที่เชิงเส้นกำกับ ข้อเสีย: คุณสิ้นเปลืองหน่วยความจำคอมพิวเตอร์ในการจัดเก็บตัวแปรเพิ่มเติมและใช้เวลาเพิ่มเติมในการอัปเดตค่า หากคุณคิดว่าเวลาเชิงเส้นไม่ดี เรารับประกันได้ว่ามันจะแย่กว่านั้นมาก ตัวอย่างเช่น O(n 2 ) สัญลักษณ์นี้หมายความว่าเมื่อ n เพิ่มขึ้น เวลาที่ต้องใช้ในการวนซ้ำผ่านองค์ประกอบต่างๆ (หรือการกระทำอื่น) จะเพิ่มมากขึ้นอย่างรวดเร็ว แต่สำหรับ n ขนาดเล็ก อัลกอริธึมที่มีความเร็วเชิงเส้นกำกับ O(n 2 ) สามารถทำงานได้เร็วกว่าอัลกอริทึมที่มีความเร็วเชิงเส้นกำกับ O(n) ![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติก การเรียงลำดับและการค้นหาอัลกอริธึม - 1](https://cdn.javarush.com/images/article/6b94db45-3b8d-44fd-9c37-79b64c478793/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 2](https://cdn.javarush.com/images/article/a9c33962-7185-4050-8c1a-7c3e93d4447c/512.jpeg)
การค้นหาเชิงเส้น
เมื่อคุณเปิดเว็บเบราว์เซอร์ ให้มองหาเพจ ข้อมูล เพื่อนบนโซเชียลเน็ตเวิร์ก คุณกำลังค้นหา เช่นเดียวกับเมื่อคุณพยายามค้นหารองเท้าคู่ที่ใช่ในร้านค้า คุณอาจสังเกตเห็นว่าความเป็นระเบียบเรียบร้อยมีผลกระทบอย่างมากต่อวิธีค้นหาของคุณ หากคุณมีเสื้อเชิ้ตทุกตัวในตู้เสื้อผ้า โดยปกติแล้วการค้นหาตัวที่คุณต้องการจะง่ายกว่าเสื้อเชิ้ตที่กระจัดกระจายโดยไม่มีระบบทั่วทั้งห้อง การค้นหาเชิงเส้นเป็นวิธีการค้นหาตามลำดับทีละรายการ เมื่อคุณตรวจสอบผลการค้นหาของ Google จากบนลงล่าง คุณกำลังใช้การค้นหาเชิงเส้น ตัวอย่าง . สมมติว่าเรามีรายการตัวเลข2 4 0 5 3 7 8 1
และเราจำเป็นต้องหา 0 เราเห็นมันทันที แต่โปรแกรมคอมพิวเตอร์ไม่ทำงานอย่างนั้น เธอเริ่มต้นที่จุดเริ่มต้นของรายการและเห็นหมายเลข 2 จากนั้นเธอตรวจสอบ 2=0? มันไม่ใช่ ดังนั้นเธอจึงดำเนินการต่อและไปยังตัวละครตัวที่สอง ความล้มเหลวก็รอเธออยู่ที่นั่นเช่นกัน และเฉพาะในตำแหน่งที่สามเท่านั้นที่อัลกอริธึมจะค้นหาหมายเลขที่ต้องการ รหัสหลอกสำหรับการค้นหาเชิงเส้น: ![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 3](https://cdn.javarush.com/images/article/9cb057a2-1499-4da6-86da-e1906eec9daa/512.jpeg)
![เนื้อหาเพิ่มเติมของ CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 4](https://cdn.javarush.com/images/article/bb83aa4a-a7a9-471a-b09d-ea634411fc5b/512.jpeg)
การค้นหาแบบไบนารีและต้นไม้
ลองนึกภาพคุณมีรายชื่อตัวละครดิสนีย์เรียงตามตัวอักษรและคุณจำเป็นต้องค้นหามิกกี้เมาส์![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติก การเรียงลำดับและการค้นหาอัลกอริธึม - 5](https://cdn.javarush.com/images/article/5f7e4f9f-ffc7-4cc9-9d28-35cf33d710f6/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 6](https://cdn.javarush.com/images/article/e34ed422-940e-49ed-ba57-8775dca438bd/512.jpeg)
![วัสดุเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 7](https://cdn.javarush.com/images/article/4280425d-8e9c-4bd2-9d40-06ef09c0a009/512.jpeg)
![วัสดุเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 8](https://cdn.javarush.com/images/article/733bbf87-5266-4f97-9fe1-837ba7db806f/512.jpeg)
![วัสดุเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 9](https://cdn.javarush.com/images/article/6383e573-9266-47ce-be8f-7459c5226d22/512.jpeg)
![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติค การเรียงลำดับและการค้นหาอัลกอริธึม - 10](https://cdn.javarush.com/images/article/7249f603-ae82-4be7-b013-0bfc80ed2e6c/512.jpeg)
![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติค การเรียงลำดับและการค้นหาอัลกอริธึม - 11](https://cdn.javarush.com/images/article/0d65a115-18f0-40f7-9a2e-0a47d93ca879/256.jpeg)
![สื่อเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติก การเรียงลำดับและการค้นหาอัลกอริธึม - 12](https://cdn.javarush.com/images/article/de388eef-a0f3-4b07-a5a7-935da24d82aa/512.jpeg)
![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติก การเรียงลำดับและการค้นหาอัลกอริธึม - 13](https://cdn.javarush.com/images/article/51d32383-651e-4db6-80ac-704088e79c5a/512.jpeg)
![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติก การเรียงลำดับและการค้นหาอัลกอริธึม - 14](https://cdn.javarush.com/images/article/12398fd4-45d7-4526-9475-139315afb6ce/512.jpeg)
![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติก การเรียงลำดับและการค้นหาอัลกอริธึม - 15](https://cdn.javarush.com/images/article/1d1c9a7e-8bc3-4d2f-b5e1-7bc3e84ef55f/512.jpeg)
![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติค การเรียงลำดับและการค้นหาอัลกอริธึม - 16](https://cdn.javarush.com/images/article/242f9728-8294-4f47-b28d-a276616a5949/256.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 17](https://cdn.javarush.com/images/article/e48f7e23-eeee-4ba8-8c00-c7098b4ce930/256.jpeg)
- จัดเรียงรายการและใช้การค้นหาแบบไบนารี
- จัดเรียงรายการอยู่เสมอในขณะที่เพิ่มและลบองค์ประกอบออกจากรายการไปพร้อมๆ กัน
- มันคือต้นไม้ (โครงสร้างข้อมูลที่จำลองโครงสร้างต้นไม้ - มีรากและโหนดอื่น ๆ (ใบ) เชื่อมต่อกันด้วย "กิ่งก้าน" หรือขอบโดยไม่มีวงจร)
- แต่ละโหนดมีลูก 0, 1 หรือ 2 ตัว
- แผนผังย่อยทั้งซ้ายและขวาเป็นแผนผังการค้นหาแบบไบนารี
- โหนดทั้งหมดของทรีย่อยด้านซ้ายของโหนด X โดยพลการมีค่าคีย์ข้อมูลน้อยกว่าค่าของคีย์ข้อมูลของโหนด X เอง
- โหนดทั้งหมดในแผนผังย่อยด้านขวาของโหนด X โดยพลการมีค่าคีย์ข้อมูลมากกว่าหรือเท่ากับค่าของคีย์ข้อมูลของโหนด X เอง
![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติค การเรียงลำดับและการค้นหาอัลกอริธึม - 18](https://cdn.javarush.com/images/article/379650c1-8a67-4532-b247-3e5a7ad475c4/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 19](https://cdn.javarush.com/images/article/51ec988d-0961-4eb2-b131-d8d9c030a8ea/512.jpeg)
![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติก การเรียงลำดับและการค้นหาอัลกอริธึม - 20](https://cdn.javarush.com/images/article/1e4a3a13-1f27-4366-bfd1-17ae21062c93/512.jpeg)
![เนื้อหาเพิ่มเติมของ CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 21](https://cdn.javarush.com/images/article/8cf552b2-e4c1-4775-aa84-dd8f4984bd90/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 22](https://cdn.javarush.com/images/article/4a9c875a-a4fd-4249-8f1c-767fd4e73da8/512.jpeg)
![เนื้อหาเพิ่มเติมของ CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 23](https://cdn.javarush.com/images/article/6ef41b00-5d77-4f95-a2f4-248a5cda0bb3/512.jpeg)
![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติก การเรียงลำดับและการค้นหาอัลกอริธึม - 24](https://cdn.javarush.com/images/article/c2e66f75-a2c8-4ef7-8bbb-273cb1d26974/512.jpeg)
- ตัวเลือกที่ง่ายที่สุด: เราจำเป็นต้องลบจุดยอดที่ไม่มีลูก เช่น เลข 7 ที่เราเพิ่งบวกเข้าไป ในกรณีนี้ เราเพียงแต่เดินตามเส้นทางไปยังจุดยอดที่มีหมายเลขนี้แล้วลบออก
- จุดยอดมีจุดยอดลูกหนึ่งจุด ในกรณีนี้คุณสามารถลบจุดยอดที่ต้องการได้ แต่ลูกหลานจะต้องเชื่อมต่อกับ "ปู่" นั่นคือจุดยอดที่บรรพบุรุษของมันเติบโตขึ้น ตัวอย่างเช่น จากต้นไม้ต้นเดียวกัน เราจำเป็นต้องลบหมายเลข 3 ออก ในกรณีนี้ เรารวมลูกหลานของมัน หนึ่ง ร่วมกับทรีย่อยทั้งหมดเป็น 5 ซึ่งทำได้ง่ายๆ เนื่องจากจุดยอดทั้งหมดทางด้านซ้ายของ 5 จะเป็น น้อยกว่าจำนวนนี้ (และน้อยกว่าสามเท่าระยะไกล)
- กรณีที่ยากที่สุดคือเมื่อจุดยอดที่ถูกลบมีลูกสองคน ตอนนี้สิ่งแรกที่เราต้องทำคือค้นหาจุดยอดที่มีการซ่อนค่าที่ใหญ่กว่าถัดไปไว้ เราต้องสลับจุดเหล่านั้น แล้วลบจุดยอดที่ต้องการ โปรดทราบว่าจุดยอดที่มีค่าสูงสุดถัดไปไม่สามารถมีลูกสองคนได้ ดังนั้นลูกด้านซ้ายจะเป็นตัวเลือกที่ดีที่สุดสำหรับค่าถัดไป ลองลบโหนดรูท 13 ออกจากแผนผังของเรา อันดับแรก เรามองหาจำนวนที่ใกล้เคียงที่สุดกับ 13 ซึ่งมากกว่าจำนวนนั้น นี่คือ 21 สลับ 21 กับ 13 และลบ 13
![เนื้อหาเพิ่มเติมของ CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 26](https://cdn.javarush.com/images/article/c183107c-d5b6-421a-8bbb-ce02efbd20a0/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 27](https://cdn.javarush.com/images/article/0037099b-9500-43f0-b619-549e823018b9/512.jpeg)
อัลกอริธึมการเรียงลำดับ
มีอาร์เรย์ของตัวเลข เราจำเป็นต้องจัดเรียงมัน เพื่อความง่าย เราจะถือว่าเรากำลังเรียงลำดับจำนวนเต็มจากน้อยไปมาก (จากน้อยไปหามาก) มีวิธีที่ทราบหลายวิธีในการทำให้กระบวนการนี้สำเร็จ นอกจากนี้คุณยังสามารถฝันถึงหัวข้อและแก้ไขอัลกอริทึมได้ตลอดเวลาเรียงตามการเลือก
![เนื้อหาเพิ่มเติมของ CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 28](https://cdn.javarush.com/images/article/708338a3-8128-48de-a1fb-630b8f14ec66/512.jpeg)
- ค้นหาค่าต่ำสุดที่ไม่ได้เรียงลำดับ
- เราสลับค่านี้กับค่าที่ไม่ได้เรียงลำดับค่าแรก ดังนั้นให้วางไว้ที่ส่วนท้ายของอาร์เรย์ที่เรียงลำดับแล้ว
- หากยังมีค่าที่ยังไม่ได้เรียงลำดับให้กลับไปสู่ขั้นตอนที่ 1
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 29](https://cdn.javarush.com/images/article/71b8e06a-af3f-44a0-a4ba-34577576590e/512.jpeg)
![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติก การเรียงลำดับและการค้นหาอัลกอริธึม - 30](https://cdn.javarush.com/images/article/00370166-af51-4328-9802-353fc81dbda8/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 31](https://cdn.javarush.com/images/article/208ac105-9613-47f5-85f3-ca22775a2c4f/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 32](https://cdn.javarush.com/images/article/363c1174-2a18-46c8-b2e5-055752a22837/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 33](https://cdn.javarush.com/images/article/7fb7aeb9-c27e-4304-be35-e0e135e1c7c3/512.jpeg)
![เนื้อหาเพิ่มเติมของ CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 34](https://cdn.javarush.com/images/article/8ccaccba-cb2b-46f7-82ba-38a196bc1134/512.jpeg)
![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติค การเรียงลำดับและการค้นหาอัลกอริธึม - 35](https://cdn.javarush.com/images/article/9885d4dd-0f5c-4470-b742-42f7001535b2/512.jpeg)
![สูตร](https://cdn.javarush.com/images/article/4d503c77-8af2-48ff-a53b-47e911ccbec0/original.jpeg)
การเรียงลำดับฟอง
อัลกอริธึมการเรียงลำดับแบบฟองเป็นหนึ่งในวิธีที่ง่ายที่สุด เราไปตามอาร์เรย์ทั้งหมดและเปรียบเทียบ 2 องค์ประกอบใกล้เคียง หากผิดลำดับเราจะเปลี่ยนให้ ในการผ่านครั้งแรก องค์ประกอบที่เล็กที่สุดจะปรากฏ (“ลอย”) ที่ส่วนท้าย (หากเราเรียงลำดับจากมากไปน้อย) ทำซ้ำขั้นตอนแรกหากมีการแลกเปลี่ยนเสร็จสิ้นในขั้นตอนก่อนหน้าอย่างน้อยหนึ่งครั้ง มาเรียงลำดับอาร์เรย์กันดีกว่า![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 36](https://cdn.javarush.com/images/article/e70a99b0-c637-4c00-bfd0-37975e436252/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 37](https://cdn.javarush.com/images/article/6c83ad33-d1fe-4539-b8ba-cef8135775ea/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 38](https://cdn.javarush.com/images/article/1a3001f1-6e67-49f3-9d7c-ea57cab9a920/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 39](https://cdn.javarush.com/images/article/e3d38ef6-ecf0-4c5a-a63c-6cb36af40b9a/512.jpeg)
![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติค การเรียงลำดับและการค้นหาอัลกอริธึม - 40](https://cdn.javarush.com/images/article/dd480a84-ab2e-448b-b31a-8497b4d8286a/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 43](https://cdn.javarush.com/images/article/570fc185-8d60-4d06-9b45-54136e3588e2/512.jpeg)
การเรียงลำดับการแทรก
แนวคิดหลักของอัลกอริธึมนี้คือการแบ่งอาเรย์ของเราออกเป็นสองส่วนคือเรียงลำดับและไม่เรียงลำดับ ในแต่ละขั้นตอนของอัลกอริทึม ตัวเลขจะย้ายจากส่วนที่ไม่ได้เรียงลำดับไปยังส่วนที่เรียงลำดับ![เนื้อหาเพิ่มเติมของ CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 41](https://cdn.javarush.com/images/article/5c5aa779-75fb-4246-a917-5bca22a9bc9c/512.jpeg)
![เนื้อหาเพิ่มเติมของ CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 42](https://cdn.javarush.com/images/article/0b6d2eb6-9ea3-483b-b05d-04b5debb5bef/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 43](https://cdn.javarush.com/images/article/806ccf98-231a-4ee6-97b2-4d41663db6ba/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 44](https://cdn.javarush.com/images/article/99add72a-17dd-4594-8f42-c0e6f77d5a29/512.jpeg)
![วัสดุเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 45](https://cdn.javarush.com/images/article/4484635a-f63d-4e98-aeba-c59a3798c29f/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 46](https://cdn.javarush.com/images/article/c04d159f-800f-4855-9f1e-37720ced17c5/512.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 47](https://cdn.javarush.com/images/article/d7e30834-3850-4a9f-9dd9-f550abbc2751/512.jpeg)
- กำหนดตำแหน่งในส่วนที่เรียงลำดับของอาร์เรย์ที่ควรแทรก n
- เลื่อนองค์ประกอบที่จัดเรียงไปทางขวาเพื่อสร้างช่องว่างสำหรับ n
- แทรก n ลงในช่องว่างผลลัพธ์ในส่วนที่เรียงลำดับของอาร์เรย์
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 48](https://cdn.javarush.com/images/article/a4e91b21-218d-4aa6-be24-4b59f054e897/512.jpeg)
ความเร็วเชิงเส้นกำกับของอัลกอริทึม
ในกรณีที่เลวร้ายที่สุด เราจะทำการเปรียบเทียบกับองค์ประกอบที่สองหนึ่งรายการ การเปรียบเทียบกับองค์ประกอบที่สามสองครั้ง และอื่นๆ ดังนั้นความเร็วของเราคือ O(n 2 ) อย่างดีที่สุด เราจะทำงานกับอาร์เรย์ที่เรียงลำดับแล้ว ส่วนที่เรียงลำดับซึ่งเราสร้างจากซ้ายไปขวาโดยไม่มีการแทรกและการเคลื่อนไหวขององค์ประกอบจะใช้เวลา Ω(n)ผสานการเรียงลำดับ
อัลกอริธึมนี้เป็นแบบเรียกซ้ำ โดยแบ่งปัญหาการเรียงลำดับขนาดใหญ่หนึ่งปัญหาออกเป็นงานย่อย การดำเนินการดังกล่าวทำให้เข้าใกล้การแก้ปัญหาใหญ่เดิมมากขึ้น แนวคิดหลักคือการแบ่งอาร์เรย์ที่ไม่ได้เรียงลำดับออกเป็นสองส่วนและเรียงลำดับแต่ละครึ่งแบบวนซ้ำ![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 49](https://cdn.javarush.com/images/article/66dff8c1-4e56-442b-aa1a-2ed957ceb35e/512.jpeg)
![สื่อการสอนเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญกรณ์ซีมโทติก การเรียงลำดับและการค้นหาอัลกอริธึม - 50](https://cdn.javarush.com/images/article/2eb22eb5-b0a6-440d-b0ca-e3b1912fec50/512.jpeg)
![วัสดุเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 51](https://cdn.javarush.com/images/article/484353c2-35f5-4ea1-a904-51feac3f053d/512.jpeg)
![วัสดุเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 52](https://cdn.javarush.com/images/article/4763925c-1b75-4c30-9e38-48e57ee8b9d0/512.jpeg)
![เนื้อหาเพิ่มเติมของ CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 56](https://cdn.javarush.com/images/article/208f0f61-050e-4b8d-ae4d-e10bf1f7b9ea/512.jpeg)
![วัสดุเพิ่มเติม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 53](https://cdn.javarush.com/images/article/2c26c238-e5ab-4558-92d9-7069192ab722/1024.jpeg)
![วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและการค้นหาอัลกอริทึม - 58](https://cdn.javarush.com/images/article/cf19e9ea-a092-4567-bb52-ec14738ff018/1024.jpeg)
GO TO FULL VERSION