วัสดุเสริม CS50 (สัปดาห์ที่ 3 การบรรยายที่ 7 และ 8): สัญลักษณ์เชิงเส้นกำกับ การเรียงลำดับและอัลกอริทึมการค้นหา

การบรรยายจากหลักสูตร Harvard เกี่ยวกับพื้นฐานการเขียนโปรแกรม CS50 การมอบหมายงาน CS50 สัปดาห์ที่ 3 ส่วนที่ 1 การมอบหมายงาน CS50 สัปดาห์ที่ 3 ส่วนที่ 2

สัญกรณ์ซีมโทติค

การวัดความเร็วของอัลกอริทึมแบบเรียลไทม์ในหน่วยวินาทีและนาทีไม่ใช่เรื่องง่าย โปรแกรมหนึ่งอาจทำงานช้ากว่าโปรแกรมอื่นไม่ใช่เพราะความไร้ประสิทธิภาพของตัวมันเอง แต่เนื่องจากระบบปฏิบัติการช้า ความเข้ากันไม่ได้กับฮาร์ดแวร์ หน่วยความจำคอมพิวเตอร์ถูกครอบครองโดยกระบวนการอื่น... เพื่อวัดประสิทธิภาพของอัลกอริธึมจึงมีการคิดค้นแนวคิดสากลขึ้นมา เพื่อวัดประสิทธิภาพของอัลกอริธึม โดยไม่คำนึงถึงสภาพแวดล้อมที่โปรแกรมกำลังทำงานอยู่ ความซับซ้อนเชิงเส้นกำกับของปัญหาวัดโดยใช้สัญลักษณ์ 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 ² ) สัญลักษณ์นี้หมายความว่าเมื่อ n เพิ่มขึ้น เวลาที่ต้องใช้ในการวนซ้ำผ่านองค์ประกอบต่างๆ (หรือการกระทำอื่น) จะเพิ่มมากขึ้นอย่างรวดเร็ว แต่สำหรับ n ขนาดเล็ก อัลกอริธึมที่มีความเร็วเชิงเส้นกำกับ O(n ² ) สามารถทำงานได้เร็วกว่าอัลกอริทึมที่มีความเร็วเชิงเส้นกำกับ O(n) แต่เมื่อถึงจุดหนึ่ง ฟังก์ชันกำลังสองจะแซงฟังก์ชันเชิงเส้น ไม่มีทางเลี่ยงมันได้ ความซับซ้อนเชิงซีมโทติกอีกประการหนึ่งคือเวลาลอการิทึมหรือ O(log n) เมื่อ n เพิ่มขึ้น ฟังก์ชันนี้จะเพิ่มขึ้นอย่างช้าๆ O(log n) คือเวลาทำงานของอัลกอริธึมการค้นหาไบนารีแบบคลาสสิกในอาเรย์ที่เรียงลำดับ (จำสมุดโทรศัพท์ที่ขาดในการบรรยายได้ไหม) อาร์เรย์ถูกแบ่งออกเป็นสองส่วน จากนั้นเลือกครึ่งหนึ่งซึ่งองค์ประกอบนั้นถูกเลือก ดังนั้น ทุกครั้งที่ลดพื้นที่การค้นหาลงครึ่งหนึ่ง เราจะค้นหาองค์ประกอบนั้น จะเกิดอะไรขึ้นถ้าเราสะดุดกับสิ่งที่เรากำลังมองหาโดยแบ่งอาร์เรย์ข้อมูลของเราออกเป็นสองส่วนเป็นครั้งแรก? มีคำศัพท์สำหรับเวลาที่ดีที่สุด - Omega-large หรือ Ω(n) ในกรณีของการค้นหาแบบไบนารี = Ω(1) (ค้นหาในเวลาคงที่ โดยไม่คำนึงถึงขนาดของอาร์เรย์) การค้นหาเชิงเส้นจะทำงานในเวลา O(n) และ Ω(1) หากองค์ประกอบที่กำลังค้นหาเป็นองค์ประกอบแรก อีกสัญลักษณ์หนึ่งคือทีต้า (Θ(n)) ใช้เมื่อตัวเลือกที่ดีที่สุดและแย่ที่สุดเหมือนกัน เหมาะสำหรับตัวอย่างที่เราจัดเก็บความยาวของสตริงไว้ในตัวแปรที่แยกจากกัน ดังนั้นสำหรับความยาวใดๆ ก็เพียงพอแล้วที่จะอ้างอิงถึงตัวแปรนี้ สำหรับอัลกอริทึมนี้ กรณีที่ดีที่สุดและแย่ที่สุดคือ Ω(1) และ O(1) ตามลำดับ ซึ่งหมายความว่าอัลกอริทึมจะทำงานทันเวลา Θ(1)

การค้นหาเชิงเส้น

เมื่อคุณเปิดเว็บเบราว์เซอร์ ให้มองหาเพจ ข้อมูล เพื่อนบนโซเชียลเน็ตเวิร์ก คุณกำลังค้นหา เช่นเดียวกับเมื่อคุณพยายามค้นหารองเท้าคู่ที่ใช่ในร้านค้า คุณอาจสังเกตเห็นว่าความเป็นระเบียบเรียบร้อยมีผลกระทบอย่างมากต่อวิธีค้นหาของคุณ หากคุณมีเสื้อเชิ้ตทุกตัวในตู้เสื้อผ้า โดยปกติแล้วการค้นหาตัวที่คุณต้องการจะง่ายกว่าเสื้อเชิ้ตที่กระจัดกระจายโดยไม่มีระบบทั่วทั้งห้อง การค้นหาเชิงเส้นเป็นวิธีการค้นหาตามลำดับทีละรายการ เมื่อคุณตรวจสอบผลการค้นหาของ Google จากบนลงล่าง คุณกำลังใช้การค้นหาเชิงเส้น ตัวอย่าง . สมมติว่าเรามีรายการตัวเลข 2 4 0 5 3 7 8 1 และเราจำเป็นต้องหา 0 เราเห็นมันทันที แต่โปรแกรมคอมพิวเตอร์ไม่ทำงานอย่างนั้น เธอเริ่มต้นที่จุดเริ่มต้นของรายการและเห็นหมายเลข 2 จากนั้นเธอตรวจสอบ 2=0? มันไม่ใช่ ดังนั้นเธอจึงดำเนินการต่อและไปยังตัวละครตัวที่สอง ความล้มเหลวก็รอเธออยู่ที่นั่นเช่นกัน และเฉพาะในตำแหน่งที่สามเท่านั้นที่อัลกอริธึมจะค้นหาหมายเลขที่ต้องการ รหัสหลอกสำหรับการค้นหาเชิงเส้น: ฟังก์ชั่น 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) เพื่อระบุว่าเราไม่พบสิ่งใดเลย คุณรู้อยู่แล้วว่าการค้นหาแบบไบนารี่จำเป็นต้องเรียงลำดับอาร์เรย์ ดังนั้น หากเรามีอาร์เรย์ที่ไม่เรียงลำดับซึ่งเราจำเป็นต้องค้นหาองค์ประกอบเฉพาะ เราก็มีสองทางเลือก:

1. จัดเรียงรายการและใช้การค้นหาแบบไบนารี
2. จัดเรียงรายการอยู่เสมอในขณะที่เพิ่มและลบองค์ประกอบออกจากรายการไปพร้อมๆ กัน

วิธีหนึ่งในการเรียงลำดับรายการคือการใช้แผนผังการค้นหาแบบไบนารี แผนผังการค้นหาแบบไบนารีเป็นโครงสร้างข้อมูลที่ตรงตามข้อกำหนดต่อไปนี้:

• มันคือต้นไม้ (โครงสร้างข้อมูลที่จำลองโครงสร้างต้นไม้ - มีรากและโหนดอื่น ๆ (ใบ) เชื่อมต่อกันด้วย "กิ่งก้าน" หรือขอบโดยไม่มีวงจร)
• แต่ละโหนดมีลูก 0, 1 หรือ 2 ตัว
• แผนผังย่อยทั้งซ้ายและขวาเป็นแผนผังการค้นหาแบบไบนารี
• โหนดทั้งหมดของทรีย่อยด้านซ้ายของโหนด X โดยพลการมีค่าคีย์ข้อมูลน้อยกว่าค่าของคีย์ข้อมูลของโหนด X เอง
• โหนดทั้งหมดในแผนผังย่อยด้านขวาของโหนด X โดยพลการมีค่าคีย์ข้อมูลมากกว่าหรือเท่ากับค่าของคีย์ข้อมูลของโหนด X เอง

ข้อควรสนใจ: รากของแผนผัง "โปรแกรมเมอร์" ซึ่งแตกต่างจากของจริงอยู่ที่ด้านบน แต่ละเซลล์เรียกว่าจุดยอด และจุดยอดเชื่อมต่อกันด้วยขอบ รากของต้นไม้คือเซลล์หมายเลข 13 ทรีย่อยด้านซ้ายของจุดยอด 3 จะถูกเน้นด้วยสีในภาพด้านล่าง: ต้นไม้ของเราตรงตามข้อกำหนดทั้งหมดสำหรับต้นไม้ไบนารี ซึ่งหมายความว่าทรีย่อยด้านซ้ายแต่ละอันมีเพียงค่าที่น้อยกว่าหรือเท่ากับค่าของจุดยอด ในขณะที่ทรีย่อยด้านขวามีเพียงค่าที่มากกว่าหรือเท่ากับค่าของจุดยอดเท่านั้น ทรีย่อยทั้งซ้ายและขวาต่างก็เป็นทรีย่อยแบบไบนารี วิธีการสร้างต้นไม้ไบนารีไม่ได้เป็นเพียงวิธีเดียว: ด้านล่างในภาพที่คุณเห็นตัวเลือกอื่นสำหรับชุดตัวเลขเดียวกันและอาจมีได้มากมายในทางปฏิบัติ โครงสร้างนี้ช่วยในการค้นหา: เราค้นหาค่าต่ำสุดโดยเลื่อนจากบนไปทางซ้ายและลงล่างในแต่ละครั้ง หากคุณต้องการค้นหาจำนวนสูงสุด เราไปจากบนลงล่างไปทางขวา การค้นหาตัวเลขที่ไม่ใช่ค่าต่ำสุดหรือสูงสุดก็ค่อนข้างง่ายเช่นกัน เราลงมาจากรากไปทางซ้ายหรือทางขวา ขึ้นอยู่กับว่าจุดยอดของเราใหญ่กว่าหรือเล็กกว่าจุดที่เรากำลังมองหา ดังนั้นหากเราต้องการค้นหาหมายเลข 89 เราก็ใช้เส้นทางนี้: คุณยังสามารถแสดงตัวเลขตามลำดับการจัดเรียงได้ ตัวอย่างเช่น หากเราต้องการแสดงตัวเลขทั้งหมดโดยเรียงลำดับจากน้อยไปหามาก เราจะใช้แผนผังย่อยทางซ้ายและเริ่มจากจุดยอดซ้ายสุดขึ้นไป การเพิ่มบางอย่างให้กับต้นไม้ก็เป็นเรื่องง่ายเช่นกัน สิ่งสำคัญที่ต้องจำคือโครงสร้าง สมมติว่าเราต้องเพิ่มค่า 7 ให้กับทรี ไปที่รูทและตรวจสอบกัน เลข 7 < 13 เลยไปทางซ้าย. เราเห็น 5 ตรงนั้น และไปทางขวา เนื่องจาก 7 > 5 นอกจากนี้ เนื่องจาก 7 > 8 และ 8 ไม่มีลูกหลาน เราจึงสร้างสาขาจาก 8 ไปทางซ้ายและแนบ 7 เข้าไป คุณยังสามารถลบจุดยอดออก จาก ต้นไม้ แต่นี่ค่อนข้างซับซ้อนกว่า มีสถานการณ์การลบที่แตกต่างกันสามแบบที่เราต้องพิจารณา

1. ตัวเลือกที่ง่ายที่สุด: เราจำเป็นต้องลบจุดยอดที่ไม่มีลูก เช่น เลข 7 ที่เราเพิ่งบวกเข้าไป ในกรณีนี้ เราเพียงแต่เดินตามเส้นทางไปยังจุดยอดที่มีหมายเลขนี้แล้วลบออก
2. จุดยอดมีจุดยอดลูกหนึ่งจุด ในกรณีนี้คุณสามารถลบจุดยอดที่ต้องการได้ แต่ลูกหลานจะต้องเชื่อมต่อกับ "ปู่" นั่นคือจุดยอดที่บรรพบุรุษของมันเติบโตขึ้น ตัวอย่างเช่น จากต้นไม้ต้นเดียวกัน เราจำเป็นต้องลบหมายเลข 3 ออก ในกรณีนี้ เรารวมลูกหลานของมัน หนึ่ง ร่วมกับทรีย่อยทั้งหมดเป็น 5 ซึ่งทำได้ง่ายๆ เนื่องจากจุดยอดทั้งหมดทางด้านซ้ายของ 5 จะเป็น น้อยกว่าจำนวนนี้ (และน้อยกว่าสามเท่าระยะไกล)
3. กรณีที่ยากที่สุดคือเมื่อจุดยอดที่ถูกลบมีลูกสองคน ตอนนี้สิ่งแรกที่เราต้องทำคือค้นหาจุดยอดที่มีการซ่อนค่าที่ใหญ่กว่าถัดไปไว้ เราต้องสลับจุดเหล่านั้น แล้วลบจุดยอดที่ต้องการ โปรดทราบว่าจุดยอดที่มีค่าสูงสุดถัดไปไม่สามารถมีลูกสองคนได้ ดังนั้นลูกด้านซ้ายจะเป็นตัวเลือกที่ดีที่สุดสำหรับค่าถัดไป ลองลบโหนดรูท 13 ออกจากแผนผังของเรา อันดับแรก เรามองหาจำนวนที่ใกล้เคียงที่สุดกับ 13 ซึ่งมากกว่าจำนวนนั้น นี่คือ 21 สลับ 21 กับ 13 และลบ 13

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

อัลกอริธึมการเรียงลำดับ

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

เรียงตามการเลือก

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

1. ค้นหาค่าต่ำสุดที่ไม่ได้เรียงลำดับ
2. เราสลับค่านี้กับค่าที่ไม่ได้เรียงลำดับค่าแรก ดังนั้นให้วางไว้ที่ส่วนท้ายของอาร์เรย์ที่เรียงลำดับแล้ว
3. หากยังมีค่าที่ยังไม่ได้เรียงลำดับให้กลับไปสู่ขั้นตอนที่ 1

ในขั้นตอนแรกค่าทั้งหมดจะไม่เรียงลำดับ ลองเรียกส่วนที่ไม่ได้เรียงลำดับว่า Unsorted และส่วนที่เรียงลำดับแล้ว Sorted (นี่เป็นเพียงคำภาษาอังกฤษ และเราทำเช่นนี้เพียงเพราะว่า Sorted นั้นสั้นกว่า "ส่วนที่เรียงลำดับ" มากและจะดูดีกว่าในรูปภาพ) เราค้นหาจำนวนขั้นต่ำในส่วนที่ไม่ได้เรียงลำดับของอาร์เรย์ (นั่นคือในขั้นตอนนี้ - ในอาร์เรย์ทั้งหมด) หมายเลขนี้คือ 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 ² ) ในกรณีที่แย่ที่สุด (ตัวเลขทั้งหมดผิด) เนื่องจากเราจำเป็นต้องดำเนินการ n ขั้นตอนในการวนซ้ำแต่ละครั้ง ซึ่งก็มี n เช่นกัน ในความเป็นจริง เช่นเดียวกับในกรณีของอัลกอริธึมการเรียงลำดับการเลือก เวลาจะน้อยกว่าเล็กน้อย (n ² /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 ของเรา และเราก็แทรกมันเข้าไปตรงนั้น เพื่อขยายส่วนที่เรียงลำดับของอาร์เรย์ สำหรับแต่ละองค์ประกอบที่ไม่ได้เรียงลำดับ คุณต้องการ:

2. กำหนดตำแหน่งในส่วนที่เรียงลำดับของอาร์เรย์ที่ควรแทรก n
3. เลื่อนองค์ประกอบที่จัดเรียงไปทางขวาเพื่อสร้างช่องว่างสำหรับ n
4. แทรก n ลงในช่องว่างผลลัพธ์ในส่วนที่เรียงลำดับของอาร์เรย์

และนี่คือรหัส! เราขอแนะนำให้เขียนโปรแกรมเรียงลำดับเวอร์ชันของคุณเอง

ความเร็วเชิงเส้นกำกับของอัลกอริทึม

ในกรณีที่เลวร้ายที่สุด เราจะทำการเปรียบเทียบกับองค์ประกอบที่สองหนึ่งรายการ การเปรียบเทียบกับองค์ประกอบที่สามสองครั้ง และอื่นๆ ดังนั้นความเร็วของเราคือ O(n ² ) อย่างดีที่สุด เราจะทำงานกับอาร์เรย์ที่เรียงลำดับแล้ว ส่วนที่เรียงลำดับซึ่งเราสร้างจากซ้ายไปขวาโดยไม่มีการแทรกและการเคลื่อนไหวขององค์ประกอบจะใช้เวลา Ω(n)

ผสานการเรียงลำดับ

อัลกอริธึมนี้เป็นแบบเรียกซ้ำ โดยแบ่งปัญหาการเรียงลำดับขนาดใหญ่หนึ่งปัญหาออกเป็นงานย่อย การดำเนินการดังกล่าวทำให้เข้าใกล้การแก้ปัญหาใหญ่เดิมมากขึ้น แนวคิดหลักคือการแบ่งอาร์เรย์ที่ไม่ได้เรียงลำดับออกเป็นสองส่วนและเรียงลำดับแต่ละครึ่งแบบวนซ้ำ สมมติว่าเรามีองค์ประกอบ n รายการที่จะเรียงลำดับ ถ้า n < 2 เราจะเรียงลำดับให้เสร็จสิ้น ไม่เช่นนั้นเราจะเรียงลำดับส่วนซ้ายและขวาของอาร์เรย์แยกกัน แล้วจึงรวมเข้าด้วยกัน มาจัดเรียงอาร์เรย์กันดีกว่า แบ่งออกเป็นสองส่วน และแบ่งต่อไปจนกว่าเราจะได้อาร์เรย์ย่อยขนาด 1 ซึ่งได้รับการจัดเรียงอย่างชัดเจน อาร์เรย์ย่อยที่เรียงลำดับสองรายการสามารถรวมเข้าด้วยกันได้ในเวลา O(n) โดยใช้อัลกอริธึมง่ายๆ: ลบตัวเลขที่น้อยกว่าที่จุดเริ่มต้นของแต่ละอาร์เรย์ย่อยแล้วแทรกลงในอาร์เรย์ที่ผสาน ทำซ้ำจนกว่าองค์ประกอบทั้งหมดจะหายไป การเรียงลำดับแบบผสานจะใช้เวลา O(nlog n) สำหรับทุกกรณี ในขณะที่เราแบ่งอาร์เรย์ออกเป็นครึ่งหนึ่งในแต่ละระดับการเรียกซ้ำ เราจะได้รับบันทึก n จากนั้น การรวมอาร์เรย์ย่อยต้องใช้การเปรียบเทียบเพียง n รายการเท่านั้น ดังนั้น O(nlog n) กรณีที่ดีที่สุดและแย่ที่สุดสำหรับการเรียงลำดับแบบผสานจะเหมือนกัน เวลาทำงานที่คาดหวังของอัลกอริทึม = Θ(nlog n) อัลกอริทึมนี้มีประสิทธิภาพมากที่สุดในบรรดาที่พิจารณา