We show below that the randomized S

We show below that the randomized Shellsort, as described
in Section 2, will  polylog(n)-near-sort an input array
A, with very high probability, for some constant  > 0.
We can then use Pratt’s version [36] of (deterministic) Shellsort
as a 2 polylog(n)-sorter, S, in a S-shaker postprocessing
pass over A, which will run in O(n(log log n)2) time and
(by Lemma 2.1) will complete the sorting of A. Note, in addition,
that since we are using a Shellsort implementation in
an S-shaker (Shellsort-type) pass, adding this postprocessing
phase to our randomized Shellsort algorithm keeps the
entire algorithm being a data-oblivious variant of the Shellsort
algorithm.

ผลลัพธ์ (ไทย) 1:

เราแสดงด้านล่างที่ Shellsort สุ่ม ตามที่อธิบายไว้ในส่วนที่ 2 จะ polylog (n) -ใกล้ - เรียงเป็นแถวอินพุตA มีความเป็นไปได้สูงมาก สำหรับบางคง > 0เราสามารถใช้รุ่นรทส์ [36] Shellsort (deterministic)เป็น polylog 2 (n) -เรียงลำดับ S ในการ postprocessing S-ปั่นผ่านไป A ซึ่งจะเรียกใช้ใน O (n (n ล็อกล็อก) 2) เวลา และ(โดยหน่วยการ 2.1) จะทำการเรียงลำดับหมายเหตุ A. นอกจากนี้ว่า ตั้งแต่เราใช้ Shellsort ดำเนินในpass S-วัติ (Shellsort ชนิด) เพิ่ม postprocessing นี้ขั้นตอนอัลกอริทึม Shellsort สุ่มของเราช่วยให้การอัลกอริทึมทั้งที่เป็นตัวแปรข้อมูลที่ลืมเลือนของ Shellsortอัลกอริทึม

ผลลัพธ์ (ไทย) 2:

เราจะแสดงด้านล่างที่ Shellsort สุ่มตามที่อธิบายไว้
ในส่วนที่ 2 จะ? polylog (N) -near จัดเรียงใส่อาร์เรย์
ที่มีความน่าจะเป็นสูงมากสำหรับบางคนคง? > 0
จากนั้นเราสามารถใช้แพรตต์รุ่น [36] ของ (กำหนด) Shellsort
เป็น 2 หรือไม่? polylog (N) -sorter, S, ใน S-ปั่น postprocessing
ผ่านไปซึ่งจะทำงานใน O (n (log log n) 2) เวลาและ
(โดยแทรก 2.1) จะเสร็จสิ้นการเรียงลำดับของ A. หมายเหตุใน นอกจากนี้
ว่าตั้งแต่เราจะใช้การดำเนินการ Shellsort ใน
S-ปั่น (Shellsort ชนิด) ผ่านการเพิ่ม postprocessing นี้
ขั้นตอนขั้นตอนวิธีการสุ่ม Shellsort ของเราช่วยให้
ขั้นตอนวิธีการทั้งหมดเป็นตัวแปรข้อมูลลบเลือนของ Shellsort
อัลกอริทึม

ผลลัพธ์ (ไทย) 3:

เราจะแสดงด้านล่างที่สุ่ม shellsort ตามที่อธิบายในส่วนที่ 2 จะ polylog ( n ) - ใกล้ เรียงใส่เรย์, มีความน่าจะเป็นสูงมาก บางคงที่ > 0เราสามารถใช้รถรุ่น [ 36 ] ( deterministic ) shellsortเป็น 2 polylog ( n ) - ตัว , S , ใน s-shaker โพรเซสซิ่งผ่านซึ่งจะทำงานใน O ( N ( log log n ) 2 ) เวลา( แทรก 2.1 ) จะเสร็จสมบูรณ์การบันทึก . นอกจากนี้เพราะเราใช้ shellsort การใช้งานในการ s-shaker ( shellsort ชนิด ) ผ่านการเพิ่มข้างหลังนี้ขั้นตอนโดยขั้นตอนวิธีการของเรา shellsort เก็บขั้นตอนวิธีการทั้งหมดเป็นข้อมูลตัวแปรของ shellsort ลบเลือนขั้นตอนวิธี