[เล่นดนตรี] 

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

โปรแกรม find.c แจ้งให้สำหรับหมายเลข เพื่อเติมกองหญ้า, การค้นหา กองหญ้าสำหรับเข็มที่ใช้ส่ง และมันไม่นี้โดยการโทรและการจัดเรียง ฟังก์ชั่นการค้นหาที่กำหนดไว้ ใน helpers.c ดังนั้น find.c ถูกเขียนอยู่แล้ว งานของคุณคือการเขียนผู้ช่วยเหลือ 

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

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

แต่มีข้อตกลง ค้นหาแบบไบนารีสามารถค้นหา ผ่านรายการที่เรียงลำดับก่อน ทำไมจึงเป็นเช่นนั้น 

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

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

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

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

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

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

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

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

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

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

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

[เล่นดนตรี]