Lớp 1
Lớp 2
Vở bài tập
Lớp 3
Vở bài tập
Đề kiểm tra
Lớp 4
Sách giáo khoa
Sách/Vở bài tập
Đề kiểm tra
Lớp 5
Sách giáo khoa
Sách/Vở bài tập
Đề kiểm tra
Lớp 6
Sách giáo khoa
Sách/Vở bài tập
Đề kiểm tra
Chuyên đề & Trắc nghiệm
Lớp 7
Sách giáo khoa
Sách/Vở bài tập
Đề kiểm tra
Chuyên đề & Trắc nghiệm
Lớp 8
Sách giáo khoa
Sách/Vở bài tập
Đề kiểm tra
Chuyên đề & Trắc nghiệm
Lớp 9
Sách giáo khoa
Sách/Vở bài tập
Đề kiểm tra
Chuyên đề & Trắc nghiệm
Lớp 10
Sách giáo khoa
Sách/Vở bài tập
Đề kiểm tra
Chuyên đề & Trắc nghiệm
Lớp 11
Sách giáo khoa
Sách/Vở bài tập
Đề kiểm tra
Chuyên đề & Trắc nghiệm
Lớp 12
Sách giáo khoa
Sách/Vở bài tập
Đề kiểm tra
Chuyên đề & Trắc nghiệm
IT
Ngữ pháp Tiếng Anh
Lập trình Java
Phát triển web
Lập trình C, C++, Python
Cơ sở dữ liệu
Cấu trúc dữ liệu và giải thuậtMột số khái niệm về Giải thuật Cấu trúc dữ liệu mảng (Array)Danh sách liên kết – Linked ListsNgăn xếp & Hàng đợiMột số Giải thuật tìm kiếmMột số Giải thuật sắp xếpCấu trúc dữ liệu đồ thị (Graph)Cấu trúc dữ liệu câyĐệ qui (Recursion)Tài liệu tham khảo
Shell Sort trong cấu trúc dữ liệu và giải thuật
Trang trước
Trang sau
Shell Sort là gì ?
Shell Sort là một giải thuật sắp xếp mang lại hiệu quả cao dựa trên giải thuật sắp xếp chèn (Insertion Sort). Giải thuật 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).
Bạn đang xem: Shell sort là gì
Đầu tiên, giải thuật này sử dụng giải thuật sắp xếp chọn trên các phần tử có khoảng cách xa nhau, sau đó sắp xếp các phần tử có khoảng cách hẹp hơn. Khoảng cách này còn được gọi là khoảng (interval) – là số vị trí từ phần tử này tới phần tử khác. Khoảng này được tính dựa vào công thức Knuth như sau:
h = h * 3 + 1trong đó: h là Khoảng (interval) với giá trị ban đâu là 1Giải thuật này khá hiệu quả với các tập dữ liệu có kích cỡ trung bình khi mà độ phức tạp trường hợp xấu nhất và trường hợp trung bình là O(n), với n là số phần tử.
Cách Shell Sort làm việc
Để dễ tìm hiểu hơn, dưới đây mình cung cấp các hình minh họa cho cách Shell Sort làm việc. Chúng ta sử dụng một mảng gồm các giá trị như dưới đây. Giả sử ban đầu giá trị Khoảng (interval) là 4. Ví dụ, với phần tử 35 thì với khoảng là 4 thì phần tử còn lại sẽ là 14. Do đó ta sẽ có các cặp giá trị {35, 14}, {33, 19}, {42, 27}, và {10, 14}.
So sánh các giá trị này với nhau trong các danh sách con và tráo đổi chúng (nếu cần) trong mảng ban đầu. Sau bước này, mảng mới sẽ trống như sau:
Sau đó, lấy giá trị Khoảng (interval) là 2 và với khoảng cách này sẽ cho hai danh sách con: {14, 27, 35, 42}, {19, 10, 33, 44}.
Tiếp tục so sánh và tráo đổi các giá trị (nếu cần) trong mảng ban đầu. Sau bước này, mảng sẽ trông như sau:
Cuối cùng, chúng ta sắp xếp phần mảng còn lại này với Khoảng (interval) bằng 1. Shell Sort sử dụng giải thuật sắp xếp chèn để sắp xếp mảng. Dưới đây là hình minh họa cho từng bước.
Xem thêm: Quy Chuẩn Là Gì – Quy Chuẩn Kỹ Thuật
Như trên các hình trên, bạn thấy rằng chúng ta chỉ cần 4 lần tráo đổi để sắp xếp phần mảng còn lại này.
Giải thuật cho Shell Sort
Bây giờ chúng ta sẽ theo dõi giải thuật cho Shell Sort:
Bước 1: Khởi tạo giá trị hBước 2: Chia list thành các sublist nhỏ hơn tương ứng với hBước 3: Sắp xếp các sublist này bởi sử dụng sắp xếp chèn (Insertion Sort)Bước 4: Lặp lại cho tới khi list đã được sắp xếp
Giải thuật mẫu cho Shell Sort
Từ các bước trên chúng ta có thể thiết kế một giải thuật mẫu cho Shell Sort như sau:
Bắt đầu hàm shellSort() A : mảng các phần tử /* Tính toán giá trị Khoảng (interval)*/ while interval 0 thực hiện: for outer = interval; outer interval -1 && A >= valueToInsert do: A = A inner = inner – interval kết thúc while /* chèn giá trị vào vị trí trên */ A = valueToInsert kết thúc for /* Tính toán giá trị Khoảng (interval)*/ interval = (interval -1) /3; kết thúc while Kết thúc hàm
Để theo dõi code đầy đủ của giải thuật Shell Sort trong ngôn ngữ C, mời bạn click chuột vào chương: Shell Sort trong C.
Đã có app thienmaonline.vn trên điện thoại, giải bài tập SGK, SBT Soạn văn, Văn mẫu, Thi online, Bài giảng….miễn phí. Tải ngay ứng dụng trên Android và iOS.
Xem thêm: 097 Là Mạng Gì – Thông Tin Hữu ích Về Sim 097
Follow fanpage của team https://www.facebook.com/thienmaonline.vnteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.thienmaonline.vn để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile…. mới nhất của chúng tôi.
Chuyên mục: Hỏi Đáp
