Shell Sort

Shell Sort

     Shell sort เป็นการพัฒนาวิธีการ sort จาก insertion sort ให้มีประสิทธิภาพในการ sort มากยิ่งขึ้น ด้วยการลดช่องว่างของการ sort ลง โดยแบ่งข้อมูลออกเป็นส่วน ๆ (segment) ในการ sort และทาการ sort ข้อมูลในแต่ละส่วน หลังจากนั้นก็ทาการแบ่งออกเป็นส่วน ๆ อีกโดยให้มีจานวนของ segment น้อยกว่าการแบ่งครั้งแรก ทากระบวนการดังกล่าวไปจนกว่าจานวนของ segment จะมีค่าเป็นหนึ่ง จึงยุติการ sort

หลังจากที่เราได้แบ่งข้อมูลออกเป็น 5 ส่วนดังที่เห็นในภาพ เราก็ทาการจัดเรียงข้อมูลในแต่ละส่วน

หลังจากการจัดเรียงข้อมูลเมื่อ segment เท่ากับ 5 ได้สิ้นสุดลงแล้ว เราจะทาการแบ่งข้อมูลออกเป็นส่วน ๆ อีก โดยคราวนี้เราจะแบ่งข้อมูลออกเป็น 3 ส่วน

เมื่อแบ่งข้อมูลได้แล้วเราก็ทาการจัดเรียงข้อมูลในแต่ละส่วน

และในที่สุดเราก็มาถึงขั้นตอนสุดท้ายคือ จานวนของ segment เหลือเพียงแค่ segment เดียว การจัดเรียงข้อมูลก็เกิดขึ้นภายใน segment นี้

Algorithms Shell Sort

public static <T extends Comparable<? super T>>

void shell (T[] arr) {

    int i, j;

    T temp;

    //calculate increment value K (# of segments)

    //based on Knuth's interval sequence

    int k = 1;

    while(k <= arr.length / 3)

       k = k * 3 + 1; //1, 4, 13, 40, 121, ...

    //sort array until # of segment is 1

    while(k > 0) {

          //sorting items in each segment simultanously

          for(i = k; i < arr.length; i++) {

              temp = arr[i];

              j = i;

              //one sub-pass; using j as index through items

             //in each segment

             while(j > k - 1 && arr[j-k].compareTo(temp) >= 0) {

                   arr[j] = arr[j - k];

                   j -= k;

             }

             arr[j] = temp;

        }

        k = (k - 1) / 3; //decreasing K value

    }

}