ฮีปซอร์ต

(เปลี่ยนทางจาก ฮีพซอร์ต)

ในทางวิทยาการคอมพิวเตอร์ ฮีปซอร์ต หรือ อัลกอริทึมจัดเรียงแบบฮีป (อังกฤษ: heapsort) คือ อัลกอริทึมจัดเรียงที่มีพื้นฐานคือการเปรียบเทียบสมาชิกในอาร์เรย์ (array) โดยใช้โครงสร้างข้อมูลแบบฮีป (heap) เป็นหลักในการจัดเรียง[1]

ฮีปซอร์ต
Sorting heapsort anim.gif
ในสเตปแรกของการรันฮีปซอร์ต สมาชิกของอาร์เรย์จะถูกจัดเรียงให้เป็นโครงสร้างข้อมูลฮีป เรียกว่า การสร้างฮีป (heapify) เมื่อสร้างเป็นฮีปแล้ว ฮีปซอร์ตจะทำการสลับสมาชิกตัวที่อยู่หน้าสุด (เป็นโหนดด้านบนสุดของฮีป) และตัวล่างสุดของฮีป (ตัวที่อยู่หลังสุดของอาร์เรย์ในส่วนที่ยังไม่ได้จัดเรียง (unsorted part of the array)) ฮีปซอร์ตจะทำแบบนี้ จนกระทั่งอาร์เรย์เรียงจากน้อยไปมากอย่างสมบูรณ์
ประเภทอัลกอริทึมจัดเรียง
โครงสร้างข้อมูลแถวลำดับ
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด (distinct keys)
or (equal keys)
ประสิทธิภาพเมื่อเกิดกรณีทั่วไป
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด total auxiliary

ฮีปซอร์ตและโครงสร้างข้อมูลฮีป[2] คิดค้นขึ้นโดย เจ. ดับเบิลยู. เจ. วิลเลียมส์ ในปี ค.ศ. 1964[3]

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

เปรียบเทียบ heapsort กับ merge sort และ quicksortแก้ไข

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

โดยทั่วไปในทางปฏิบัติแล้ว heapsort จะช้ากว่า merge sort และ quicksort และถือเป็นอัลกอริทึมที่ไม่เสถียร (unstable algorithm) กล่าวคือ heapsort จะไม่ทำการรักษาตำแหน่งของเรคคอร์ดในอาร์เรย์ในกรณีที่ตำแหน่งสองตำแหน่งขึ้นไปนั้น มีค่า (value/key) ที่เท่ากัน[5]

อย่างไรก็ดี heapsort ไม่จำเป็นต้องใช้พื้นที่ในการเก็บข้อมูล (memory space) เหมือนกับ merge sort และเวลารันในกรณีที่แย่ที่สุดของ heapsort คือ Θ(nlogn) ทำให้เร็วกว่า quicksort ซึ่งมีเวลารันในกรณีที่แย่ที่สุดคือ O(n2)

ตัวอย่างแก้ไข

ให้ { 6, 5, 3, 1, 8, 7, 2, 4 } เป็นลิสต์ เราต้องการเรียงสมาชิกของลิสต์นี้จากน้อยที่สุดไปมากที่สุด[6]

 
ตัวอย่างฮีปซอร์ต

การสร้างฮีปแก้ไข

ฮีป สมาชิกใหม่ใส่เข้าไปในฮีป สลับ (swap) สมาชิก
NULL (ว่างเปล่า) 6
6 5
6, 5 3
6, 5, 3 1
6, 5, 3, 1 8
6, 5, 3, 1, 8 5, 8
6, 8, 3, 1, 5 6, 8
8, 6, 3, 1, 5 7
8, 6, 3, 1, 5, 7 3, 7
8, 6, 7, 1, 5, 3 2
8, 6, 7, 1, 5, 3, 2 4
8, 6, 7, 1, 5, 3, 2, 4 1, 4
8, 6, 7, 4, 5, 3, 2, 1

การเรียงแก้ไข

ฮีป สลับ (swap) สมาชิก ลบ (delete) สมาชิก อาร์เรย์ที่จัดเรียงแล้ว ข้อมูล
8, 6, 7, 4, 5, 3, 2, 1 8, 1 สลับ 8 และ 1 เพื่อลบ 8 จาก heap
1, 6, 7, 4, 5, 3, 2, 8 8 ลบ 8 จาก heap และเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
1, 6, 7, 4, 5, 3, 2 1, 7 8 สลับ 1 และ 7 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
7, 6, 1, 4, 5, 3, 2 1, 3 8 สลับ 1 และ 3 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
7, 6, 3, 4, 5, 1, 2 7, 2 8 สลับ 7 และ 2 เพื่อลบ 7 จาก heap
2, 6, 3, 4, 5, 1, 7 7 8 ลบ 7 จาก heap และเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
2, 6, 3, 4, 5, 1 2, 6 7, 8 สลับ 2 และ 6 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
6, 2, 3, 4, 5, 1 2, 5 7, 8 สลับ 2 และ 5 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
6, 5, 3, 4, 2, 1 6, 1 7, 8 สลับ 6 และ 1 เพื่อลบ 6 จาก heap
1, 5, 3, 4, 2, 6 6 7, 8 ลบ 6 จาก heap และเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
1, 5, 3, 4, 2 1, 5 6, 7, 8 สลับ 1 และ 5 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
5, 1, 3, 4, 2 1, 4 6, 7, 8 สลับ 1 และ 4 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
5, 4, 3, 1, 2 5, 2 6, 7, 8 สลับ 5 และ 2 เพื่อลบ 5 จาก heap
2, 4, 3, 1, 5 5 6, 7, 8 ลบ 5 จาก heap และเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
2, 4, 3, 1 2, 4 5, 6, 7, 8 สลับ 2 และ 4 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
4, 2, 3, 1 4, 1 5, 6, 7, 8 สลับ 4 และ 1 เพื่อลบ 4 จาก heap
1, 2, 3, 4 4 5, 6, 7, 8 ลบ 4 จาก heap และเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
1, 2, 3 1, 3 4, 5, 6, 7, 8 สลับ 1 และ 3 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
3, 2, 1 3, 1 4, 5, 6, 7, 8 สลับ 3 และ 1 เพื่อลบ 3 จาก heap
1, 2, 3 3 4, 5, 6, 7, 8 ลบ 3 จาก heap และเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
1, 2 1, 2 3, 4, 5, 6, 7, 8 สลับ 1 และ 2 เนื่องจากพวกมันเรียงลำดับอย่างไม่ถูกต้องในฮีป
2, 1 2, 1 3, 4, 5, 6, 7, 8 สลับ 2 และ 1 เพื่อลบ 2 จาก heap
1, 2 2 3, 4, 5, 6, 7, 8 ลบ 2 จาก heap และเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
1 1 2, 3, 4, 5, 6, 7, 8 ลบ 1 จาก heap และเพิ่มไปยังอาร์เรย์ที่เรียงแล้ว
1, 2, 3, 4, 5, 6, 7, 8 เรียงสมบูรณ์

อ้างอิงแก้ไข

  1. Heapsort (2021). GeeksforGeeks. https://www.geeksforgeeks.org/heap-sort/
  2. Brass, Peter (2008). Advanced Data Structures. Cambridge University Press. p. 209. ISBN 978-0-521-88037-4.
  3. Williams 1964
  4. CS241: Data Structures & Algorithms II (cpp.edu) (สืบค้นเมื่อวันที่ 3 มกราคม ค.ศ. 2022)
  5. Stable Sorting Algorithms | Baeldung on Computer Science
  6. László Szabó. Algoritmusok (Budapest, 2016). Eötvös Lóránd University. ลิงก์: https://www.inf.elte.hu/dstore/document/329/szabo_laszlo_alg2016.pdf