อัลกอริทึม Shell Sort พร้อมตัวอย่าง

Shell Sort คืออะไร?

Shell Sort หรือที่เรียกว่าวิธีของ Shell เป็นอัลกอริทึมการเรียงลำดับแบบเปรียบเทียบที่มีประสิทธิภาพสูง ซึ่งทำงานแบบ in-place ตั้งชื่อตาม Donald Shell ผู้ริเริ่มแนวคิดนี้ในปี 1959 โดยเป็นส่วนขยายทั่วไปของ Insertion Sort ที่สามารถเอาชนะพฤติกรรมแบบกำลังสองของ Insertion Sort บนข้อมูลที่กระจัดกระจายได้

แนวคิดพื้นฐานคือ��ารจัดกลุ่มองค์ประกอบที่อยู่ห่างกันมาก จัดเรียงแต่ละกลุ่มโดยใช้การเรียงลำดับแบบแทรก และลดช่องว่างทีละขั้นตอนจนกระทั่งเหลือหนึ่ง เมื่อถึงตอนนั้นอาร์เรย์ก็จะเรียงลำดับเกือบสมบูรณ์แล้ว

ช่องว่างหรือช่วงเวลานี้ เป็นไปตามลำดับที่เลือกไว้ เช่น ลำดับดั้งเดิมของเชลล์, คนูธ, ฮิบเบิร์ด หรือเซดจ์วิก ลำดับดั้งเดิมของเชลล์คือ n/2, n/4, ..., 1.

อัลกอริทึมการเรียงลำดับเชลล์

ขั้นตอน 1) กำหนดค่าเริ่มต้นของช่วง h เป็น h = n/2 โดยที่ n คือขนาดของอาร์เรย์

ขั้นตอน 2) นำองค์ประกอบทั้งหมดที่อยู่ภายในระยะห่าง h มาใส่ไว้ในรายการย่อย

ขั้นตอน 3) เรียงลำดับแต่ละรายการย่อยโดยใช้การเรียงลำดับแบบแทรก (insertion sort)

ขั้นตอน 4) กำหนดช่วงเวลาใหม่ h = h/2

ขั้นตอน 5) ถ้า h > 0 ให้กลับไปที่ขั้นตอนที่ 2 มิฉะนั้น ให้ไปที่ขั้นตอนที่ 6

ขั้นตอน 6) ขณะนี้อาร์เรย์ที่ได้นั้นเรียงลำดับอย่างสมบูรณ์แล้ว

การเรียงลำดับเชลล์ทำงานอย่างไร

ในการเรียงลำดับแบบแทรก (insertion sort) องค์ประกอบจะเคลื่อนที่ไปทีละตำแหน่งเท่านั้น แต่การเรียงลำดับแบบเชลล์ (Shell Sort) จะแบ่งอาร์เรย์ออกเป็นรายการย่อยที่มีระยะห่างกันมากตามช่วงที่กำหนด และทำการเรียงลำดับแบบแทรกกับแต่ละรายการย่อยนั้น

เมื่อช่วงเวลาลดลง ขนาดของรายการย่อยจะเพิ่มขึ้น เนื่องจากขั้นตอนก่อนหน้านี้ทำให้ข้อมูลเรียงลำดับเพียงบางส่วน ช่วงเวลาที่เล็กกว่าจึงต้องการการสลับน้อยกว่าการทำงานปกติมาก การเรียงลำดับการแทรก เริ่มต้นใหม่ทั้งหมด ภาพด้านล่างแสดงขั้นตอนการเรียงลำดับแบบ Shell Sort หนึ่งรอบ

การทำงานของอัลกอริธึม Shell Sort พร้อมตัวอย่าง

มาเรียงลำดับอาร์เรย์ด้านล่างโดยใช้ Shell Sort กัน

ขั้นตอน 1) ขนาดของอาร์เรย์คือ 8 ดังนั้นค่าช่วงเริ่มต้นคือ h = 8/2 = 4

ขั้นตอน 2) จัดกลุ่มองค์ประกอบโดยเว้นระยะห่างกันสี่ตำแหน่ง รายการย่อย: {8, 1}, {6, 4}, {7, 5}, {2, 3}

ขั้นตอน 3) เรียงลำดับแต่ละรายการย่อยโดยใช้การเรียงลำดับแบบแทรก (insertion sort) ตัวแปรชั่วคราวจะเก็บค่าที่กำลังวางลงไปในขณะที่องค์ประกอบต่างๆ เลื่อนตำแหน่ง หลังจากสลับตำแหน่งแล้ว อาร์เรย์จะมีลักษณะดังนี้

ขั้นตอน 4) ลดช่วงเวลา���ง ช่วงเวลาใหม่คือ h = 4/2 = 2

ขั้นตอน 5) เนื่องจาก 2 > 0 ให้กลับไปที่ขั้นตอนที่ 2 และจัดกลุ่มองค์ประกอบที่ห่างกันสองตำแหน่ง: {1, 5, 8, 7} และ {4, 2, 6, 3}

เรียงลำดับรายการย่อยแรก อาร์เรย์จะกลายเป็น:

หลังจากจัดเรียงรายการย่อยที่สองแล้ว:

ลดช่วงลงอีกครั้งเป็น h = 2/2 = 1 ด้วยช่องว่างหนึ่ง Shell Sort จะทำการเรียงลำดับแบบแทรกครั้งสุดท้ายกับอาร์เรย์ทั้งหมด ดังแสดงด้านล่าง

ขั้นตอน 6) เมื่อหารช่วงอีกครั้งจะได้ 0 ตอนนี้อาร์เรย์เรียงลำดับเสร็จสมบูรณ์แล้ว:

หลอกCode สำหรับการเรียงลำดับเชลล์

Start
Input array a of size n
for (interval = n / 2; interval > 0; interval /= 2)
    for (i = interval; i < n; i += 1)
        temp = a[i];
        for (j = i; j >= interval && a[j - interval] > temp; j -= interval)
            a[j] = a[j - interval];
        a[j] = temp;
End

โปรแกรม Shell Sort ใน C/C++

Input:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

Output:

Sorted Output:

1 2 3 4 5 6 7 8

ตัวอย่างการเรียงลำดับเชลล์ใน Python

Input:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

Output:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

การใช้งานของ Shell Sort

Shell Sort ยังคงพบเห็นได้ในระบบสมัยใหม่ที่ให้ความสำคัญกับพื้นที่สแต็กหรือความเรียบง่าย

• การขอ ลินุกซ์เคอร์เนล ใช้ Shell Sort ในกรณีที่การหลีกเลี่ยง Call Stack มีความสำคัญ
• uClibc ซึ่งเป็นไลบรารี C แบบฝังตัว ใช้ Shell Sort เพื่อลดการใช้หน่วยความจำ
• bzip2 ใช้ Shell Sort เพื่อหลีกเลี่ยงการเรียกซ้ำแบบลึกในระหว่างการเรียงลำดับแบบบล็อก
• เฟิร์มแวร์แบบฝังตัวนิยมใช้ Shell Sort สำหรับชุดข้อมูลขนาดเล็กที่การเรียกซ้ำมีข้อจำกัด

ข้อดีและข้อเสียของการเรียงลำดับแบบเชลล์

การวิเคราะห์ความซับซ้อนของการเรียงลำดับเชลล์

ความซับซ้อนของเวลาของการเรียงลำดับเชลล์

ความซับซ้อนเชิงเวลาของ Shell Sort ขึ้นอยู่กับลำดับช่องว่างที่ใช้

ในกรณีที่ดีที่สุด เมื่ออาร์เรย์ได้รับการจัดเรียงเกือบสมบูรณ์แล้ว แต่ละรอบจะต้องการการทดสอบเพียงจำนวนลอการิทึม ทำให้ได้ประสิทธิภาพ O(n log n)

ในกรณีที่เลวร้ายที่สุด อาร์เรย์จะถูกจัดเรียงเพื่อให้องค์ประกอบต่างๆ ต้องการการเปรียบเทียบสูงสุด และการเพิ่มค่าครั้งสุดท้ายจะครอบงำที่ O(n^2) ด้วยลำดับดั้งเดิมของ Shell

1. ความซับซ้อนในกรณีที่ดีที่สุด: O(n log n)
2. ความซับซ้อนในกรณีเฉลี่ย: O(n log n) ถึง O(n^(4/3)) ขึ้นอยู่กับลำดับช่องว่าง
3. ความซับซ้อนในกรณีที่เลวร้ายที่สุด: O(n^2) ด้วยลำดับดั้งเดิมของ Shell

ลำดับช่องว่างอเนกประสงค์ที่ดีที่สุดยังคงเป็นคำถามวิจัยที่เปิดกว้างอยู่ แม้ว่าลำดับ Sedgewick และ Ciura จะทำงานได้ดีในทางปฏิบัติก็ตาม

ความซับซ้อนของพื้นที่การเรียงลำดับเชลล์

Shell Sort ไม่จำเป็นต้องใช้อาร์เรย์เสริม ดังนั้นความซับซ้อนของพื้นที่จึงเป็น O(1) โดยไม่คำนึงถึงขนาดของข้อมูลนำเข้า ซึ่งเป็นหนึ่งในข้อได้เปรียบที่สำคัญที่สุดในทางปฏิบัติ

คำถ��มที่พบบ่อย