Lưu ý:Đây là phần 4 trong loạt bài về việc triển khai các thuật toán sắp xếp khác nhau với Ruby. Phần 1 khám phá sắp xếp bong bóng, phần 2 khám phá sắp xếp lựa chọn và phần 3 khám phá sắp xếp hợp nhất.
Khi chúng tôi 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 tôi chuyển sang sắp xếp chèn. Có một số lý do để thích sắp xếp chèn! Đầu tiên, sắp xếp chèn là ổn định , có 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 tại chỗ , nghĩa là nó không tạo một mảng mới để lưu trữ các phần tử đã được sắp xếp. Cuối cùng, sắp xếp chèn 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 lại quan tâm
Thật khó để tránh nghe giống như một kỷ lục bị phá vỡ ở đây, nhưng như chúng ta đã thảo luận trong tất cả các bài viết trước, điều quan trọng là phải hiểu các cơ chế khác nhau để sắp xếp dữ liệu và sự đánh đổi là gì với mỗi phương pháp khác nhau. Ví dụ:trong khi sắp xếp chèn không hữu ích lắm cho các tập dữ liệu lớn (chúng ta sẽ khám phá thêm điều này bên dưới), nhưng nó có thể tốt và khá hiệu quả cho các tập dữ liệu nhỏ và những tập đã gần được sắp xếp. Bạn sẽ tìm hiểu lý do tại sao sau khi chúng tôi xem xét việc triển khai. Chắc chắn, bạn sẽ thường sử dụng các phương pháp tích hợp sẵn mà ngôn ngữ lập trình mà bạn lựa chọn cung cấp để sắp xếp, nhưng nó chỉ có thể xuất hiện dưới dạng câu hỏi phỏng vấn như một bài tập chương trình cặp hoặc có thể liên quan đến độ phức tạp về thời gian. May mắn thay, vào thời điểm chúng tôi thực hiện xong bài đăng này, bạn sẽ có thể viết mã một loại chèn và hiểu sự phức tạp về thời gian một cách dễ dàng.
Trình bày bằng hình ảnh
Trước khi chúng ta bắt đầu viết mã, tôi thực sự khuyên bạn nên xem video sau. Nó giải thích việc sắp xếp chèn bằng cách sử dụng một điệu nhảy, và cá nhân tôi, tôi không thể hiểu đủ về nó! :)
Hướng dẫn từng bước về mã
Hãy xem mã!
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 tôi bắt đầu bằng for vòng lặp đặt biến i đến 1 và tiếp tục tăng cho đến khi i bằng độ dài của mảng của chúng ta.
Bước 2:
Chúng tôi tạo một biến khác j và khởi tạo nó với giá trị 1 (vì đó là i là).
Bước 3:
Tiếp theo, chúng ta có while lồng nhau vòng lặp 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 tôi biết điều này sẽ thực thi ít nhất một lần.
Bước 4:
if... else khối có thể trông đáng sợ lúc đầu, nhưng đừng lo lắng. Sẽ có ý nghĩa khi chúng ta xem qua nó (và bạn luôn có thể xem lại ví dụ về khiêu vũ trên YouTube!).
Đối với if điều kiện, chúng tôi kiểm tra xem [j-1] lớn hơn array[j] . Kể từ j hiện là 1, về cơ bản chúng tôi sẽ so sánh array[0] với array[1] . Điều này có ý nghĩa vì chúng tôi đ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 cái 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 if khối. Tuy nhiên, nếu giá trị trong array[0] nhỏ hơn giá trị trong array[1] , sau đó tuyệt vời! Chúng tôi không cần phải làm bất cứ điều gì vì nó đã được sắp xếp, vì vậy chúng tôi chỉ cần nhấn break trong else khối.
Bước 5:
Từ đây, chúng tôi giảm j . Bây giờ, chúng ta quay lại for vòng lặp và i bây giờ sẽ là 2 . Bạn có thể tưởng tượng cách chúng ta sẽ so sánh array[1] với array[2] cho lần lặp đầu tiên trong while và sau đó chúng ta sẽ thực sự đi qua while lặp lại vì j của chúng tôi bắt đầu lúc 2 so với 1 .
Ví dụ với Dữ liệu Thực
Hãy xem qua đoạn mã này bằng cách sử dụng mảng ví dụ sau:[5,7,2,10,9,12]
Trong lần lặp đầu tiên, chúng tôi sẽ so sánh 5 và 7 . Kể từ 5 < 7 , chúng tôi nhanh chóng thoát ra khỏi if/else và tiếp tục.
Trong lần lặp tiếp theo, chúng tôi 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 một lần nữa với 5 để kết thúc bằng [2, 5, 7, 10, 9, 12] .
Trong lần lặp tiếp theo trong for vòng lặp, chúng tôi sẽ so sánh 10 và 7 - Yay! Chúng đã được đặt hàng.
Tiếp tục, chúng tôi so sánh 10 và 9 và thấy rằng chúng ta cần phải hoán đổi. Sau đó, 7 nhỏ hơn 9 , vì vậy chúng tôi sẽ không phải thực hiện bất kỳ hoán đổi nào khác. Bây giờ chúng ta còn lại [2, 5, 7, 9, 10, 12] .
Lần lặp cuối cùng tìm thấy 12 , lớn hơn 10 , vậy thì đấy! Chúng tôi đã hoàn thành và sắp xếp.
Phân tích hiệu suất
Mặc dù một số thuật toán sắp xếp mà chúng tôi đã xem xét, cụ thể là sắp xếp bong bóng, rất hiếm khi được thực hành trong cuộc sống thực, nhưng sắp xếp chèn 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 - sắp xếp chèn sẽ chạy rất nhanh và hiệu quả. Mặt khác, điều gì sẽ xảy ra nếu chúng ta cần sắp xếp một mảng theo thứ tự ngược lại. Đó sẽ là một tình huống ác mộng đối với việc sắp xếp chèn.
Nếu mảng đã được sắp xếp, mã sắp xếp chèn sẽ chạy tại O(n) vì nó sẽ chỉ phải lặp qua n lần. Nếu bạn muốn giải quyết vấn đề này, hãy thêm puts i ở đầu phương thức và chạy chương trình truyền vào một mảng đã được sắp xếp.
Nếu mảng được sắp xếp ngược lại, mã sắp xếp chèn sẽ chạy ở O(n^2) Bạn có thể hình dung điều này trong đầu. Vì nó sẽ phải thực hiện các hoán đổi liên tiếp, nó sẽ chạm vào if điều kiện cho mọi phần tử đơn lẻ. Rất tiếc! Một lần nữa, hãy thử điều này bằng cách chuyển vào một mảng được sắp xếp ngược và tạo một biến bộ đếm được in ra.
Mặc dù trường hợp xấu nhất là O(n^2) như bạn có thể nhớ lại, sắp xếp bong bóng và sắp xếp lựa chọn giống nhau, sắp xếp chèn thường được ưu tiên hơn. Điều này là do, như chúng ta đã thấy, trường hợp tốt nhất có thể là O(n) , trong khi trường hợp tốt nhất để sắp xếp lựa chọn là O(n^2) . Loại chèn cũng có ít hoán đổi hơn so với loại bong bóng, vì vậy nó sẽ thắng trận chiến này.
Kết thúc
Tôi hy vọng rằng bài đăng này hữu ích và bạn cảm thấy tự tin về việc hiểu những ưu và nhược điểm của sắp xếp chèn, cũng như cách thuật toán hoạt động. Nếu bạn vẫn muốn tìm hiểu thêm, tôi khuyên bạn nên xem trang wikipedia để biết sắp xếp chèn.