การเรียงลำดับเพชันส์

ภาพรวม

ชื่อของอัลกอริทึมมาจากรูปแบบที่เรียบง่ายของเกมการ์ดการถอดไพ่ เกมนี้เริ่มต้นด้วยไพ่สับไพ่ การ์ดเหล่านี้จะถูกแจกเป็นลำดับกองบนโต๊ะตามกฎต่อไปนี้
1. เริ่มแรกไม่มีกองไพ่ ไพ่ใบแรกที่แจกให้เป็นกองใหม่ประกอบด้วยไพ่ใบเดียว
2. การ์ดใบต่อ ๆ ไปจะอยู่บนกองที่มีอยู่ด้านซ้ายสุดซึ่งการ์ดด้านบนมีค่ามากกว่าหรือเท่ากับค่าของบัตรใหม่หรือด้านขวาของกองไพ่ทั้งหมดที่มีอยู่แล้วจึงเป็นกองใหม่
3. เมื่อไม่มีไพ่เหลืออยู่อีกต่อไปเกมจะสิ้นสุดลง
เกมการ์ดใบนี้ถูกเปลี่ยนเป็นอัลกอริทึมการจัดเรียงแบบสองเฟสดังนี้ ให้อาร์เรย์ขององค์ประกอบ n จากโดเมนทั้งหมด ให้พิจารณาอาร์เรย์นี้เป็นชุดของการ์ดและจำลอง patience sorting ในการเรียงลำดับเกม เมื่อเกมเสร็จสิ้นแล้วให้กู้คืนลำดับที่เรียงลำดับโดยการเลือกการ์ดที่มองเห็นได้น้อย ๆ กล่าวคือให้ทำการรวม k วิธี ของ p กอง ซึ่งแต่ละอันจะเรียงลำดับกันภายใน

การวิเคราะห์

ขั้นตอนแรกของ patience sort การจำลองเกมการ์ดสามารถใช้เพื่อเปรียบเทียบ O (n log n) ในกรณีที่เลวร้ายที่สุดสำหรับอาร์เรย์ข้อมูล n-element: จะมีกอง n ส่วนใหญ่และโดยการก่อสร้างด้านบน ไพ่ของกองแบบฟอร์มลำดับที่เพิ่มขึ้นจากซ้ายไปขวาดังนั้นกองที่ต้องการสามารถพบได้โดยการค้นหาแบบไบนารี ระยะที่สองการรวมกองสามารถทำได้ในเวลา O (n log n) ด้วยการใช้การเข้าคิวลำดับความสำคัญ
เมื่อข้อมูลอินพุตมีข้อมูล "ทำงาน" ตามธรรมชาติเช่นโครงสร้างย่อยที่ไม่ลดลงประสิทธิภาพจะดีขึ้นอย่างเห็นได้ชัด ในความเป็นจริงเมื่ออาร์เรย์อินพุตถูกจัดเรียงเรียบร้อยแล้วค่าทั้งหมดจะเป็นแบบกองเดียวและทั้งสองเฟสจะทำงานในเวลา O (n) ความซับซ้อนของกรณีโดยเฉลี่ยยังคงเป็น O (n log n): ลำดับสุ่มของค่าใด ๆ จะให้จำนวน O (√n) ที่คาดหวังไว้, ซึ่งใช้เวลา O (n log √n) = O (n log n) เวลาในการผลิตและผสาน
การประเมินผลการปฏิบัติงานของ patience sort คือ Chandramouli และ Goldstein ผู้แสดงให้เห็นว่า naive version ช้ากว่า quicksort  เป็นเวลาประมาณสิบถึงยี่สิบนาที quicksort บนปัญหามาตรฐานของพวกเขา พวกเขาให้เหตุผลว่าเป็นการวิจัยเชิงปริมาณเพียงเล็กน้อยของ patience sort และพัฒนาการเพิ่มประสิทธิภาพหลายอย่างซึ่งจะทำให้ประสิทธิภาพการทำงานของมันอยู่ในระดับที่สองของ quicksort
ถ้าค่าของการ์ดอยู่ในช่วง 1,....,n, มีการใช้งานที่มีประสิทธิภาพด้วย  O (n log log n) เวลาทำงานที่เลวร้ายที่สุด (worst-case) สำหรับการใส่ไพ่ลงกองโดยใช้ต้นไม้ Van Emde Boas

ความสัมพันธ์กับปัญหาอื่นธ์

Patience sorting มีความเกี่ยวข้องกับเกมไพ่ที่เรียกว่าเกม Floyd เกมนี้มีความคล้ายคลึงกับเกมที่ร่างไว้ก่อนหน้านี้:
1. บัตรแรกที่แจกให้เป็นกองใหม่ประกอบด้วยการ์ดใบเดียว
2. การ์ดใบใดก็ตามที่มีอยู่จะถูกวางลงบนกองที่มีอยู่ซึ่งการ์ดด้านบนมีค่าไม่เกินมูลค่าของบัตรใหม่หรือด้านขวาของไพ่ทั้งหมดที่มีอยู่แล้วจึงเป็นกองใหม่
3. เมื่อไม่มีไพ่เหลืออยู่อีกแล้วเกมจะสิ้นสุดลง
เป้าหมายของเกมคือการจบด้วยกองน้อยที่สุดเท่าที่จะเป็นไปได้ ความแตกต่างกับอัลกอริธึม Patience sorting คือไม่จำเป็นต้องวางการ์ดใบใหม่ไว้ที่กองซ้ายสุดซึ่งจะได้รับอนุญาต การเรียงลำดับความอดทนถือเป็นกลยุทธ์ greedy ในการเล่นเกมนี้
Aldous และ Diaconis แนะนำให้กำหนดกอง 9 หรือน้อยกว่าเป็นผลลัพธ์ที่ดีสำหรับ n = 52 ซึ่งเกิดขึ้นได้ด้วยความน่าจะเป็นประมาณ 5%

อัลกอริทึมสำหรับการหาลำดับชั้นที่ยาวที่สุดที่เพิ่มขึ้น

ขั้นแรกให้รันอัลกอริทึมการเรียงลำดับตามที่อธิบายไว้ด้านบน จำนวนกองเป็นความยาวของบันไดที่ยาวที่สุด เมื่อใดก็ตามที่มีการวางไพ่ขึ้นด้านบนของกองให้วางตัวชี้กลับไปที่ด้านบนของไพ่ในกองก่อนหน้านี้ (ที่โดยสมมติฐานมีค่าต่ำกว่าการ์ดใบใหม่มี) ในตอนท้ายให้ทำตามตัวชี้ด้านหลังจากด้านบนของไพ่ในกองสุดท้ายเพื่อกู้คืนความยาวที่ลดลงของความยาวที่ยาวที่สุด ย้อนกลับของมันคือคำตอบของอัลกอริธึมย่อยที่เพิ่มขึ้นที่ยาวที่สุด
S. Bespamyatnikh และ M. Segal ให้คำอธิบายเกี่ยวกับการใช้อัลกอริธึมที่มีประสิทธิภาพโดยไม่ก่อให้เกิดค่าใช้จ่ายเพิ่มเติมในการจัดเรียง (เนื่องจากการจัดเก็บข้อมูลการสร้างและการข้ามผ่านแบบย้อนหลังต้องใช้เวลาและพื้นที่เชิงเส้น) พวกเขายังแสดงวิธีการรายงานข้อมูลที่ยาวที่สุดทั้งหมดที่เพิ่มขึ้นจากโครงสร้างข้อมูลผลลัพธ์ที่เหมือนกัน

Python

1 import bisect, heapq 2  3 def sort(seq): 4     piles = [] 5     for x in seq: 6         new_pile = [x] 7         i = bisect.bisect_left(piles, new_pile) 8         if i != len(piles): 9             piles[i].insert(0, x)10         else:11             piles.append(new_pile)12     print "longest increasing subsequence has length =", len(piles)13 14     # priority queue allows us to retrieve least pile efficiently15     for i in xrange(len(seq)):16         small_pile = piles[0]17         seq[i] = small_pile.pop(0)18         if small_pile:19             heapq.heapreplace(piles, small_pile)20         else:21             heapq.heappop(piles)22     assert not piles23 24 foo = [4, 65, 2, 4, -31, 0, 99, 1, 83, 782, 1]25 sort(foo)26 print foo

ประวัติ

Patience sorting ได้รับการตั้งชื่อโดย C. L. Mallows ผู้ที่คิดค้นสิ่งประดิษฐ์ให้กับ A.S.C. Ross ในต้นปี 1960 ตามที่ Aldous และ Diaconis Patience sorting เป็นที่รู้จักเป็นอันดับแรกในฐานะอัลกอริทึมในการคำนวณความยาวที่ยาวที่สุดโดย Hammersley และโดย A.S.C. Ross และ Robert W. Floyd เป็นขั้นตอนการจัดเรียง การวิเคราะห์ครั้งแรกทำโดย Mallows เกม Floyd ได้รับการพัฒนาโดย Floyd ในการติดต่อกับ Donald Knuth