MARK GROZEN-SMITH: สวัสดีครับผมมาร์ค Grozen สมิ ธ และนี่คือ Quicksort เช่นเดียวกับการจัดเรียงแทรกและฟอง เรียงลำดับ Quicksort เป็นอัลกอริทึม การเรียงลำดับรายการหรืออาร์เรย์ของสิ่งที่ สำหรับความเรียบง่ายสมมติว่าผู้ สิ่งที่เป็นเพียงจำนวนเต็ม แต่ รู้ว่า Quicksort ทำงานให้กับ มากกว่าเพียงตัวเลข Quickstart เป็นบิตที่ซับซ้อนมากขึ้น กว่าแทรกหรือฟอง แต่ก็ นอกจากนี้ยังมีประสิทธิภาพมากขึ้น ในกรณีส่วนใหญ่ รอสอง แต่เขาก็บอกว่า "มากที่สุด กรณี "ไม่ใช่" ทั้งหมด "? ที่น่าสนใจไม่ ไม่ได้ทุกกรณีเหมือนกัน ไม่ต้องกังวลเกี่ยวกับรายละเอียดนี้ถ้าคุณ ยังไม่เห็นสัญกรณ์โอใหญ่ แต่ quicksort คือ O (n squared) ขั้นตอนวิธีการ ที่เลวร้ายที่สุดเช่นเดียวกับ แทรกหรือฟองเรียง แต่ก็มักจะทำหน้าที่มากขึ้น เช่นอัลกอริธึมอนาล็อกเก่า ทำไม? เราจะได้รับกลับไปในภายหลังว่า แต่สำหรับตอนนี้ขอเพียงแค่เรียนรู้ วิธีการทำงานของ Quicksort 

จึงขอเดินผ่าน Quicksorting นี้ อาร์เรย์ของจำนวนเต็มจากที่เล็กที่สุด ที่ใหญ่ที่สุด ที่นี่เรามีจำนวนเต็ม 6, 5, 1, 3, 8, 4, 7, 9, และ 2 ครั้งแรกที่เราเลือกองค์ประกอบสุดท้ายของ อาร์เรย์นี้ - ในกรณีนี้สอง - และเรียกว่า "หมุน". ต่อไปเรา เริ่มต้นที่จะมองไปที่สองสิ่ง - หนึ่งดัชนีต่ำสุดที่ผมจะดู ว่าอยู่ทางด้านขวาของ ผนังและสองซ้ายสุด องค์ประกอบที่ฉันจะเรียกว่า "ปัจจุบัน องค์ประกอบ. "สิ่งที่เรากำลังจะทำคือ ดูทุกองค์ประกอบอื่น ๆ อื่น ๆ กว่าเดือยและใส่องค์ประกอบทั้งหมด มีขนาดเล็กกว่าที่จะหมุน ด้านซ้ายของผนังและทุกคน มีขนาดใหญ่กว่าที่จะหมุน ทางด้านขวาของผนัง แล้วในที่สุดเราจะวางหมุน ขวาบนผนังที่จะนำมันระหว่างที่ ตัวเลขทั้งหมดมีขนาดเล็กกว่ามัน และตัวเลขทั้งหมดที่มีขนาดใหญ่ 

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

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

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

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

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

วิธีการนี​​้จะทำงานได้ดีถ้า ค่าของหัวใจได้รับการแต่งตั้งเป็น ประมาณกลาง ช่วงของค่ารายการ นี้จะหมายถึงว่าหลังจากที่เราย้าย องค์ประกอบรอบ ๆ มีเป็นจำนวนมากเกี่ยวกับ องค์ประกอบทางด้านซ้ายของเดือย เท่าที่มีไปทางขวา และธรรมชาติแบ่งและพิชิตของ ขั้นตอนวิธี quicksort จะมาแล้ว ประโยชน์อย่างเต็มที่จาก นี้จะสร้างรันไทม์ของ O (n log n) n เพราะเราต้องทำ n ลบ 1 การเปรียบเทียบในแต่ละรุ่นและเข้าสู่ระบบ n เพราะเรามีการแบ่งรายการ log n ครั้ง อย่างไรก็ตามในกรณีที่เลวร้ายที่สุดนี้ ขั้นตอนวิธีการสามารถจริงจะ O (n squared.) สมมติว่าในแต่ละรุ่น หมุนเกิดขึ้นเพียงเพื่อที่จะเป็น ที่มีขนาดเล็กหรือใหญ่ที่สุดของ ตัวเลขที่เรากำลังการเรียงลำดับ นี้จะหมายถึงรายการที่จะหมดสภาพ n ครั้งและการทำ n ลบ 1 เปรียบเทียบทุกครั้งเดียว ดังนั้น o n-squared 

วิธีการที่เราสามารถปรับปรุงวิธีการหรือไม่ วิธีการหนึ่งที่ดีในการปรับปรุงวิธีการที่ เพื่อลดความน่าจะเป็นที่ runtime เคยจริง o n-squared จำที่เลวร้ายที่สุดกรณีสถานการณ์นี้เลวร้ายที่สุด สามารถเกิดขึ้นได้เมื่อ หมุนเลือกอยู่เสมอสูงสุด หรือค่าต่ำสุดในอาร์เรย์ เพื่อให้แน่ใจว่านี้เป็นโอกาสน้อยที่จะเกิดขึ้น เราสามารถหาหมุนโดย การเลือกองค์ประกอบหลาย การค่ามัธยฐาน 

ชื่อของฉันคือมาร์ค Grozen สมิ ธ และนี่คือ CS50 

สำหรับความเรียบง่ายสมมติว่าผู้ สิ่งที่เป็นเพียงจำนวนเต็ม แต่ รู้ว่า Quicksert - Quicksert? ขอโทษ 

ที่นี่เรามีจำนวนเต็ม 6, 5, 1, 3, 8, 4, 9 

ลำโพง 1: จริงเหรอ? 

ลำโพง 2: อย่าหยุดเพียงแค่นั้น 

ลำโพง 1: จริงเหรอ?