CoE KKU

คำว่า inversion ของตัวเลขในอะเรย์ คือ คู่อันดับ (ordered pair) (i, j) ใด ๆ ที่มีคุณสมบัติที่ i < j แต่มี a[i] > a[j] จากรูปที่ 7.1 มีอินพุตคือ 34, 8, 64, 51, 32, 21 มี inversions อยู่ทั้งสิ้น 9 ตัว คือ (34,8), (34,32), (34,21), (64,51), (64,32), (64,21), (51,32), (51,21) และ (32,21) ซึ่งจะเห็นได้ว่าตัวเลข 9 นี้จะเท่ากันกับจำนวนครั้งที่ต้องใช้ในการสลับค่าที่ใช้ใน insertion sort นั่นเอง ซึ่งจะเป็นจริงเช่นนี้เสมอ

เนื่องจากการสลับตำแหน่งสมาชิกสองตัวที่อยู่ติดกันจะทำให้ inversion ตัวหนึ่งหายไป และข้อมูลที่มีการจัดเรียงลำดับค่าแล้วนั้นเป็นข้อมูลที่ไม่มี inversions เนื่องจากในอัลกอริทึมจะมีการทำงานอื่น ๆ อีกด้วยเวลา O(N) ดังนั้น running time ของ insertion sort จึงเป็น O(I + N), เมื่อ I คือจำนวน inversions ของอินพุต ดังนั้น insertion sort จึงใช้เวลาเป็น linear time ถ้าจำนวน inversions เป็น O(N) เราสามารถคำนวณขอบเขตกรณีเฉลี่ยของ running time ของ insertion sort ได้แม่นยำมากขึ้นด้วยการคำนวณหาจำนวนเฉลี่ยของ inversions ใน permutation เราสมมุติให้ข้อมูลไม่มีค่าซ้ำกัน เราสามารถตั้งสมมุติฐานได้ว่าอินพุตก็คือ permutation ของตัวเลขจำนวนเต็มจำนวน N ตัว และตำแหน่งของตัวเลขมีโอกาสเกิดได้เท่า ๆ กัน ด้วยสมมุติฐานนี้ จึงได้ทฤษฎีต่อไปนี้:

THEOREM 7.1.

ค่าเฉลี่ยของจำนวน inversions ที่มีอยู่ในอะเรย์ของเลขจำนวน N ตัวที่ไม่ซ้ำกัน คือ N (N – 1) / 4

PROOF:

สำหรับรายการใด ๆ ของตัวเลข, L, ให้ Lr,เป็นรายการที่มีค่าเรียงย้อนกลับกัน (reverse order) เช่นรายการ 21, 32, 51, 64, 34, 8 เป็นค่าเรียงย้อนกลับของตัวอย่างที่แล้ว คู่ของตัวเลข (x, y) ใด ๆ ในรายการ โดยที่ y > x นั้นแน่นอนว่าต้องเป็นของ L หรือ Lr ตัวใดตัวหนึ่ง และคู่อันดับนี้ คือ inversion นั่นเอง จำนวนทั้งหมดของคู่อันดับเหล่านี้อยู่ในรายการ L และ reverse ของมัน (คือ Lr) มีจำนวนเท่ากับ N(N - 1)/2 ดังนั้นค่าเฉลี่ยของมันคือ ครึ่งหนึ่งซึ่งก็คือ N(N -1)/4 นั่นเอง

จากทฤษฎีหมายความว่า insertion sort มี running time สำหรับกรณีเฉลี่ยเป็น quadratic และยังเป็นขอบเขตล่างของอัลกอริทึมการจัดเรียงใด ๆ ก็ตามที่ใช้การสลับค่าของรายการที่อยู่ติดกันด้วย

THEOREM 7.2

อัลกอริทึมของการจัดเรียงที่ใช้การสลับค่าที่อยู่ติดกันจะมี running time กรณีเฉลี่ยเป็น $\Omega(N^2)$

PROOF:

จำนวนเฉลี่ยของ inversions คือ N(N - 1)/4 ซึ่งก็คือ $\Omega(N^2)$ การสลับค่าแต่ละครั้งจะลด inversion ลงหนึ่งค่า ดังนั้นทั้งหมดจึงต้องใช้การสลับค่า $\Omega(N^2)$ ครั้ง

ขอบเขตล่างที่กล่าวมานั้นแสดงให้เห็นว่าถ้าต้องการจัดเรียงด้วย running time ที่ต่ำกว่า quadratic (subquadratic) หรือ $o(N^2)$ อัลกอริทึมนั้นจะต้องทำการเปรียบเทียบและสลับคู่ของค่าสมาชิกที่อยู่ห่างกันออกไป ดังนั้นอัลกอริทึมของการจัดเรียงที่กำจัด inversions และทำงานได้อย่างมีประสิทธิภาพกว่าจะต้องเป็นอัลกอริทึมที่สามารถกำจัด inversion ได้มากกว่าหนึ่งตัวต่อการสลับค่าหนึ่งครั้ง