comparisons, where QCjDDCj , and fo

comparisons, where QC
j
DD
Cj , and for all feasible i and j , Ci is independent of QC
j .
The 1-stage now comes in, requiring additional comparisons to remove the remaining
inversions. When we are about to insert Y. j /, we place it among
fX.1/; : : : ; X. j /g [ fY.1/; : : : ; Y. j¡1/g:
Because the 2-stage has sorted the Y ’s, fY.1/; : : : ; Y. j¡1/g do not have any inversions with
Y. j /. Only fX.1/; : : : ; X. j /g can introduce inversions. It is well known that the so-called
sentinel version of insertion sort makes
C.5n/ D n C I .5n/
comparisons to sort a permutation 5n with I .5n/ inversions. Let Vj be the number of
inversions Y. j / makes with all the elements that precede it, that is
Vj D 1fX.1/>Y. j /g C¢ ¢ ¢C1fX. j />Y. j /g;

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

เปรียบเทียบ ที่ QCเจดีดีCj และทั้งหมดเป็นไปได้ฉันและเจ Ci เป็นอิสระของ QCเจ1-ขั้นตอนนี้มาใน ต้องเปรียบเทียบเพิ่มเติมก็จะเอาเหลือinversions เมื่อเราจะแทรก Y. j / เราทำในfX.1/ : : : ; ไฟร์เจ /g [fY.1/;:::, Y. j¡1/g:เนื่องจากระยะ 2 มีเรียงลำดับ Y ของ fY.1/ : : : ; Y. j¡1/g มี inversions ใด ๆ ด้วยY. j / เฉพาะ fX.1/ : : : ; ไฟร์เจ /g สามารถแนะนำ inversions มันเป็นที่รู้จักที่เรียกว่าทำให้รุ่นยามเรียงลำดับแบบแทรกN C.5n/ D C ฉัน.5n /เปรียบเทียบการเรียงลำดับ 5n เรียงสับเปลี่ยนกับฉัน.5n / inversions ให้เป็นหมายเลขของ Vjinversions Y. j / ทำกับองค์ประกอบทั้งหมดที่ชัดเจน คือ1fX.1/ Vj D > Y. j /g C เลขหมายเลข C1fX. เจ / > Y. j /g

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

การเปรียบเทียบที่ QC
เจ
DD
Cj และทั้งหมดที่ฉันเป็นไปได้และเจ Ci เป็นอิสระจากการควบคุมคุณภาพ
j.
1 ขั้นตอนนี้มาในต้องเปรียบเทียบเพิ่มเติมเพื่อลบส่วนที่เหลืออีก
inversions เมื่อเรากำลังจะแทรกวายเจ / เราวางไว้ในหมู่
fX.1 /; :::; เอ็กซ์เจ / g [fY.1 /; :::; วายj¡1 / g:
เพราะ 2 ขั้นตอนมีการเรียง Y 's, fY.1 /; :::; วายj¡1 / g ไม่ได้มี inversions ใด ๆ
กับวาย เจ / เฉพาะ fX.1 /; :::; เอ็กซ์เจ / กรัมสามารถแนะนำ inversions
เป็นที่ทราบกันดีว่าสิ่งที่เรียกว่ารุ่นแมวมองของการจัดเรียงแทรกทำให้
C.5n / D n CI .5n /
เปรียบเทียบกับเรียงลำดับ 5n เปลี่ยนแปลงกับ I .5n / inversions ให้ VJ เป็นจำนวน
inversions วายเจ / ทำให้มีองค์ประกอบทั้งหมดที่นำหน้านั่นคือ
VJ D 1fX.1 /> Y เจ / กรัม C ¢¢¢ C1fX เจ /> Y เจ / กรัม

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

การเปรียบเทียบที่ QC
J

DD CJ และทั้งหมดที่เป็นไปได้และ J , CI เป็นอิสระของ QC
J .
1-stage ตอนนี้มาในที่ต้องการเปรียบเทียบเพิ่มเติมเพื่อเอา inversions ที่เหลืออยู่

เมื่อเรากำลังจะใส่ Y . J / เราวางไว้ระหว่าง
fx.1/ ; : : : ; X . J / g [ fy.1/ ; : : : ; Y . J ¡ 1 / G :
เพราะพื้นที่มีการเรียง Y ' S , fy.1/ ; : : : ; Y . J ¡ 1 / G ไม่ได้ มี inversions กับ
Y . J /เพียง fx.1/ ; : : : ; X . J / g สามารถแนะนำ inversions . มันเป็นที่รู้จักกันดีว่าเรียกว่า
Sentinel รุ่นของการเรียงลำดับแบบแทรกทำให้
c.5n/ D N C . 5N /
เปรียบเทียบการจัดเรียงเรียงลำดับ 5N กับผม . 5N / inversions . ให้ วีเจ เป็นหมายเลขของ
inversions Y . J / ให้กับองค์ประกอบทั้งหมดที่นำหน้ามัน ที่เป็นวีเจ 1fx
D 1 / > Y . J / g c ¢¢¢ c1fx . J > / Y . J / g ;