To show that this method sorts an m

To show that this method sorts an m-near-sorted array
A, we make use of the zero-one principle for sorting networks
(which also applies to data-oblivious sorting algorithms):Theorem 2.1 (Knuth [24]): A sorting network (or dataoblivious
sorting algorithm) correctly sorts all sequences of
arbitrary inputs if and only if it correctly sorts all sequences
of 0-1 inputs.
The main idea behind this principle is that it allows us to
reduce each case of distinguishing the k largest elements and
the n−k smallest elements to an instance having k ones and
n − k zeroes. This allows us to easily prove the following:
Lemma 2.1: Given an m-near-sorted array A of size n, and
a 2m-sorter S, running in T(m) time, a S-shaker pass over
A will sort A in O(T(m)n/m) time.

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

แสดงว่า วิธีนี้เรียงลำดับเป็นแถว m ใกล้เรียงA ที่เราทำใช้หลักการหนึ่งเป็นศูนย์สำหรับการเรียงลำดับเครือข่าย(ซึ่งยังใช้กับอัลกอริทึมการเรียงลำดับข้อมูลขยี้): ทฤษฎีบท 2.1 (Knuth [24]): เครือข่ายการเรียงลำดับ (หรือ dataobliviousการเรียงลำดับขั้นตอนวิธี) อย่างถูกต้องเรียงลำดับทั้งหมดของโดยอำเภอใจอินพุตและถ้าหากมันถูกต้องเรียงลำดับทั้งหมด0-1 อินพุตหลักเบื้องหลังหลักการนี้ก็คือ ว่า มันช่วยให้เราได้ลดแต่ละกรณีแยกความแตกต่างที่ใหญ่ที่สุดองค์ประกอบ k และองค์ประกอบที่เล็กที่สุดของ n−k กับอินสแตนซ์ที่มี k คน และn − k เป็นศูนย์ ทำให้เราได้พิสูจน์ต่อไปนี้:หน่วยการที่ 2.1: รับ m ใกล้เรียงเป็นแถว A ของขนาด n และS เรียงลำดับ 2 เมตร ทำงานใน T(m) เวลา ผ่าน S-ปั่นผ่านA จะเรียงลำดับ A O(T(m)n/m) เวลา

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

แสดงให้เห็นว่าวิธีการนี้แปลก M-ใกล้เรียงอาร์เรย์
เราใช้หลักการศูนย์หนึ่งสำหรับการจัดเรียงเครือข่าย
(ซึ่งยังนำไปใช้อัลกอริทึมข้อมูลลบเลือนเรียงลำดับ): ทฤษฎีบท 2.1 (นู [24]): เรียงลำดับ เครือข่าย (หรือ dataoblivious
ขั้นตอนวิธีการเรียงลำดับ) อย่างถูกต้องเรียงลำดับทั้งหมดของ
ปัจจัยการผลิตที่กำหนดเองและถ้าหากมันถูกต้องเรียงลำดับทั้งหมด
ของปัจจัยการผลิต 0-1
ความคิดหลักที่อยู่เบื้องหลังหลักการนี้ก็คือว่ามันช่วยให้เราสามารถ
ลดแต่ละกรณีของการแยกความแตกต่าง K องค์ประกอบที่ใหญ่ที่สุดและ
เป็นส่วนประกอบเล็ก ๆ n-K เพื่ออินสแตนซ์ที่มีคน K และ
n - k เลขศูนย์ นี้จะช่วยให้เราได้อย่างง่ายดายพิสูจน์ต่อไปนี้:
บทแทรก 2.1: ให้เอ็มใกล้เรียงอาร์เรย์ขนาด n และ
(M) เวลา 2m-เรียงลำดับ S, ทำงานใน T, ผ่าน S-ปั่นกว่า
จะจัดเรียง ใน O (T (M) n / m) เวลา

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

เพื่อแสดงให้เห็นว่าวิธีการนี้ประเภทที่เป็น m-near-sorted เรย์เป็นเราใช้ของศูนย์หนึ่งหลักการสำหรับการจัดเรียงเครือข่าย( ซึ่งยังใช้กับข้อมูลลบเลือนขั้นตอนวิธีการเรียงลำดับ ( 2.1 ) : ทฤษฎีบท คนูธ [ 24 ] ) : เครือข่าย ( หรือ dataoblivious การเรียงลำดับขั้นตอนวิธีการเรียงลำดับของประเภททั้งหมด ) อย่างถูกต้องกระผมเองถ้าและเพียงถ้ามันถูกต้องเรียงลำดับทั้งหมด0-1 ปัจจัยการผลิตความคิดหลักของทฤษฎีนี้ก็คือว่ามันช่วยให้เราลดแต่ละกรณีแยก K ใหญ่ที่สุด องค์ประกอบn − K น้อยที่สุดองค์ประกอบ เช่น มีคน และเคn − K zeroes . นี้ช่วยให้เราสามารถพิสูจน์ได้ดังต่อไปนี้พ 2.1 : ได้รับ m-near-sorted array ของขนาด n และเป็นเครื่องคัดแยก 2 เมตร , วิ่งใน t ( M ) s-shaker ผ่านเวลาจะเรียงเป็น O ( t ( m ) N / m ) เวลา