CoE KKU

Shellsort ตั้งตามชื่อของผู้คิดค้นการจัดเรียงแบบนี้ คือ Donald Shell (ในปี 1959) และเป็นหนึ่งในอัลกอริทึมแรก ๆ ที่ทำลายขอบเขตเวลาที่เป็น quadratic ถึงแม้ว่าจะพิสูจน์ได้ว่าอัลกอริทึมนี้มี running time ต่ำกว่า quadratic หลังจากที่มีการนำเสนอครั้งแรกในหลายปีต่อมาก็ตาม ในขณะทำงานแต่ละ phase นั้น shell sort ใช้การเปรียบเทียบค่าที่อยู่ในตำแหน่งที่ห่างกัน ระยะห่างดังกล่าวนี้จะลดลงลงเรื่อย ๆ จนกระทั่งถึงขั้นตอนสุดท้ายที่เป็นการเปรียบเทียบค่าที่อยู่ติดกัน ด้วยเหตุที่ระยะห่างของค่าที่นำมาเปรียบเทียบกันลดลงไปในระหว่างการทำงานของอัลกอริทึมนี้เอง จึงเรียก Shellsort อีกอย่างว่า diminishing increment sort

Shellsort ใช้ลำดับ $h_1, h_2, ... , h_t$ ซึ่งเรียกว่า increment sequence และลำดับที่ใช้จะมีค่าลักษณะใดก็ได้เพียงแต่มีเงื่อนไขว่า $h_1 = 1$ เท่านั้น แต่แน่นอนว่าบางลำดับจะทำงานได้ดีกว่าบางลำดับ (จะกล่าวถึงอีกครั้ง) หลังการทำงานแต่ละ phase ที่ใช้ลำดับการเพิ่ม $h_k$ ผลที่ได้ คือ สำหรับแต่ละค่า i เราจะได้ว่า $a[i] ≤ a[i + h_k]$ กล่าวคือสมาชิกทุกตัวที่มีระยะห่างกัน $h_k$ จะอยู่ในลำดับที่มีการจัดเรียงอย่างถูกต้อง ซึ่งเรียกว่า $h_k$-sorted file รูปที่ 7.3 แสดงอะเรย์หลังการทำงานของเฟสต่าง ๆ ของ Shellsort คุณสมบัติที่สำคัญประการหนึ่งของ Shellsort คือ การทำ $h_k$-sorted แล้วตามด้วย $h_{k-1}$-sorted นั้นยังคงสภาพของ hk-sorted เอาไว้ได้เช่นเดิม

รูปที่ 7.3 อะเรย์หลังการทำงานของเฟสต่าง ๆ ของ Shellsort

วิธีการทั่วไปในการทำ $h_k$-sort ก็คือ สำหรับแต่ละตำแหน่ง i ใน $h_k$ , $h_k$ + 1, $h_k$ + 2, . . . , N – 1 ให้ทำการจัดวางสมาชิกลงในตำแหน่งที่ถูกต้องภายในระหว่างตำแหน่ง i, i - $h_k$ , i - 2$h_k$ etc. สิ่งสำคัญคือ การทำงานของ $h_k$-sort หนึ่ง ๆ นั้นจะเป็นการทำ insertion sort กับอะเรย์ย่อย $h_k$ ที่เป็นอิสระกัน

ลำดับการเพิ่มที่นิยมใช้ (แต่ไม่ดี) คือลำดับการเพิ่มที่เสนอโดย Shell คือลำดับ $h_t = ⌊N/2⌋$ และ $h_k = ⌊h_{k+1}/2⌋$ รูปที่ 7.4 เป็นโปรแกรมที่ใช้ลำดับการเพิ่มนี้ ในปัจจุบันมีการคิดค้นลำดับการเพิ่มที่แตกต่างออกไปที่ทำให้อัลกอริทึมมีประสิทธิภาพที่ดีกว่านี้

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

รูปที่ 7.4 Shellsort ที่ใช้ลำดับการเพิ่มที่เสนอโดย Shell

การวิเคราะห์หาร running time ของ Shellsort จะมีความยุ่งยากอยู่มาก ทั้งนี้เนื่องจาก running time ของมันขึ้นอยู่กับการเลือกใช้ลำดับการเพิ่ม และการพิสูจน์ก็มีความยุ่งยากมาก การพิสูจน์กรณีเฉลี่ยของ Shellsort ก็ยังเป็นที่ถกเถียงกันอยู่ยกเว้นกรณีที่ใช้ลำดับการเพิ่มพื้น ๆ เท่านั้น เราจะกล่าวถึงขอบเขตของกรณี worst-case สำหรับลำดับการเพิ่มที่เสนอโดย Shell

THEOREM 7.3

running time กรณี worst-case ของ Shellsort ที่ใช้ลำดับการเพิ่มของ Shell คือ $\Theta(N^2)$

PROOF:

ในการพิสูจน์ไม่เพียงแต่ต้องแสดงให้เห็นถึงขอบเขตบนของ running time กรณี worst-case เท่านั้น แต่ยังต้องแสดงว่ามีบางอินพุตที่ต้องใช้เวลาในการทำงานเป็น $\Omega(N^2)$ ด้วย ในตอนแรกจะพิสูจน์ขอบเขตล่างก่อน (lower bound) โดยการสร้างกรณีข้อมูลไม่ดีขึ้น ก่อนอื่นเลือกค่า N ให้มีค่าเป็นเลขยกกำลังของ 2 ซึ่งจะทำให้ลำดับการเพิ่มทั้งหมดเป็นเลขคู่ ยกเว้นลำดับการเพิ่มสุดท้ายที่มีค่าเท่ากับ 1 และกำหนดให้อินพุตเป็นอะเรย์ input_data ที่มีกลุ่มที่มีค่ามากที่สุดจำนวน N/2 ตัวอยู่ในตำแหน่งคู่และกลุ่มที่มีค่าน้อยที่สุดอีกจำนวน N/2 ตัวอยู่ในตำแหน่งเลขคี่ เมื่อการทำงานในรอบก่อนรอบสุดท้ายจบลงจะพบว่ากลุ่มตัวเลขที่มากที่สุด N/2 ตัวก็ยังคงอยู่ในตำแหน่งเลขคู่ และกลุ่มตัวเลขที่น้อยที่สุดจำนวน N/2 ตัวก็ยังคงอยู่ในตำแหน่งคี่ ดังนั้นก่อนการเริ่มทำงานในรอบสุดท้ายตัวเลขที่มีค่าน้อยที่สุดอันดับที่ i ซึ่ง i ⇐ N/2 มีอยู่ในตำแหน่ง 2i – 1 เพื่อที่จะทำให้สมาชิกตัวที่ i นี้ไปอยู่ในตำแหน่งที่ถูกต้องของมันเราต้องเคลื่อนย้ายมันเป็นระยะ i – 1 ตำแหน่งภายในอะเรย์ ดังนั้น เพื่อที่จะจัดวางให้ตัวเลขที่น้อยที่สุดจำนวน N/2 ตัวไปอยู่ในตำแหน่งที่ถูกต้องของมัน เราต้องใช้การทำงานอย่างน้อย $∑_{i=1}^{N/2} i-1 = \Omega(N^2)$ รูปที่ 7.5 แสดงอินพุตที่ไม่ดี (แต่ไม่ใช่เป็นกรณี worst case) เมื่อ N = 16 จำนวน inversion ยังคงมีอยู่ภายหลัง 2-sort คือ 1+2+3+4+5+6+7 = 28 ซึ่งในการทำงานรอบสุดท้ายจะยังคงใช้เวลามากทีเดียว

สุดท้ายจะแสดงให้เห็นว่าขอบเขตบน คือ $O(N^2)$ ดังที่ได้กล่าวแล้วว่า การทำงานในรอบที่มีลำดับการเพิ่มเป็น $h_k$ นั้นต้องใช้การทำงาน insertion sort ที่ทำกับสมาชิกจำนวนประมาณ $N/h_k$ ตัว เป็นจำนวน $h_k$ ครั้ง เนื่องจาก insertion sort เป็น quadratic ดังนั้นในแต่ละรอบจึงใช้เวลาทั้งหมดเป็น $O(h_k(N/h_k)^2) = O(N^2/h_k)$ ดังนั้นเมื่อรวมทุกรอบการทำงานทั้งหมดแล้วจะได้ $Ο(∑_{i=1}^tN^2/h_i) = Ο(N^2 ∑_{i=1}^t 1/h_i)$ และเนื่องจากรูปแบบลำดับการเพิ่มเป็น geometric series ที่มี common ratio เป็น 2 และเทอมที่มากที่สุดคือ h1 = 1 และ $∑_{i=1}^t 1/h_i < 2$ ดังนั้นจึงได้ $O(N^2)$

รูปที่ 7.5 อินพุตที่ไม่ดีสำหรับ Shellsort ที่ใช้การเพิ่มของ Shell เมื่อ N = 16

Hibbard เสนอลำดับการเพิ่มที่แตกต่างไปเล็กน้อยซึ่งให้ผลในทางปฏิบัติที่ดีกว่าเล็กน้อยลำดับการเพิ่มดังกล่าว คือ $1, 3, 7, ... , 2^k – 1$ และ running time สำหรับกรณี worst-case ของ Shellsort ที่ใช้ลำดับการเพิ่มของ Hibbard คือ $\Omega(N^{3/2})$ นอกจากนี้ยังมีผู้เสนอลำดับการเพิ่มแบบอื่น ๆ ซึ่งให้ผล running time ที่แตกต่างกันออกไปมากบ้างน้อยบ้าง อีกทั้งการวิเคราะห์ก็มีความซับซ้อนมากต้องใช้ทฤษฎีทางคณิตศาสตร์ ขั้นสูง เช่น ลำดับการเพิ่มที่เสนอโดย Sedgewick ($4^k+3·2^k-1 + 1$) มี running time เป็น $O(N^{4/3})$ ในกรณี worst-case ประสิทธิภาพการทำงานของ Shellsort เป็นที่ยอมรับกันในทางปฏิบัติ ถึงแม้ขนาดอินพุตจะมีจำนวนหลายหมื่นหน่วยข้อมูล การที่ Shellsort เขียนโปรแกรมง่ายทำให้เป็นที่นิยมใช้เพื่อจัดเรียงข้อมูลที่มีขนาดไม่ใหญ่มากนัก