การเรียงลำดับคี่–คู่
Example of odd-even transposition sort sorting a list of random numbers. | |
ประเภท | Sorting algorithm |
---|---|
โครงสร้างข้อมูล | Array |
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | |
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด | |
ปริมาณความต้องการพื้นที่เมื่อเกิดกรณีแย่ที่สุด | |
ในทางด้านการคำนวณ การจัดเรียงแบบคี่-คู่ (odd–even sort, odd–even transposition sort) ยังเป็นที่รู้จักกันในชื่อ brick sort เป็นความสัมพันธ์แบบง่าย ๆ ในการจัดเรียงลำดับข้อมูลแบบขั้นตอนวิธีการ (Sorting Algorithm) เดิมทีถูกพัฒนาเพื่อใช้สำหรับตัวประมวลผลแบบขนาน (parallel processors) กับการเชื่อมต่อในระดับท้องถิ่น (Local) มันเป็นการเรียงลำดับแบบเปรียบเทียบที่มีลักษณะคล้ายกับการเรียงลำดับข้อมูลแบบฟองสบู่ (Bubble sort) ซึ่งมีลักษณะหลายอย่างที่มีความคล้ายกัน โดยมีฟังก์ชันการทำงานเปรียบเทียบจำนวนคี่/คู่ ทั้งหมดที่อยู่ติดกันเข้าจับคู่กันของสมาชิก (Elements) ในรายการ และถ้าการจับคู่อยู่ในลำดับที่ไม่ถูกต้อง (ในครั้งแรกจะขนาดใหญ่กว่าครั้งที่สอง) สมาชิกจะทำการสลับที่กัน ขั้นตอนต่อไปทำซ้ำโดนดูจากสมาชิกที่ติดกัน จากนั้นจะสลับระหว่างขั้นตอนคี่/คู่ และ คู่/คี่ จนกว่ารายการจะถูกจัดเรียงลำดับทั้งหมด
Class | การจัดเรียงลำดับข้อมูลแบบขั้นตอนวิธีการ |
---|---|
Data structure | อาเรย์ |
Worst-case performance | O(n^2) |
Best-case performance | O(n) |
Worst-case space complexity | O(1) |
การเรียงลำดับบนอาร์เรย์ของตัวประมวลผล
[แก้]ในตัวประมวลผลแบบขนาน กับค่าหนึ่งค่าต่อหนึ่งตัวประมวลผล และมีเพียงการเชื่อมต่อแบบเพื่อนบ้านทางซ้ายขวาเท่านั้นโปรเซสเซอร์ทั้งหมดพร้อมกันทำการเปรียบเทียบกับเพื่อนบ้านของพวกเขาสลับกันระหว่างการจับคู่แบบคี่และแม้แต่คู่กัน
อัลกอริธึมนี้ถูกนำเสนอครั้งแรกและแสดงให้เห็นว่ามีประสิทธิภาพในตัวประมวลผล โดย Habermann ในปี พ.ศ. 2515 อัลกอริธึมจะขยายได้อย่างมีประสิทธิภาพต่อบางกรณีที่มีหลายรายการต่อหนี่งโปรเซสเซอร์ ในอัลกอริธึมการแยกส่วนของจำนวนคี่และคู่ใน Baudet - Stevenson แต่ละตัวประมวลผลทำการเรียงข้อมูลรายการย่อยของตัวมันเองในแต่ละขั้นตอน ใช้อัลกอริทึมการจัดเรียงที่มีประสิทธิภาพ และดำเนินการแยกการผสาน (merge splitting) หรือการขนย้ายแบบผสาน (Transposition-merge) มีการทำงานใกล้สมาชิกใกล้เคียง และมีการจับคู่กันแบบสลับระหว่างจำนวนคี่-คู่ และจำนวนคู่-คี่ ในแต่ละขั้นตอน Batcher's odd–even merge sort ขั้นตอนวิธีการเรียงลำดับที่เกี่ยวข้อง แต่มีประสิทธิภาพมากขึ้นคือ Batcher odd–even merge sort ใช้การเปรียบเทียบการดำเนินงานและการดำเนินการแบบสุ่มสมบูรณ์แบบ วิธี Batcher มีประสิทธิภาพในโปรเซสเซอร์แบบขนานที่มีการเชื่อมต่อในระยะไกล
ตัวอย่างโปรแกรม
[แก้]เมื่อใช้วิธีการเรียงลำดับคี่-คู่บนเครื่องที่มีหน่วยประมวลผลเดียว จะมีลักษณะของโปรแกรมคล้ายกับการเรียงลำดับแบบฟอง การทำงานของโปรแกรมนั้นเข้าใจได้ง่าย แต่โปรแกรมมีประสิทธิภาพในการทำงานไม่สูงนัก
โปรแกรมการเรียงลำดับคี่-คู่ที่มีการเรียงลำดับจากน้อยไปหามาก สามารถแสดงในภาษาไพทอนได้ดังตัวอย่างด้านล่าง
def oddEvenSort(list):
def swap(list, i, j):
temp = list[i];
list[i] = list[j];
list[j] = temp;
issorted = False;
while not issorted:
issorted = True;
""" odd phase """
for i in range (1,len(list)-1,2):
if list[i] > list[i+1]:
swap(list, i, i+1);
issorted = False;
""" even phase """
for i in range (0,len(list)-1,2):
if list[i] > list[i+1]:
swap(list, i, i+1);
issorted = False;
return list
การพิสูจน์ความถูกต้อง
[แก้]Unsorted
[แก้][3 2] [3 8] [5 6] [4 1] (oddPhase1)
2 [3 3] [8 5] [6 1] 4 (evenPhase2)
[2 3] [3 5] [8 1] [6 4] (oddPhase3)
2 [3 3] [5 1] [8 4] 6 (evenPhase4)
[2 3] [3 1] [5 4] [8 6] (oddPhase5)
2 [3 1] [3 4] [5 6] 8 (evenPhase6)
[2 1] [3 3] [4 5] [6 8] (oddPhase7)
1 [2 3] [3 4] [5 6] 8 (evenPhase8)
[1 2] [3 3] [4 5] [6 8] (oddPhase9)
Sorted
[แก้]ความซับซ้อนของเวลา (Time Complexity) : O(N2), N = จำนวนของสมาชิกที่อยู่ในอาเรย์
และมีความซับซ้อนของเวลาในกรณีที่ดีที่สุด : O(N)
พื้นที่เสริม (Auxiliary Space) : O(1) เหมือนกับ bubble sort และนี้ยังเป็นอัลกอริทึมแบบแทนที่
References
[แก้]1.Phillips, Malcolm. "Array Sorting". Homepages.ihug.co.nz. Archived from the original on 28 October 2011. Retrieved 3 August 2011.
2.N. Haberman (1972) "Parallel Neighbor Sort (or the Glory of the Induction Principle)," CMU Computer Science Report (available as Technical report AD-759 248, National Technical Information Service, US Department of Commerce, 5285 Port Royal Rd Sprigfield VA 22151).
3.Lakshmivarahan, S.; Dhall, S. K. & Miller, L. L. (1984), Alt, Franz L. & Yovits, Marshall C., eds., "Parallel Sorting Algorithms", Advances in computers, Academic Press, 23: 295–351, ISBN 978-0-12-012123-6
4.Sedgewick, Robert (2003). Algorithms in Java, Parts 1-4 (3rd ed.). Addison-Wesley Professional. pp. 454–464. ISBN 978-0-201-36120-9.
5.Kent, Allen; Williams, James G. (1993). Encyclopedia of Computer Science and Technology: Supplement 14. CRC Press. pp. 33–38. ISBN 978-0-8247-2282-1.
6."Five Lectures on CA" (PDF). Liinwww.ira.uka.de. Retrieved 2017-07-30.
7.Lang, Hans Werner. "The 0-1-principle". Iti.fh-flensburg.de. Retrieved 30 July 2017.
8."Distributed Sorting" (PDF). Net.t-labs.tu-berlin.de. Retrieved 2017-07-30.