Lưu ý: Đây là phần 4 trong series xem xét việc triển khai các thuật toán sắp xếp với Ruby. Phần 1 khám phá bubble sort, phần 2 khám phá selection sort, và phần 3 khám phá merge sort.
Khi chúng ta tiếp tục khám phá các phương pháp khác nhau để sắp xếp dữ liệu, chúng ta chuyển sang sắp xếp chèn (insertion sort). Có một số lý do để thích insertion sort! Trước tiên, insertion sort là ổn định (stable), nghĩa là nó không thay đổi thứ tự tương đối của các phần tử có khóa bằng nhau. Nó cũng là một thuật toán in-place, nghĩa là nó không tạo mảng mới để lưu trữ các phần tử đã sắp xếp. Cuối cùng, insertion sort là một thuật toán khá đơn giản để triển khai, như bạn sẽ sớm thấy!
Tại Sao Phải Quan Tâm
Khó tránh khỏi nghe như đĩa vỡ ở đây, nhưng như chúng ta đã thảo luận trong tất cả các bài trước, việc hiểu các cơ chế khác nhau để sắp xếp dữ liệu và trade-off của mỗi phương pháp là quan trọng. Ví dụ, trong khi insertion sort không quá hữu ích cho tập dữ liệu lớn (chúng ta sẽ khám phá thêm dưới đây), nó có thể hoàn toàn ổn và khá hiệu quả cho tập dữ liệu nhỏ và những tập dữ liệu đã gần như được sắp xếp. Bạn sẽ hiểu tại sao khi chúng ta đi qua triển khai. Chắc chắn, bạn thường dùng các phương thức built-in mà ngôn ngữ lập trình bạn chọn cung cấp cho việc sắp xếp, nhưng nó có thể xuất hiện như câu hỏi phỏng vấn dưới dạng bài tập pair-programming hoặc có liên quan đến độ phức tạp thời gian. May mắn thay, khi chúng ta xong bài này, bạn sẽ có thể vừa code insertion sort vừa hiểu độ phức tạp thời gian dễ dàng.
Biểu Diễn Trực Quan
Trước khi bắt đầu code, tôi khuyên mạnh mẽ bạn nên xem video sau. Nó giải thích insertion sort bằng một điệu múa, và cá nhân tôi không thể lấy được đủ nó! :)
Duyệt Qua Code Bước Đi Từng Bước
Hãy nhìn vào code!
def insertion_sort(array)
for i in 1...(array.length)
# Step 1
j = i
# Step 2
while j > 0
# Step 3
if array[j-1] > array[j]
# Step 4
temp = array[j]
array[j] = array[j-1]
array[j-1] = temp
else
break
end
j = j - 1
# Step 5
end
end
return array
end
Bước 1:
Chúng ta bắt đầu với vòng lặp for thiết lập biến i thành 1 và tiếp tục tăng cho đến khi i bằng độ dài mảng của chúng ta.
Bước 2:
Chúng ta tạo biến khác j và khởi tạo nó với giá trị 1 (vì đó là giá trị của i).
Bước 3:
Tiếp theo, chúng ta có một vòng lặp while lồng nhau sẽ tiếp tục miễn là j lớn hơn 0. Vì chúng ta bắt đầu với j bằng 1, chúng ta biết điều này sẽ thực thi ít nhất một lần.
Bước 4:
Khối if... else có vẻ đáng sợ lúc đầu, nhưng đừng lo. Nó sẽ có ý nghĩa khi chúng ta đi qua nó (và bạn luôn có thể quay lại ví dụ YouTube điệu múa!).
Đối với điều kiện if, chúng ta kiểm tra xem [j-1] có lớn hơn array[j] không. Vì j hiện tại là 1, chúng ta về cơ bản đang so sánh array[0] với array[1]. Điều này hợp lý vì chúng ta đang so sánh hai phần tử đầu tiên của mảng.
Nếu phần tử đầu tiên (array[0]) lớn hơn phần tử tiếp theo (array[1]), thì tất nhiên chúng ta cần hoán đổi, đó là những gì xảy ra trong khối if. Tuy nhiên, nếu giá trị trong array[0] nhỏ hơn giá trị trong array[1], thì tuyệt! Chúng ta không cần làm gì vì nó đã được sắp xếp, nên chúng ta chỉ cần hit break trong khối else.
Bước 5:
Từ đây, chúng ta giảm j. Bây giờ, chúng ta quay lại vòng lặp for, và i giờ sẽ là 2. Bạn có thể tưởng tượng chúng ta sẽ so sánh array[1] với array[2] cho lần lặp đầu tiên trong vòng lặp while, và sau đó chúng ta thực sự sẽ đi qua vòng lặp while lại vì j bắt đầu ở 2 so với 1.
Ví Dụ Với Dữ Liệu Thực
Hãy đi qua code này sử dụng mảng ví dụ sau: [5,7,2,10,9,12]
Trong lần lặp đầu tiên, chúng ta sẽ so sánh 5 và 7. Vì 5 < 7, chúng ta nhanh chóng break khỏi if/else và tiếp tục.
Trong lần lặp tiếp theo, chúng ta so sánh 7 và 2. Bây giờ, các giá trị này sẽ cần được hoán đổi, vì vậy chúng ta sẽ có [5, 2, 7, 10, 9, 12]. Sau đó, chúng ta sẽ hoán đổi 2 lại với 5 để kết thúc với [2, 5, 7, 10, 9, 12].
Trong lần lặp tiếp theo trong vòng lặp for, chúng ta sẽ so sánh 10 và 7 -- Yay! Chúng đã theo thứ tự.
Tiếp tục, chúng ta so sánh 10 và 9 và thấy rằng chúng ta cần hoán đổi. Sau đó, 7 nhỏ hơn 9, vì vậy chúng ta sẽ không phải thực hiện hoán đổi nào khác. Chúng ta giờ còn lại với [2, 5, 7, 9, 10, 12].
Lần lặp cuối tìm thấy 12, lớn hơn 10, vì vậy voila! Chúng ta xong và đã sắp xếp.
Phân Tích Hiệu Suất
Trong khi một vài thuật toán sắp xếp chúng ta đã xem, đặc biệt là bubble sort, rất hiếm khi được thực hành trong đời thực, insertion sort có thể là một giải pháp hợp lý. Hãy tưởng tượng nếu mảng của chúng ta đã được sắp xếp -- insertion sort sẽ chạy rất nhanh và hiệu quả. Mặt khác, điều gì xảy ra nếu chúng ta cần sắp xếp một mảng theo thứ tự ngược. Đó sẽ là một cơn ác mộng cho insertion sort.
Nếu mảng đã được sắp xếp, code insertion sort sẽ chạy ở O(n) vì nó chỉ phải lặp qua n lần. Nếu bạn muốn chứng minh điều này, thêm puts i ở đầu phương thức và chạy chương trình truyền vào mảng đã sắp xếp.
Nếu mảng được sắp xếp ngược, code insertion sort sẽ chạy ở O(n^2). Bạn có thể hình dung điều này trong đầu. Vì nó phải thực hiện hoán đổi liên tiếp, nó sẽ hit điều kiện if cho mọi phần tử đơn lẻ. Yikes! Lại lần nữa, thoải mái thử bằng cách truyền mảng sắp xếp ngược và tạo biến đếm được in ra.
Mặc dù worst case là O(n^2), mà, như bạn có thể nhớ, giống hệt bubble sort và selection sort, insertion sort thường ưu tiên hơn. Điều này là vì, như chúng ta đã thấy, best case có thể là O(n), trong khi best case cho selection sort là O(n^2). Insertion sort cũng có ít hoán đổi hơn bubble sort, vì vậy nó thắng trận này.
Tổng Kết
Tôi hy vọng bài viết này hữu ích và bạn cảm thấy tự tin về việc hiểu ưu và nhược điểm của insertion sort, cũng như cách thuật toán hoạt động. Nếu bạn vẫn thèm thêm, tôi khuyên bạn nên xem trang Wikipedia về insertion sort.