Sắp xếp học tập Sắp xếp theo Ruby

Question

Tôi vừa mới bắt đầu khóa học Giới thiệu về thuật toán của MIT thông qua tài liệu được đăng trực tuyến. Cùng với khóa học, tôi cũng đã quyết định học/nâng cao kỹ năng Ruby của mình bằng cách mã hóa các thuật toán trong đó.

Tôi đang trên thuật toán đầu tiên được đưa ra, đó là Sắp xếp chèn, và tôi đã gõ đoạn mã sau lên nhưng tôi nhận được lỗi này khi tôi chạy nó:

insertionsort.rb: 5: trong ` > ': so sánh Fixnum với con số không thất bại (ArgumentError)

def insertionsort(num) 
for j in 2..num.length 
    key = num[j] 
    i = j - 1 
    while i > 0 and num[i] > key 
     num[i+1] = num[i] 
     i = i - 1 
    end 
    num[i+1] = key 
end 
puts num 
end 

numbers = [23,34,46,87,12,1,66] 

insertionsort(numbers) 

tôi chắc chắn rằng nó là một vấn đề khá cơ bản nhưng tôi chỉ không thể nắm bắt nó là gì vào lúc này. Bất kỳ trợ giúp hoặc lời khuyên nào sẽ được đánh giá rất nhiều.

Answer 1

Bạn đang vượt quá giới hạn mảng của mình. Ví dụ bạn đã đưa ra là giả sử các mảng được lập chỉ mục 1, nhưng các mảng trong ruby ​​là 0 được lập chỉ mục. Dòng đầu tiên phải là

for j in 1...num.length 

Answer 2

Câu trả lời khác chính xác là bạn sẽ vượt quá cuối giá trị trong mảng vì giá trị này dựa trên 0 nhưng có những thay đổi khác bạn cần thực hiện để làm cho thuật toán hoạt động :

for j in 1..(num.length - 1) 

và

while i >= 0 and num[i] > key 

Answer 3

Chỉ cần một sự bổ sung nhỏ cho khác, câu trả lời tuyệt vời:

Tôi nghĩ rằng bây giờ thường được chấp nhận rằng chỉ mục 0 nguồn gốc có một số lợi thế thực tế và thực nghiệm so với chỉ mục 1 nguồn gốc. Kinh nghiệm cho thấy rằng nó chỉ "hoạt động tốt hơn" và ít bị lỗi hơn.

Đó là lý do tại sao nhiều lập trình viên đánh số thứ từ số không và những người "bình thường" kinh ngạc.

Answer 4

Trong khi bài tập này là thực sự mát mẻ, theo bài đăng blog tuyệt vời có lẽ bạn nên tránh phải viết loại của riêng bạn và dựa vào việc xây dựng trong mảng :: sort

http://philcrissman.com/2010/07/18/how-not-to-write-sorting-algorithms-in-ruby/

Answer 5

Việc thực hiện đơn giản nhất là một cái gì đó như này:

def insertion_sort(arr) 
    for i in (1...(arr.size)) 
    if arr[i-1] > arr[i] 
     i.downto(1) do |el| 
     if arr[el] < arr[el-1] 
      arr[el-1], arr[el] = arr[el], arr[el-1] 
     end 
     end 
    end 
    end 
    arr 
end 

arr = [5, 2, 4, 6, 1, 3] 

p insertion(arr) 

Lưu ý: để cải thiện hiệu quả của thuật toán bạn có thể sử dụng tìm kiếm nhị phân để so sánh các phần tử.

What Is Insertion Sort ?