เนื้อหา

• แผนภูมิเปรียบเทียบ
• นิยามของ Quick Sort
• ความหมายของการเรียงลำดับผสาน
• ข้อสรุป

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

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

1. 1. แผนภูมิเปรียบเทียบ
   2. คำนิยาม
   3. ความแตกต่างที่สำคัญ
   4. ข้อสรุป

แผนภูมิเปรียบเทียบ

พื้นฐานสำหรับการเปรียบเทียบ	จัดเรียงด่วน	เรียงลำดับการผสาน
การแบ่งองค์ประกอบในอาร์เรย์	การแยกรายการองค์ประกอบไม่จำเป็นต้องแบ่งออกเป็นครึ่ง	Array จะแบ่งออกเป็นครึ่งเสมอ (n / 2)
ความซับซ้อนของกรณีที่แย่ที่สุด	บน2)	O (n log n)
ทำงานได้ดีบน	อาร์เรย์ที่เล็กกว่า	ทำงานได้ดีในอาเรย์ทุกประเภท
ความเร็ว	เร็วกว่าอัลกอริธึมการเรียงลำดับอื่นสำหรับชุดข้อมูลขนาดเล็ก	ความเร็วคงที่ในชุดข้อมูลทุกประเภท
ข้อกำหนดเกี่ยวกับพื้นที่เก็บข้อมูลเพิ่มเติม	น้อยกว่า	มากกว่า
อย่างมีประสิทธิภาพ	ไม่มีประสิทธิภาพสำหรับอาร์เรย์ขนาดใหญ่	มีประสิทธิภาพมากกว่า.
วิธีการเรียงลำดับ	ภายใน	ภายนอก

นิยามของ Quick Sort

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

สมมติว่า A คืออาร์เรย์ A, A, A, …… .. , A ของจำนวน n ที่ต้องเรียงลำดับ อัลกอริทึมการเรียงลำดับอย่างรวดเร็วประกอบด้วยขั้นตอนต่อไปนี้

1. องค์ประกอบแรกหรือองค์ประกอบแบบสุ่มใด ๆ ที่เลือกเป็นกุญแจสมมติว่า key = A (1)
2. ตัวชี้“ ต่ำ” ถูกวางไว้ที่ตำแหน่งที่สองและตัวชี้“ ขึ้น” จะถูกวางตำแหน่งที่องค์ประกอบสุดท้ายของอาเรย์นั่นคือต่ำ = 2 และขึ้น = n;
3. อย่างต่อเนื่องเพิ่มตัวชี้“ ต่ำ” โดยหนึ่งตำแหน่งจนกระทั่งปุ่ม (A>)
4. อย่างต่อเนื่องลดตัวชี้“ ขึ้น” โดยหนึ่งตำแหน่งจนกระทั่ง (ปุ่ม <=)
5. ถ้าสูงกว่าการแลกเปลี่ยน A กับ A ต่ำ
6. ทำซ้ำขั้นตอนที่ 3,4 และ 5 จนกระทั่งเงื่อนไขในขั้นตอนที่ 5 ล้มเหลว (เช่นขึ้น <= ต่ำ) จากนั้นแลกเปลี่ยน A กับคีย์
7. หากองค์ประกอบด้านซ้ายของคีย์นั้นเล็กกว่าคีย์และองค์ประกอบด้านขวาของคีย์นั้นใหญ่กว่าคีย์ดังนั้นอาร์เรย์จะถูกแบ่งพาร์ติชันออกเป็นสองอาร์เรย์ย่อย
8. ขั้นตอนข้างต้นถูกนำไปใช้ซ้ำกับระบบย่อยจนกระทั่งอาร์เรย์ทั้งหมดถูกเรียงลำดับ

   

   
   

ข้อดีและข้อเสีย

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

ความหมายของการเรียงลำดับผสาน

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

ให้ A เป็นอาร์เรย์ของจำนวนองค์ประกอบที่จะเรียงลำดับ A, A, ……, A. การจัดเรียงผสานตามขั้นตอนที่กำหนด

1. แบ่งอาร์เรย์ A ออกเป็นอาร์เรย์ย่อยที่เรียงลำดับประมาณ n / 2 ด้วย 2 ซึ่งหมายความว่าองค์ประกอบใน (A, A), (A, A), (A, A), (A, A), (A, A) ต้องใช้อาร์เรย์ย่อย เรียงตามลำดับ
2. รวมคู่แต่ละคู่เพื่อรับรายการ subarrays เรียงขนาด 4; องค์ประกอบใน subarrays ยังเรียงตามลำดับ (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A)
3. ขั้นตอนที่ 2 จะดำเนินการซ้ำ ๆ จนกว่าจะมีอาร์เรย์ที่เรียงลำดับขนาดเดียวเท่านั้น

   

ข้อดีและข้อเสีย

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

1. ในการจัดเรียงผสานอาร์เรย์จะต้องแยกเป็นสองส่วนเท่านั้น (เช่น n / 2) ในการเรียงลำดับอย่างรวดเร็วไม่มีการบังคับให้แบ่งรายการออกเป็นองค์ประกอบที่เท่ากัน
2. ความซับซ้อนของกรณีที่แย่ที่สุดของการจัดเรียงอย่างรวดเร็วคือ O (n²) เนื่องจากต้องใช้การเปรียบเทียบมากขึ้นในสภาพที่เลวร้ายที่สุด ในทางตรงกันข้ามการจัดเรียงผสานมีตัวพิมพ์เล็กและใหญ่ที่สุดที่ซับซ้อนที่สุดนั่นคือ O (n log n)
3. การเรียงลำดับการผสานสามารถทำงานได้ดีกับชุดข้อมูลทุกประเภทไม่ว่าจะใหญ่หรือเล็ก ในทางตรงกันข้ามการเรียงลำดับอย่างรวดเร็วไม่สามารถทำงานได้ดีกับชุดข้อมูลขนาดใหญ่
4. การเรียงลำดับด่วนจะเร็วกว่าการรวมการเรียงในบางกรณีเช่นชุดข้อมูลขนาดเล็ก
5. การจัดเรียงเวียนต้องใช้พื้นที่หน่วยความจำเพิ่มเติมเพื่อจัดเก็บอาร์เรย์เสริม ในทางตรงกันข้ามการจัดเรียงอย่างรวดเร็วไม่จำเป็นต้องใช้พื้นที่มากสำหรับการจัดเก็บเพิ่มเติม
6. การเรียงลำดับผสานมีประสิทธิภาพมากกว่าการเรียงแบบรวดเร็ว
7. การจัดเรียงอย่างรวดเร็วเป็นวิธีการเรียงลำดับภายในซึ่งข้อมูลที่จะจัดเรียงนั้นจะถูกปรับทีละครั้งในหน่วยความจำหลัก ในทางกลับกันการผสานการจัดเรียงเป็นวิธีการเรียงลำดับภายนอกซึ่งข้อมูลที่จะถูกจัดเรียงไม่สามารถรองรับได้ในหน่วยความจำในเวลาเดียวกันและบางส่วนจะต้องเก็บไว้ในหน่วยความจำเสริม

ข้อสรุป

การเรียงลำดับแบบเร็วเป็นกรณีที่เร็วกว่า แต่ไม่มีประสิทธิภาพในบางสถานการณ์และยังทำการเปรียบเทียบจำนวนมากเมื่อเปรียบเทียบกับการจัดเรียงแบบผสาน แม้ว่าการเรียงแบบผสานต้องใช้การเปรียบเทียบน้อยกว่า แต่ต้องการพื้นที่หน่วยความจำเพิ่มเติมเป็น 0 (n) สำหรับการจัดเก็บอาร์เรย์พิเศษในขณะที่การเรียงแบบด่วนต้องการพื้นที่ของ O (log n)