Shell sort là một kỹ thuật sắp xếp, nó phân chia một danh sách nhất định thành các danh sách con và sau đó sắp xếp chúng bằng cách sử dụng insertion sort (sắp xếp chèn). Thuật toán sử dụng khoảng trống n để chọn các mục cách nhau n khoảng trống để tạo thành danh sách con.
Các danh sách con sau đó được sắp xếp bằng cách sử dụng insertion sort, rồi được kết hợp với nhau. Danh sách kết hợp không được sắp xếp hoàn toàn nhưng giúp thuật toán này có lợi thế là có các mục (items) gần vị trí cuối cùng của chúng hơn.
insertion sort một lần nữa được sử dụng để sắp xếp danh sách cuối cùng.
1. Tìm hiểu kỹ hơn về Shell sort
Mô tả ở trên có thể không có nhiều ý nghĩa, nhưng một ví dụ sẽ hữu ích. Giả sử bạn có danh sách: [39, 6, 2, 51, 30, 42, 7, 4, 16] và giá trị khoảng cách (gap value) là 3.
Danh sách phụ đầu tiên sẽ có các mục: 39, 51, 7
Danh sách phụ thứ hai: 6, 30, 4
Danh sách phụ thứ ba & cuối cùng: 2, 42, 16
Sau khi insertion sort, mỗi danh sách con sẽ được sắp xếp như sau:
Đầu tiên: 7, 39, 51
Thứ hai: 4, 6, 30
Thứ ba: 2, 16, 42
Danh sách con đã được sắp xếp hiện được kết hợp theo một cách nhất định. Mỗi mục (item) trong danh sách con được đưa vào chỉ mục (index) mà từ đó giá trị danh sách con chưa được sắp xếp ban đầu được tập hợp.
Do đó, bạn sẽ kết thúc với trình tự bên dưới:
[7, 4, 2, 39, 6, 16, 51, 30, 42]Lưu ý rằng danh sách vẫn chưa được sắp xếp nhưng các mục đã ở gần vị trí cuối cùng của chúng hơn. Sau khi thực hiện insertion sort trên tổ hợp danh sách này, danh sách cuối cùng cũng được sắp xếp:
[2, 4, 6, 7, 16, 30, 39, 42, 51]>>> Đọc ngay: 4 con đường sự nghiệp cho các nhà phân tích dữ liệu (Data Analyst)
1.1 Phân tích thuật toán
Độ phức tạp của shell sort nằm giữa O (n) và O (n2). Việc tính toán để đi đến kết luận này nằm ngoài phạm vi của bài viết này.
1.2 Triển khai Python:
def shellSort(my_list):
n = len(my_list)
interval = n // 2 # floor division
while interval > 0:
for val in range(interval, n):
temp = my_list[val]
x = val
while x >= interval and my_list[x - interval] > temp:
my_list[x] = my_list[x - interval]
x = x - interval
my_list[x] = temp
interval = interval // 2 >>> Đọc ngay: Nghề phân tích dữ liệu data analysis tại Việt Nam
2. Chuyển sang Merge sort
Mỗi thuật toán sắp xếp có một cơ chế hoạt động riêng. Ví dụ, merge sort (sắp xếp hợp nhất) sử dụng chiến lược ‘chia để trị’ và có độ phức tạp là O (nlogn).
Merge sort, trong một số trường hợp, tốt hơn shell sort và chắc chắn đáng để xem xét.
>>> Nếu bạn đang có nhu cầu học lập trình trực tuyến, tìm hiểu ngay tại đây:
>>>Xem thêm bài viết liên quan:
Phân tích dữ liệu kinh doanh là làm gì năm 2022
Data analyst là gì? Tất cả những gì cần biết về nghề phân tích dữ liệu Data analyst
Trang bị Kỹ năng phân tích dữ liệu cho người mới
Nhà phân tích dữ liệu làm gì: mô tả, trách nhiệm?
Nghề phân tích dữ liệu sử dụng công cụ nào? Kiến thức cho dân IT cần phải biết
Phân biệt vai trò dữ liệu: Kỹ sư, nhà phân tích và nhà khoa học
Cách trở thành chuyên viên phân tích dữ liệu
Vân Nguyễn
Dịch từ: https://www.makeuseof.com/intro-to-shell-sort/
Bình luận (0
)