Thuật toán Shell Sort – HỌC VIỆN NGÂN HÀNG VIỆN ĐÀO TẠO QUỐC TẾ BÀI TẬP LỚN HỌC PHẦN: CẤU TRÚC DỮ – StuDocu

Posted on by mtoplistChuyên mục:Top List

Tóm Tắt

HỌC VIỆN NGÂN HÀNG

VIỆN ĐÀO TẠO QUỐC TẾ

BÀI TẬP LỚN

HỌC PHẦN: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT

ĐỀ TÀI: THUẬT TOÁN SHELL SORT

GIẢNG VIÊN HƯỚNG DẪN: Nguyễn Thanh Thụy
THÀNH VIÊN NHÓM:
1. Phạm Lê Kim Chi_J01-
2. Nguyễn Thùy Dương_J01-
3. Dương Quốc Vương_J01-
4. Ngô Hải Yến_J01-

Hà Nội, tháng 1 năm 2021

MỤC LỤ

Phần I: Thuật toán Insertion Sort…………………………………………………………………….

1. Ý tưởng và cài đặt thuật toán……………………………………………………………….

1. Ý tưởng………………………………………………………………………………………
1. Cài đặt thuật toán………………………………………………………………………….

2. Ví dụ minh họa…………………………………………………………………………………..

Phần II: Thuật toán Shell Sort…………………………………………………………………………

Sắp xếp chèn là một thuật toán sắp xếp dựa trên so sánh in-place. Sắp xếp
chèn là chèn thêm một phần tử vào danh sách con đã qua sắp xếp. Phần tử được
chèn vào vị trí thích hợp sao cho vẫn đảm bảo rằng danh sách con đó vẫn sắp theo
thứ tự.
Với cấu trúc dữ liệu mảng, chúng ta tưởng tượng là mảng gồm hai phần: một
danh sách con đã được sắp xếp và phần khác là các phần tử không có thứ tự. Giải
thuật sắp xếp chèn sẽ thực hiện việc tìm kiếm liên tiếp qua mảng đó, và các phần
tử không có thứ tự sẽ được di chuyển và được chèn vào vị trí thích hợp trong danh
sách con (của cùng mảng đó).
Thuật toán này không thích hợp sử dụng với các tập dữ liệu lớn khi độ phức
tạp trường hợp xấu nhất và trường hợp trung bình là Ο(n 2 ) với n là số phần tử.

1. Ý tưởng và cài đặt thuật toán……………………………………………………………….

1. Ý tưởng………………………………………………………………………………………

Bước 1: Khởi tạo mảng với dãy con đã sắp xếp có k = 1 phần tử (phần
tử đầu tiên, phần tử có chỉ số 0)
Bước 2: Duyệt từng phần tử từ phần tử thứ 2, tại mỗi lần duyệt phần tử
ở chỉ số i thì đặt phần tử đó vào một vị trí nào đó trong đoạn từ [0..] sao cho
dãy số từ [0..] vẫn đảm bảo tính chất dãy số tăng dần. Sau mỗi lần duyệt, số
phần tử đã được sắp xếp k trong mảng tăng thêm 1 phần tử.
Bước 3: Lặp cho tới khi duyệt hết tất cả các phần tử của mảng.

1. Cài đặt thuật toán………………………………………………………………………….

Void Insertionsort(int a[], int n)
{
int pos,x;
For (int i = 1; i < n; i++)
{
x = a[i];
pos = i -1;
While (a[pos] > x && pos >= 0)
{
a[pos + 1] = a[pos];
pos–;
}
a[pos + 1] = x;
}
}
2. Ví dụ minh họa
Cho dãy: 3 5 7 1 6 2 4
Dùng thuật toán Insertion sắp xếp dãy trên:

0 1 2 3 4 5 6

i = 7 = n => Kết thúc
Dãy sau khi sắp xếp là: 1 2 3 4 5 6 7

3. Đánh giá thuật toán…………………………………………………………………………….

Trường hợp Số phép so sánh Số phép gán
Tốt nhất 2(n – 1) + 1 3(n – 1)
Xấu nhất n 2 − n ¿ 1 ) n(n + 5)/2 – 3
Trung bình (2n 2 – 1)/2 (n 2 + 8n – 9)/

Phần II: Thuật toán Shell Sort

Shellsort còn được gọi là Shell sort hoặc Shell’s method được đề xuất năm
1959 bởi Donald L. Shell trên tạp chí Communication of the ACM. Nó có thể được
xem như là một sự cải tiến của thuật toán sắp xếp chèn trực tiếp ( Inserttion sort ).
Thuật toán này tránh các trường hợp phải tráo đổi vị trí của hai phần tử xa nhau
trong giải thuật sắp xếp chọn (nếu như phần tử nhỏ hơn ở vị trí bên phải khá xa so
với phần tử lớn hơn bên trái).
1. Ý tưởng và cài đặt thuật toán
3. Ý tưởng
Bước 1: Phân chia dãy ban đầu thành những dãy con gồm các phần tử ở
cách nhau h vị trí.
Bước 2: Tiến hành sắp xếp các phần tử trong cùng dãy con sẽ làm cho các
phần tử được đưa về vị trí đúng tương đối.
Bước 3: Giảm khoảng cách h để tạo thành các dãy con mới. Dừng khi h=1.
Dãy hk cần thỏa mãn 2 điều kiện:

  • hst>hst+
  • hk=
    3. Cài đặt thuật toán
    void ShellSort(int a[],int n,int h[],int k)
    {int st,i,j,x,c;
    for (st=0;st<k;st++)
    { c=h[st];

i = 8 = n = 8 => kết thúc vòng for

Vì x = 5 < a[j] = 6 và j = 0 nên a[3] = 6 và j = j – c = –3;

  • MỞ ĐẦU…………………………………………………………………………………………………….
  • Phần I: Thuật toán Insertion Sort…………………………………………………………………….
      1. Ý tưởng và cài đặt thuật toán……………………………………………………………….
        1. Ý tưởng………………………………………………………………………………………
        1. Cài đặt thuật toán………………………………………………………………………….
      1. Ví dụ minh họa…………………………………………………………………………………..
      1. Đánh giá thuật toán…………………………………………………………………………….
  • Phần II: Thuật toán Shell Sort…………………………………………………………………………
      1. Ý tưởng và cài đặt thuật toán……………………………………………………………….
        1. Ý tưởng………………………………………………………………………………………
        1. Cài đặt thuật toán………………………………………………………………………….
      1. Ví dụ minh họa…………………………………………………………………………………..
      1. Đánh giá thuật toán…………………………………………………………………………..
  • Phần 3: So sánh giữa Shell Sort và Insertion Sort…………………………………………….
      1. So sánh độ phức tạp của hai thuật toán…………………………………………………
      1. Shell Sort là sự cải tiến từ Insertion Sort………………………………………………
  • Phần 4: Những ứng dụng thực tế của Shell Sort………………………………………………
  • KẾT LUẬN……………………………………………………………………………………………….
  • TÀI LIỆU THAM KHẢO……………………………………………………………………………
    – a[0] =

    • Ta có dãy mới là: 6, 2, 8, 5, 1, 12, 4,
      – i = 6 < n = 8 : x = a[6] = 4, j = i – c =
      – Vì x = 4 > a[j] = 2 nên a[6] =
      – i = 7 < n = 8 : x = a[7] = 15, j = i – c =
      – Vì x = 15 > a[j] = 8 nên a[7] =
  • Với st = 1 < k = 3 => c =
    – i = 3 < n = 8 : x = a[3] = 5, j = i – c =
    – a[0] = Vì c = –3 < 0 => thoát vòng lặp while
    – Ta có dãy mới là: 5, 2, 8, 6, 1, 12, 4,
    – i = 4 < n = 8 : x = a[4] = 1, j = i – c =
    – Vì x = 1 < a[j] = 2 và j = 1 > 0 nên a[4] = 2 và j = j – c = –
    – a[1] = Vì c = –2 < 0 => thoát vòng lặp while
    – Ta có dãy mới là: 5, 1, 8, 6, 2, 12, 4,
    – i = 5 < n = 8 : x = a[5] = 12, j = i – c =
    – Vì x = 12 > a[j] = 8 nên a[5] =
    – i = 6 < n = 8 : x = a[6] = 4, j = i – c =
    – Vì x = 4 < a[j] = 6 và j = 3 > 0 nên a[6] = 6 và j = j – c =
    – Vì x = 4 < a[j] = 5 và j = 0 nên a[3] = 5 và j = j – c = –
    – a[0] = Vì j = –3 < 0 => dừng vòng lặp while

    • Ta có dãy mới là: 4, 1, 8, 5, 2, 12, 6,
      • i = 7 < n = 8 : x = a[7] = 15, j = i – c =
        • Vì x = 15 > a[j] = 2 nên a[7] =
  • Với st = 2 < k = 3 => c = i = 8 = n = 8 => kết thúc vòng for
    – i = 1 < n = 8 : x = a[1] = 1, j = i – c =
    – Vì x = 1 < a[j] = 4 và j = 0 nên a[1] = a và j = j – c = –
    – a[0] = Vì j = –1 < 0 => dừng vòng lặp while

    • Ta có dãy mới là: 1, 4, 8, 5, 2, 12, 6,
      • i = 2 < n = 8 : x = a[2] = 8, j = i – c =
        • Vì x = 8 > a[j] = 4 nên a[2] =
      • i = 3 < n = 8 : x = a[3] = 5, j = i – c =
        • Vì x = 5 < a[j] = 8 và j = 2 > 0 nên a[3] = 8 và j = j – c =

Với st = 3 = k = 3 => kết thúc vòng for
Kết thúc chương trình.
Vậy dãy sau khi được sắp xếp là: 1, 2, 4, 5, 6, 8, 12, 15.

3. Đánh giá thuật toán…………………………………………………………………………..

Việc phân tích giải thuật này đặt ra những vấn đề toán học hết sức phức tạp
mà trong đó có một số vấn đề đến nay vẫn chưa được giải quyết.
Vấn đề của thuật toán Shellsort chính là lựa chọn dãy hk như thế nào cho hợp
lý. Người ta chỉ có thể chỉ ra rằng dãy hk này tốt hơn dãy hk kia, chứ không thể xác
định được dãy nào tốt nhất. Tuy nhiên, một số ý kiến cho rằng dãy 1, 4, 10, 23, 57,
132, 301, 701, 1750 là dãy tốt nhất.
Một số kết quả đã chứng minh được:
– Dãy tăng gồm các mũ của 2 là dãy tăng tồi nhất, thời gian thực hiện
bằng thời gian của Insertion Sort.
– Với dãy hk là (2k – 1), (2k + 1) độ phức tạp là O(n3/2) trong trường hợp
xấu nhất.

– Với dãy hk là 4k + 3*2k-1 + 1 độ phức tạp là O(n4/3) trong trường hợp

xấu nhất.
**Lưu ý: các dãy luôn bắt đầu bằng 1.

Phần 3: So sánh giữa Shell Sort và Insertion Sort…………………………………………….

1. So sánh độ phức tạp của hai thuật toán…………………………………………………

Chí phí trung bình cho Insertion Sort là O(n 2 ) trong khi đó chi phí cho Shell
Sort là O(n3/2) hay O(n4/3) tùy thuộc vào việc lựa chọn dãy hk. Rõ ràng chi phí
cho Shell Sort thấp hơn nhiều so với chi phí cho Insertion Sort. Cùng với đó thì
Shell Sort cũng sẽ hoạt động hiệu quả hơn và có hiệu suất cao hơn Insertion
Sort với các tập dữ liệu lớn.
 Bảng phức tạp về thời gian
def shell(a, n):
gap = n / 2
while gap >= 1:
insertion(a, n, gap) # or bubble
gap /= 2

def insertion(a, n, gap = 1):
for i in range (1, n):
x = a[i]
j = i – gap
while j >= 0 and a[j] > x:
a[j + gap] = a[j]
j – = gap

Phần 4: Những ứng dụng thực tế của Shell Sort………………………………………………

Chương trình được đề cập là chương trình cơ sở cho vi điều khiển. Bộ vi điều
khiển phải thu thập khoảng 1000 số nguyên 16 bit từ một cảm biến, và sau đó thực
hiện trích xuất lượng tử. Vì vậy, điều đó có nghĩa là sắp xếp các số nguyên đó 1000
phần tử đủ lớn để bất kỳ thuật toán n2 nào là quá chậm. Bởi vì bộ vi điều khiển có
RAM hạn chế, hầu hết các thuật toán sắp xếp nlogn không thể được sử dụng. Shell
Sort dễ dàng là sự cân bằng tốt nhất cho tình huống này.
Các lập trình viên có kinh nghiệm đôi khi chọn Shell Sort vì nó có thời gian
chạy chấp nhận được ngay cả đối với các mảng lớn vừa phải; nó yêu cầu một
lượng nhỏ mã; và nó không sử dụng thêm không gian. Nếu bạn cần giải pháp cho
vấn đề sắp xếp và đang làm việc trong một tình huống mà sắp xếp hệ thống có thể
không khả dụng (ví dụ: mã dành cho phần cứng hoặc hệ thống nhúng), bạn có thể
sử dụng Shell Sort một cách an toàn, sau đó xác định xem nó có đáng giá để thay
thế cho một phương pháp phức tạp hơn hay không.

TÀI LIỆU THAM KHẢO……………………………………………………………………………

  1. Slide bài giảng môn Cấu trúc dữ liệu và giải thuật – Nguyễn Thanh Thụy
    TỶ LỆ ĐÓNG GÓP CỦA CÁC THÀNH VIÊN TRONG NHÓM:
    Phạm Lê Kim Chi_J01-019: 30%
    Nguyễn Thùy Dương_J01-024: 25%
    Dương Quốc Vương_J01-018: 25%
    Ngô Hải Yến_J01-022: 20%

mtoplist