Lưu ý: Đây là phần 2 của loạt bài xem xét các thuật toán sắp xếp với Ruby. Phần 1 khám phá bubble sort.
Trong bài này, tôi sẽ hướng dẫn cách triển khai thuật toán selection sort với Ruby. Selection sort là thuật toán sắp xếp so sánh in-place. Nghĩa là các item đã sắp xếp chiếm cùng bộ nhớ với các item gốc. Trước khi đi xa, quan trọng lưu ý selection sort không thường dùng thực tế trừ khi dataset nhỏ (10-20 phần tử). Tuy nhiên, nó là thuật toán khởi đầu tuyệt vời để học và hiểu, giống như học xe ba gác trước xe hai gác. Triển khai có thể xuất hiện trong coding challenge phỏng vấn, hoặc bạn có thể được hỏi tại sao thuật toán như selection sort không thực tế cho dataset lớn. Selection sort thường vượt trội hơn bubble sort, thuật toán đầu tiên chúng ta xem trong loạt bài.
Ở mức cao, selection sort chia mảng thành hai phần: một nửa đã sắp xếp và nửa chưa. Ban đầu, phần đã sắp xếp rỗng, phần chưa sắp xếp chứa tất cả phần tử. Selection sort dùng hai vòng lặp; vòng ngoài lặp n lần, n là số phần tử. Chúng ta ngay lập tức đặt "min index" là phần tử đầu, rồi dùng vòng lặp khác so sánh, đổi min index nếu phần tử liền kề nhỏ hơn min hiện tại.
Nếu khó theo dõi, đừng lo! Chúng ta sẽ đi qua ví dụ thực tế ngay. :)
Từng bước
Bắt đầu với mảng các phần tử: [10, 30, 27, 7, 33, 15, 40, 50]
Vòng lặp một: Tìm số nhỏ nhất
Trong trường hợp này, số nhỏ nhất là 7, đặt nó lên đầu và di chuyển 10 đến vị trí 7. Mảng giờ: [7, 30, 27, 10, 33, 15, 40, 50]
Vòng lặp hai: Tìm số nhỏ nhất tiếp theo
Bắt đầu tại phần tử vị trí index 1 (nhớ mảng 0-indexed), tìm phần tử nhỏ nhất tiếp theo
Trong trường hợp này là 10. Di chuyển 10 đến vị trí thứ hai và 30 đến vị trí 10 cũ. Mảng kết quả: [7, 10, 27, 30, 33, 15, 40, 50]
Từ đây, tiếp tục quy trình chính xác cho đến khi mảng sắp xếp xong. Dưới đây mảng kết quả sau các vòng lặp tiếp theo.
Vòng lặp ba:
[7, 10, 15, 30, 33, 27, 40, 50]
Vòng lặp bốn:
[7, 10, 15, 27, 33, 30, 40, 50]
Vòng lặp năm:
[7, 10, 15, 27, 30, 33, 40, 50]
Xong! Đã sắp xếp!
Nếu bạn học tốt bằng hình ảnh, đây là ví dụ selection sort với mảng []
Nguồn ảnh
Triển khai Ruby
Đây là hàm selection sort viết bằng Ruby:
def selection_sort(array) n = array.length - 1 n.times do |i| min_index = i for j in (i + 1)..n min_index = j if array[j] < array[min_index] end array[i], array[min_index] = array[min_index], array[i] if min_index != i end puts array end Hãy xem cách hoạt động.
Đầu tiên, đặt n bằng số phần tử. Nhớ trừ 1 vì mảng 0-indexed.
Tiếp, tạo vòng lặp ngoài, chạy n lần.
min_index = i Ở đây, đặt minimum index là phần tử vị trí đầu.
for j in (i + 1)..n Tiếp, tạo vòng lặp trong. Dòng này nghĩa là "với phần tử vị trí thứ hai đến phần tử thứ n, làm theo". Nếu không quen toán tử .., nó tạo range từ điểm bắt đầu đến điểm kết thúc, bao gồm cả hai. Ví dụ, 1..10 tạo range 1 đến 10 inclusive.
min_index = j if array[j] < array[min_index] Bên trong vòng lặp, đặt min_index thành phần tử mới nếu nó nhỏ hơn min_index hiện tại.
array[i], array[min_index] = array[min_index], array[i] if min_index != i Bên ngoài vòng lặp trong, kiểm tra min_index hiện tại có bằng i không. Nếu đúng, cần đổi chỗ phần tử. Gán array[i] thành array[min_index] và array[min_index] thành array[i]. Ở đây, thực hiện "swap" như ví dụ.
Cuối cùng, khi xong, output mảng, giờ đã sắp xếp!
Tổng hợp
Đây là chương trình đầy đủ:
def selection_sort(array) n = array.length - 1 n.times do |i| min_index = i for j in (i + 1)..n min_index = j if array[j] < array[min_index] end array[i], array[min_index] = array[min_index], array[i] if min_index != i end puts array end array = [10, 30, 27, 7, 33, 15, 40, 50] selection_sort(array) Chạy ruby ruby-selection-sort.rb từ terminal cho output:
7 10 15 27 30 33 40 50 Tuyệt!
Hiểu tại sao Selection Sort kém hiệu quả
Cách đo hiệu quả thuật toán là xem "ký pháp Big-O"; đại diện hiệu năng xấu nhất để so sánh thuật toán. Ví dụ, thuật toán Big-O O(1) nghĩa là runtime xấu nhất không đổi khi số phần tử "n" tăng, trong khi O(n) nghĩa là runtime xấu nhất tăng tuyến tính với n. Nghĩa là nếu mảng 100 phần tử và phải chọn giữa thuật toán O(n) và O(1), bạn chọn O(1) vì O(1) chắc chắn thắng O(100).
Giống bubble sort, selection sort có độ phức tạp xấu nhất và trung bình O(n^2) do vòng lặp lồng. Nghĩa là hiệu quả giảm mạnh khi số phần tử tăng.
Kết luận
Tóm lại, selection sort vẫn là thuật toán thú vị có thể xuất hiện trong coding challenge. Hoặc bạn có thể nhận hàm selection sort và được hỏi Big-O là gì và tại sao. Hy vọng ví dụ trong bài giúp bạn sẵn sàng xử lý cả hai kịch bản.