แนะนำ, 2024

ตัวเลือกของบรรณาธิการ

ความแตกต่างระหว่าง Quick Sort และ Merge Sort

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

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

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

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

นิยามของ Quick Sort

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

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

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

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

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

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

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

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

  1. แบ่งอาร์เรย์ A ออกเป็นอาร์เรย์ย่อยประมาณ n / 2 เรียง 2 ซึ่งหมายความว่าองค์ประกอบใน (A [1], A [2]), (A [3], A [4]), (A [ k], A [k + 1]), (A [n-1], A [n]) อาร์เรย์ย่อยจะต้องเรียงตามลำดับ
  2. รวมคู่แต่ละคู่เพื่อรับรายการ 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])
  3. ขั้นตอนที่ 2 จะดำเนินการซ้ำ ๆ จนกว่าจะมีอาร์เรย์ที่เรียงลำดับขนาดเดียวเท่านั้น

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

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

ความแตกต่างที่สำคัญระหว่างการเรียงลำดับแบบด่วนและการเรียงแบบผสาน

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

ข้อสรุป

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

Top