ทั้งเทคนิคการเรียงลำดับการเรียงอย่างรวดเร็วและการเรียงแบบผสานถูกสร้างขึ้นบนวิธีการแบ่งและพิชิตซึ่งชุดขององค์ประกอบจะถูกแยกส่วนแล้วรวมเข้าด้วยกันหลังจากการจัดเรียงใหม่ การเรียงแบบด่วนมักต้องการการเปรียบเทียบมากกว่าการรวมแบบเรียงเพื่อเรียงลำดับชุดองค์ประกอบขนาดใหญ่
แผนภูมิเปรียบเทียบ
พื้นฐานสำหรับการเปรียบเทียบ | จัดเรียงด่วน | เรียงลำดับการผสาน |
---|---|---|
การแบ่งพาร์ติชันขององค์ประกอบในอาร์เรย์ | การแยกรายการองค์ประกอบไม่จำเป็นต้องแบ่งออกเป็นครึ่ง | อาร์เรย์จะแบ่งออกเป็นครึ่งหนึ่งเสมอ (n / 2) |
ความซับซ้อนของกรณีที่แย่ที่สุด | O (N2) | O (n log n) |
ทำงานได้ดีบน | อาร์เรย์ที่เล็กกว่า | ทำงานได้ดีในอาเรย์ทุกประเภท |
ความเร็ว | เร็วกว่าอัลกอริธึมการเรียงลำดับอื่นสำหรับชุดข้อมูลขนาดเล็ก | ความเร็วคงที่ในชุดข้อมูลทุกประเภท |
ข้อกำหนดเกี่ยวกับพื้นที่เก็บข้อมูลเพิ่มเติม | น้อยกว่า | มากกว่า |
อย่างมีประสิทธิภาพ | ไม่มีประสิทธิภาพสำหรับอาร์เรย์ขนาดใหญ่ | มีประสิทธิภาพมากกว่า. |
วิธีการเรียงลำดับ | ภายใน | ภายนอก |
นิยามของ Quick Sort
Quick sort ใช้อัลกอริธึมการเรียงลำดับอย่างแพร่หลายเนื่องจากรวดเร็วสำหรับอาร์เรย์สั้น ๆ ชุดขององค์ประกอบถูกแบ่งออกเป็นส่วน ๆ ซ้ำ ๆ จนกว่ามันจะเป็นไปไม่ได้ที่จะแบ่งมันต่อไป การเรียงลำดับด่วนเรียกอีกอย่างว่าการ เรียงลำดับการแลกเปลี่ยนพาร์ติชัน มันใช้องค์ประกอบที่สำคัญ (รู้จักกันในนามเดือย) สำหรับการแบ่งองค์ประกอบ หนึ่งพาร์ติชันประกอบด้วยองค์ประกอบเหล่านั้นที่มีขนาดเล็กกว่าองค์ประกอบสำคัญ อีกพาร์ติชันประกอบด้วยองค์ประกอบเหล่านั้นที่มากกว่าองค์ประกอบสำคัญ องค์ประกอบถูกเรียงลำดับแบบวนซ้ำ
สมมติว่า A คืออาร์เรย์ A [1], A [2], A [3], …… .., A [n] ของจำนวน n ที่ต้องเรียงลำดับ อัลกอริทึมการเรียงลำดับอย่างรวดเร็วประกอบด้วยขั้นตอนต่อไปนี้
- องค์ประกอบแรกหรือองค์ประกอบสุ่มใด ๆ ที่เลือกเป็นกุญแจสมมติว่า key = A (1)
- ตัวชี้“ ต่ำ” ถูกวางไว้ที่ตำแหน่งที่สองและตัวชี้“ ขึ้น” จะถูกวางตำแหน่งที่องค์ประกอบสุดท้ายของอาเรย์นั่นคือ low = 2 และ up = n;
- อย่างต่อเนื่องเพิ่มตัวชี้“ ต่ำ” โดยหนึ่งตำแหน่งจนกระทั่ง (ปุ่ม [ต่ำ]>)
- อย่างต่อเนื่องลดตัวชี้“ ขึ้น” โดยหนึ่งตำแหน่งจนกระทั่ง (ปุ่ม [ขึ้น] <=)
- ถ้าสูงกว่าการแลกเปลี่ยนที่ต่ำ A [ต่ำ] กับ A [ขึ้น]
- ทำซ้ำขั้นตอนที่ 3, 4 และ 5 จนกระทั่งเงื่อนไขในขั้นตอนที่ 5 ล้มเหลว (เช่นขึ้น <= ต่ำ) จากนั้นแลกเปลี่ยน A [ขึ้น] ด้วยปุ่ม
- หากองค์ประกอบด้านซ้ายของคีย์นั้นเล็กกว่าคีย์และองค์ประกอบด้านขวาของคีย์นั้นใหญ่กว่าคีย์ดังนั้นอาร์เรย์จะถูกแบ่งพาร์ติชันออกเป็นสองอาร์เรย์ย่อย
- ขั้นตอนข้างต้นถูกนำไปใช้ซ้ำกับระบบย่อยจนกระทั่งอาร์เรย์ทั้งหมดถูกเรียงลำดับ
ข้อดีและข้อเสีย
มันมีพฤติกรรมกรณีที่ดีโดยเฉลี่ย ความซับซ้อนของเวลาในการจัดเรียงอย่างรวดเร็วนั้นดีมากซึ่งเร็วกว่าอัลกอริธึมเช่นการเรียงลำดับฟองการเรียงการแทรกและการเรียงลำดับการเลือก อย่างไรก็ตามมันมีความซับซ้อนและเกิดซ้ำมากนั่นคือเหตุผลที่มันไม่เหมาะสำหรับอาร์เรย์ขนาดใหญ่
ความหมายของการเรียงลำดับการผสาน
Merge sort เป็นอัลกอริธึมภายนอกซึ่งขึ้นอยู่กับกลยุทธ์การแบ่งและพิชิต องค์ประกอบจะถูกแบ่งออกเป็นอาร์เรย์ย่อย (n / 2) อีกครั้งและอีกครั้งจนกว่าจะมีเพียงหนึ่งองค์ประกอบที่เหลือซึ่งลดเวลาการเรียงลำดับอย่างมีนัยสำคัญ จะใช้ที่เก็บข้อมูลเพิ่มเติมสำหรับการจัดเก็บอาร์เรย์เสริม การเรียงแบบผสานใช้สามอาร์เรย์ที่สองถูกใช้สำหรับการจัดเก็บแต่ละครึ่งและอันที่สามถูกใช้เพื่อเก็บรายการที่เรียงลำดับสุดท้าย แต่ละอาร์เรย์จะถูกจัดเรียงแบบวนซ้ำ ในที่สุดอาร์เรย์ย่อยจะถูกรวมเข้าด้วยกันเพื่อทำให้เป็นขนาดองค์ประกอบของอาร์เรย์ รายการจะแบ่งออกเป็นเพียงครึ่งหนึ่ง (n / 2) ที่แตกต่างกันไปเป็นการจัดเรียงอย่างรวดเร็ว
ให้ A เป็นอาร์เรย์ของจำนวนองค์ประกอบที่จะเรียง A [1], A [2], ………, A [n] การจัดเรียงผสานทำตามขั้นตอนที่กำหนด
- แบ่งอาร์เรย์ A ออกเป็นอาร์เรย์ย่อยประมาณ n / 2 เรียง 2 ซึ่งหมายความว่าองค์ประกอบใน (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]), (A [n-1], A [n]) อาร์เรย์ย่อยจะต้องเรียงตามลำดับ
- รวมคู่แต่ละคู่เพื่อรับรายการ subarrays เรียงขนาด 4; องค์ประกอบใน subarrays ยังเรียงตามลำดับ (A [1], A [2], A [3], A [4]), ……, (A [k-1], A [k], A [k + 1], A [k + 2]), ……., (A [n-3], A [n-2], A [n-1], [[n])
- ขั้นตอนที่ 2 จะดำเนินการซ้ำ ๆ จนกว่าจะมีอาร์เรย์ที่เรียงลำดับขนาดเดียวเท่านั้น
ข้อดีและข้อเสีย
อัลกอริทึมการจัดเรียงผสานดำเนินการในลักษณะเดียวกันและแม่นยำโดยไม่คำนึงถึงจำนวนองค์ประกอบที่เกี่ยวข้องในการเรียงลำดับ มันทำงานได้ดีแม้กับชุดข้อมูลขนาดใหญ่ อย่างไรก็ตามมันใช้หน่วยความจำส่วนใหญ่
ความแตกต่างที่สำคัญระหว่างการเรียงลำดับแบบด่วนและการเรียงแบบผสาน
- ในการจัดเรียงผสานอาร์เรย์จะต้องแยกเป็นสองส่วนเท่านั้น (เช่น n / 2) ในการเรียงลำดับอย่างรวดเร็วไม่มีการบังคับให้แบ่งรายการออกเป็นองค์ประกอบที่เท่ากัน
- ความซับซ้อนของกรณีที่เลวร้ายที่สุดของการจัดเรียงอย่างรวดเร็วคือ O (n2) เนื่องจากมีการเปรียบเทียบมากขึ้นในสภาพที่เลวร้ายที่สุด ในทางตรงกันข้ามการเรียงลำดับการผสานมีตัวพิมพ์เล็กและตัวพิมพ์ใหญ่ที่สุดที่เหมือนกันนั่นคือ O (n log n)
- การเรียงลำดับการผสานสามารถทำงานได้ดีบนชุดข้อมูลทุกประเภทไม่ว่าจะใหญ่หรือเล็ก ในทางตรงกันข้ามการเรียงลำดับอย่างรวดเร็วไม่สามารถทำงานได้ดีกับชุดข้อมูลขนาดใหญ่
- การเรียงลำดับด่วนจะเร็วกว่าการรวมการเรียงในบางกรณีเช่นชุดข้อมูลขนาดเล็ก
- การจัดเรียงเวียนต้องใช้พื้นที่หน่วยความจำเพิ่มเติมเพื่อจัดเก็บอาร์เรย์เสริม ในทางตรงกันข้ามการจัดเรียงอย่างรวดเร็วไม่ต้องใช้พื้นที่มากสำหรับการจัดเก็บเพิ่มเติม
- การเรียงลำดับผสานมีประสิทธิภาพมากกว่าการเรียงแบบรวดเร็ว
- การจัดเรียงอย่างรวดเร็วเป็นวิธีการเรียงลำดับภายในซึ่งข้อมูลที่จะจัดเรียงนั้นจะถูกปรับทีละครั้งในหน่วยความจำหลัก ในทางกลับกันการผสานการจัดเรียงเป็นวิธีการเรียงลำดับภายนอกซึ่งข้อมูลที่จะถูกจัดเรียงไม่สามารถรองรับได้ในหน่วยความจำในเวลาเดียวกันและบางส่วนจะต้องเก็บไว้ในหน่วยความจำเสริม
ข้อสรุป
การเรียงลำดับแบบเร็วเป็นกรณีที่เร็วกว่า แต่ไม่มีประสิทธิภาพในบางสถานการณ์และยังทำการเปรียบเทียบจำนวนมากเมื่อเปรียบเทียบกับการจัดเรียงแบบผสาน แม้ว่าการเรียงแบบผสานต้องใช้การเปรียบเทียบน้อยกว่า แต่ต้องการพื้นที่หน่วยความจำเพิ่มเติมเป็น 0 (n) สำหรับการเก็บอาร์เรย์พิเศษในขณะที่การเรียงแบบด่วนต้องการพื้นที่ของ O (log n)