CoE KKU

Insertion Sort เป็นอัลกอริทึมอย่างง่ายอัลกอริทึมหนึ่งสำหรับการจัดเรียงค่า อัลกอริทึมมีการทำงานเป็นรอบที่ประกอบด้วยจำนวนรอบ N – 1 รอบ (passes) สำหรับจากรอบที่ p = 2 ถึง N ก็จะประกันได้ว่าสมาชิกที่อยู่ในตำแหน่ง 1 ถึง p จะถูกจัดอยู่ในลำดับที่ถูกต้องแล้ว การทำงานของ Insertion sort จะใช้ประโยชน์จากความจริงที่ว่าการทำงานในรอบที่ p นั้นสมาชิกในตำแหน่งที่ 1 ถึง p - 1 เป็นสมาชิกที่ถูกจัดเรียงเรียบร้อยแล้ว รูปที่ 7.1 แสดงตัวอย่างข้อมูลหลังการทำงานแต่ละรอบของ insertion sort

รูปที่ 7.1 แสดงวิธีทั่วไปของอัลกอริทึมโดยการทำงานในรอบที่ p เราจะเคลื่อนสมาชิกของตำแหน่ง p ไปทางซ้ายจนพบตำแหน่งที่ถูกต้องในระหว่างกลุ่มสมาชิก p + 1 ตัวแรก รูปที่ 7.2 แสดงโปรแกรมที่ทำงานตามที่ได้กล่าวมานี้ บรรทัดที่ 2 ถึง 5 จะทำการเลื่อนสมาชิกแบบที่กล่าวมาโดยไม่ได้มีการสลับค่ากันกับสมาชิกอื่น ๆ สมาชิกตัวที่ p ถูกจัดเก็บในตัวแปร tmp และสมาชิกที่มีตำแหน่งอยู่ข้างหน้าและมีค่ามากกว่ามันก็จะถูกเลื่อนไปทางขวามือ 1 ตำแหน่งเพื่อจะได้ช่องว่างในตำแหน่งสำหรับวางค่าของ tmp ลงในตำแหน่งนั้น

รูปที่ 7.1 ข้อมูลหลังการทำงานแต่ละรอบของ insertion sort

        public static void insertionSort( Comparable [ ] a )
        {   int j;
/* 1*/      for( int p = 1; p < a.length; p++ )
            {
/* 2*/          Comparable tmp = a[ p ];
/* 3*/          for ( j = p; j > 0 && tmp.compareTo(a[ j - 1 ]) < 0; j-- )
/* 4*/              a[ j ] = a[ j - 1 ];
/* 5*/          a[ j ] = tmp;
            }
        }

รูปที่ 7.2 โปรแกรมฟังก์ชัน Insertion sort

เนื่องจากโปรแกรมใช้ลูปซ้อน และแต่ละลูปอาจทำงานได้เป็นจำนวน N รอบ ดังนั้น insertion sort จึงเป็น $O(N^2)$ และ running time นี้เป็นขอบเขตที่มั่นคง เนื่องจากถึงแม้อินพุตจะมีลำดับที่เรียงกลับกันก็จะยังได้ running time นี้ หากพิจารณาอย่างละเอียดจะพบว่าในบรรทัดที่ 3 จะมีการทดสอบค่าที่มีจำนวนครั้งทำมากที่สุด p+1 ครั้งสำหรับแต่ละค่า p ดังนั้นเมื่อรวมทุกค่า p เข้าด้วยกันจะได้ $∑_{i=2}^N i=2+3+4+⋯+N=\Theta(N^2 )$

อีกด้านหนึ่ง ถ้าอินพุตมีการจัดเรียงไว้เรียบร้อยแล้วแต่แรก อัลกอริทึมนี้ก็จะมี running time เป็น $O(N)$ เนื่องจากว่าคำสั่งที่เป็นการทดสอบในลูป for ด้านใน (inner loop) จะล้มเหลวในทันที ความจริงแล้วถ้าข้อมูลที่เป็นอินพุตเกือบทั้งหมดได้รับการจัดเรียงมาก่อนแล้ว insertion sort ก็จะทำงานได้เร็วมาก เนื่องจากความหลากหลายของข้อมูลอินพุตเองทำให้การวิเคราะห์กรณีเฉลี่ยได้ประโยชน์มากกว่า และสำหรับกรณีเฉลี่ยแล้วอัลกอริทึมนี้จะมี running time เป็น $\Theta(N^2)$ ซึ่งจะกล่าวถึงต่อไป