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

ในด้านวิทยาศาสตร์คอมพิวเตอร์ patience sorting เป็นขั้นตอนวิธีการจัดเรียงที่ได้รับแรงบันดาลใจจากและตั้งชื่อตามการถอดไพ่ของเกมการ์ด ตัวแปรของอัลกอริทึมมีประสิทธิภาพคำนวณความยาวของบันไดที่ยาวที่สุดเพิ่มมาในอาร์เรย์ที่ระบุ

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

ประเภท	Sorting algorithm
โครงสร้างข้อมูล	Array
ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด	O(n log n)
ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด	O(n); occurs when the input is pre-sorted

ภาพรวม

ชื่อของอัลกอริทึมมาจากรูปแบบที่เรียบง่ายของเกมการ์ดการถอดไพ่ เกมนี้เริ่มต้นด้วยไพ่สับไพ่ การ์ดเหล่านี้จะถูกแจกเป็นลำดับกองบนโต๊ะตามกฎต่อไปนี้

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 ให้คำอธิบายเกี่ยวกับการใช้อัลกอริธึมที่มีประสิทธิภาพโดยไม่ก่อให้เกิดค่าใช้จ่ายเพิ่มเติมในการจัดเรียง (เนื่องจากการจัดเก็บข้อมูลการสร้างและการข้ามผ่านแบบย้อนหลังต้องใช้เวลาและพื้นที่เชิงเส้น) พวกเขายังแสดงวิธีการรายงานข้อมูลที่ยาวที่สุดทั้งหมดที่เพิ่มขึ้นจากโครงสร้างข้อมูลผลลัพธ์ที่เหมือนกัน

Coding

Python

import bisect, heapq

def sort(seq):
    piles = []
    for x in seq:
        new_pile = [x]
        i = bisect.bisect_left(piles, new_pile)
        if i != len(piles):
            piles[i].insert(0, x)
        else:
            piles.append(new_pile)
    print "longest increasing subsequence has length =", len(piles)

    # priority queue allows us to retrieve least pile efficiently
    for i in xrange(len(seq)):
        small_pile = piles[0]
        seq[i] = small_pile.pop(0)
        if small_pile:
            heapq.heapreplace(piles, small_pile)
        else:
            heapq.heappop(piles)
    assert not piles

foo = [4, 65, 2, 4, -31, 0, 99, 1, 83, 782, 1]
sort(foo)
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

นำไปใช้

อัลกอริทึม patience sorting สามารถใช้กับการควบคุมกระบวนการ ในชุดของการวัดการดำรงอยู่ของการเพิ่มระยะยาวที่สามารถใช้เป็นเครื่องหมายแนวโน้ม บทความ 2002 ในนิตยสาร SQL Server มีการใช้ SQL ในบริบทนี้ของอัลกอริธึมการจัดเรียงความอดทนสำหรับระยะเวลาที่ยาวที่สุดที่มีการเพิ่มขึ้น