A sorting algorithm is called adapt

A sorting algorithm is called adaptive with respect
to some measure of presortedness if, for some given
input size, the running time of the algorithm is provably
better for inputs with low value of the measure. Perhaps
the most well-known measure is Inv, the number of
inversions (i.e. pairs of elements that are in the wrong
order) in the input. Other measures of presortedness
include Rem, the minimum number of elements that
must be removed for the remaining elements to be
sorted, and Runs, the number of consecutive ascending
runs. More examples of measures can be found in [5].
An example of an adaptive sorting algorithm is insertion
sort using level-linked B-trees with nger searches for
locating each new insertion point [13], which sorts in
O(n(1 + log(1 + Inv=n))) time. In the comparison
model, this is known to be optimal with respect to the
measure Inv [5].

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

อัลกอริทึมการเรียงลำดับเรียกว่าเหมาะสม ด้วยความเคารพการวัดบาง presortedness ถ้า สำหรับให้ป้อนข้อมูล เวลาทำงานของอัลกอริทึมมีขนาด provablyดีสำหรับอินพุตมีค่าต่ำสุดของการวัด บางทีวัดรู้จักมากที่สุดเป็น Inv จำนวนinversions (เช่นคู่ขององค์ประกอบที่อยู่ในไม่ถูกต้องสั่ง) ในการป้อนข้อมูล มาตรการอื่น ๆ ของ presortednessมี Rem จำนวนขององค์ประกอบที่ต้องเอาองค์ประกอบที่เหลือให้เรียงลำดับ และทำ งาน จำนวนเรียงติดกันทำงาน สามารถพบตัวอย่างเพิ่มเติมมาตรการใน [5]ตัวอย่างของขั้นตอนวิธีการเรียงลำดับที่เหมาะสมคือ แทรกเรียงลำดับการเชื่อมโยงระดับ B-ต้นไม้ด้วย nger หาแต่ละแทรกจุดใหม่ [13], การเรียงลำดับในการค้นหาO (n (1 + ล็อก (1 + Inv = n))) เวลานั้น ในการเปรียบเทียบรุ่น นี้เป็นที่รู้จักกันจะเหมาะสมที่สุดกับ respect เพื่อวัด Inv [5]

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

อัลกอริทึมการเรียงลำดับเรียกว่าการปรับตัวด้วยความเคารพในการชี้วัดของ presortedness บางอย่างถ้าสำหรับบางคนที่กำหนดขนาดการป้อนข้อมูลเวลาการทำงานของอัลกอริทึมเป็นสรรพสิ่งที่ดีกว่าสำหรับปัจจัยการผลิตที่มีมูลค่าต่ำของวัด บางทีอาจจะเป็นตัวชี้วัดที่รู้จักกันดีที่สุดคือ Inv จำนวน inversions (เช่นคู่ขององค์ประกอบที่อยู่ในที่ไม่ถูกต้องตามลำดับ) ในการป้อนข้อมูล มาตรการอื่น ๆ ของ presortedness รวมถึง Rem, จำนวนขั้นต่ำขององค์ประกอบที่จะต้องออกสำหรับองค์ประกอบที่เหลือที่จะเรียงและทำงานจำนวนน้อยไปมากติดต่อกันวิ่ง ตัวอย่างอื่น ๆ ของมาตรการสามารถพบได้ใน [5]. ตัวอย่างของขั้นตอนวิธีการเรียงลำดับการปรับตัวมีการแทรกการเรียงลำดับโดยใช้ระดับการเชื่อมโยง B-ต้นไม้ที่มีการค้นหา Nger สำหรับตำแหน่งแต่ละจุดแทรกใหม่[13] ซึ่งเรียงลำดับในO (n (1 + เข้าสู่ระบบ (1 + Inv n =))) เวลา ในการเปรียบเทียบรูปแบบนี้เป็นที่รู้จักกันดีที่สุดเกี่ยวกับการวัดInv [5]

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

เรียงลำดับขั้นตอนวิธีเรียกว่า Adaptive ด้วยความเคารพ
ถึงบางวัด presortedness เผื่อว่าให้
ขนาดใส่วิ่งเวลาของขั้นตอนวิธีอาจ
ดีกว่าสำหรับปัจจัยการผลิตที่มีค่าต่ำของวัด บางที
วัดที่เป็นที่รู้จักมากที่สุดคือ INV , จํานวนของ
inversions ( เช่นคู่ขององค์ประกอบที่อยู่ในลำดับผิด
) ในการป้อนข้อมูล มาตรการอื่น ๆของ presortedness
รวมถึงเรมจำนวนขั้นต่ำขององค์ประกอบที่
ต้องออกเพื่อให้เหลือองค์ประกอบ
เรียง และวิ่ง หมายเลขติดต่อกันขึ้น
วิ่ง อีกตัวอย่างของมาตรการที่สามารถพบได้ใน [ 5 ] .
ตัวอย่างของการปรับตัวขั้นตอนวิธีการเรียงลำดับการจัดเรียงแทรก
ระดับการใช้เชื่อมโยง b-trees กับ  เง้อค้นหา
ตำแหน่งจุดแทรกแต่ละใหม่ [ 13 ] ซึ่งประเภทใน
o ( n ( 1 log ( 1 N = N ) ) ) ) ) ) ) เวลาในการเปรียบเทียบ
รุ่นนี้เป็นที่รู้จักกันเพื่อให้เหมาะสมกับการเคารพ
วัด INV [ 5 ]