The Ultimate Guide to Ruby Sorting

Có bao nhiêu cách để sắp xếp mảng trong Ruby Mặc dù Array chỉ có 2 methods sắp xếp là sort & sort_by, nhưng các method này có thể kết hợp sử dụng với block để cho ra nhiều cách sắp xếp khác nhau. Tôi muốn chia sẻ với các bạn 1 số ví dụ trong bài viết này. Và bạn cũng có thể thực hiện một phương thức sắp xếp của bạn sử dụng thuật toán quick-sort ở cuối bài.

Basic Sorting

Method cơ bản nhất của việc sắp xếp trong Ruby là sort. Nó được định nghĩa trong Enumerable module

numbers = [5,3,2,1]
numbers.sort
# [1,2,3,5]

sort trả về kết quả là một mảng mới. Hoặc có thể dùng sort! để sửa ngay trên mảng hiện tại mà không tạo ra mảng mới.

Customized Sorting

Bây giờ chúng ta hãy xem loại sắp xếp nâng cao hơn một chút. Với sort_by

strings = %w(foo test blog a)
 
strings.sort_by(&:length)
 
# ["a", "foo", "test", "blog"]

Hoặc sort

strings = %w(foo test blog a)
 
strings.sort { |a,b| a.length <=> b.length }
 
# ["a", "foo", "test", "blog"]

Ở đây mình khuyên dùng sort_by bởi vì nhìn rõ ràng hơn và tốc độ có nhanh hơn một chút.

Reverse Sort

Để reverse sort bạn có thể sử dụng reverse method sau khi sorting. Hoặc 1 cách khác như sau.

strings = %w(foo test blog a)
 
strings.sort_by { |str| -str.length }
 
# ["blog", "test", "foo", "a"]

Alphanumeric Sorting

Bạn muốn sắp xếp 1 mảng các string có chứa numbers

music = %w(21.mp3 10.mp3 5.mp3 40.mp3)

Sử dụng method sort

music.sort
 
# ["10.mp3", "21.mp3", "40.mp3", "5.mp3"]

Đây không phải là kết qủa chúng ta mong đợi. Đây là cách chúng ta sắp xếp với trường hợp này.

music.sort_by { |s| s.scan(/d+/).first.to_i }
 
# ["5.mp3", "10.mp3", "21.mp3", "40.mp3"]

Sorting Hashes

Chúng ta cũng có thể sort trên hash tương tự như với array.

hash = {coconut: 200, orange: 50, bacon: 100}
 
hash.sort_by(&:last)
 
# [[:orange, 50], [:bacon, 100], [:coconut, 200]]

Kết quả sắp xếp đúng và trả về dạng mảng đa chiều. Chúng ta có thể chuyển về dạng hash bằng cách sử dụng Array#to_h

QuickSort Implementation

Bây giờ chúng ta sẽ implement 1 phương thức sắp xếp riêng của chúng ta, có thể sẽ chậm hơn method sort, nhưng nó sẽ khá thú vị để học.

def quick_sort(list)
  qsort_helper(list).flatten
end
 
def qsort_helper(list)
  return [] if list.empty?
 
  number        = list.sample
  lower, higher = list.partition { |n| n < number }
 
  higher.delete_at(higher.index(number))
 
  [qsort_helper(lower), number, qsort_helper(higher)]
end
 
p quick_sort [3, 7, 2, 1, 8, 12]
 
# [1, 2, 3, 7, 8, 12]

Ý tưởng của Quick sort là chọn ngẫu nhiên 1 số M trong mảng, chia mảng thành 2 phần. 1 phần có các giá trị nhỏ hơn M và 1 phần có giá trị lớn hơn hoặc bằng M. Và sẽ tiếp tục lặp lại quá trình này cho tới khi mảng được sắp xếp.

Benchmarks

Bây giờ ta sẽ so sánh tốc độ của các method sắp xếp ở phiên bản ruby 2.4.0

  sort!:                1405.8 i/s
  sort:                 1377.6 i/s - same-ish: difference falls within error
  sort_by reverse:      196.6  i/s - 7.15x  slower
  sort_by:              183.7  i/s - 7.65x  slower
  sort_by minus:        172.3  i/s - 8.16x  slower
  sort with block:      164.1  i/s - 8.57x  slower

=> sort nhanh hơn sort_by nhưng nó sẽ kém linh hoạt nếu ban không dùng block

Bài viết được dịch tại:

https://www.blackbytes.info/2017/07/ruby-sort/