Ruby Sorting

Có bao nhiêu cách để sắp xếp một mảng trong Ruby? Nó có nhiều hơn là bạn nghĩ đấy....mặc dù với Array chỉ có 2 phương thức (sort & sort_by), nhưng khi kết hợp các phương thức này với block bạn có thể sắp xếp theo nhiều cách khác nhau. Ở bài viết này tôi muốn chia sẻ một vài ví dụ về nó.

Basic Sorting Hầu hết các hình thức cơ bản của sắp xếp được cung cấp bởi phương thức sort trong Ruby và được định nghĩa trong module Enumerable. Hãy xem ví dụ bên dưới:

numbers = [5,3,2,1]

numbers.sort

# [1,2,3,5]

Lưu ý rằng sort sẽ trả về một array mới cùng với kết quả đã sắp xếp. Sử dụng sort! nếu bạn muốn sắp xếp trực tiếp trên mảng cũ và trả về mảng đó thay vì một mảng mới.

Customized Sorting Bây giờ hãy thửu sắp xếp với các chức năng nâng cao hơn, như sắp xếp theo độ dài string hoặc những thứ khác tương tự như thế. Ta có thể dùng sort_by để thực hiện điều đó: Vi dụ:

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

Ví dụ trên cũng có thể được thực hiện bởi phương thức sort kèm với block:

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

Tuy nhiên, phương thức sort_by thường được sử dụng nhiều hơn do nó trông rõ ràng hơn, dễ đọc và nhanh hơn phương thức sort.

Note: Toán tử <=> được gọi là toán tử so sánh kết hợp (toán tử spaceship) và nó là một phương thức bạn có thể cài đặt trong class của mình. Ns trả về 1 nếu lơn hơn, 0 nếu bằng và -1 nếu nhỏ hơn.

Reverse Sort Bạn có thể sử dụng phương thức reverse sau khi sắp xếp để đảo ngược mảng, hoặc bạn có thể sử dụng block và đặt dấu - đằng trước điều kiện bạn đang sử dụng để sắp xếp. Hãy xem ví dụ:

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

Alphanumeric Sorting Bây giờ nếu bạn muốn sắp xếp danh sách string mà nó bao gồm cả các chữ số thì sao? Danh sách string giống thế này:

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

Nếu dùng sort như trên, bạn sẽ không nhận được danh sách đã sắp xếp đúng như bạn muốn:

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

Nhưng bạn có thể sửa nó bằng cách sử dụng sort_by:

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

Ở đây, ta sử dụng một biểu thức chính quy (\d+) để bắt các chữ số, sau ssos lấy số đầu tiên (first) và chuyển nó thành một số Integer (to_i).

Sorting Hashes Bạn không chỉ sắp xếp mảng, bạn cũng có thể sắp xếp một hash nữa. Ví dụ:

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

Ví dụ bên trên sắp xếp theo giá trị của hash, nhưng hãy chú ý điều thú vị ở đây, giá trị trả về không phải là một hash! Bạn nhận được một mảng đa chiều khi sắp xếp một hash. Để chuyển kết quả thành hash, bạn có thể dùng phương thức Array#to_h.

QuickSort Implementation Bây giờ hãy thử điều thú vị hơn: cài đặt phương thức sort của chính bạn. Nó có thể chậm hơn phương thức sort có sẵn nhưng đây vẫn là một bài tập thú vị nếu bạn thích khoa học máy tính.

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à lấy một số ngẫu nhiên sau đó chia danh sách của chúng ta thành 2 nhóm. Một nhóm là các số nhỏ hơn số đã chọn và nhóm còn lại gồm các số lớn hơn số đã chọn. Sau đó, chúng ta chỉ việc lặp lại phép toán này tới khi danh sách được sắp xếp.

Đánh giá Giờ hãy xem sự so sánh về hiệu suất của tất cả các phương thức sắp xếp:

# 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

Như bạn thấy, phương thức sort thông thường nhanh hơn rất nhiều so với sort_by, nhưng nó không linh hoạt trừ khi bạn sử dụng cùng với block.

Tổng kết Bạn vừa biết thêm về cách sử dụng phương thức sort và sort_by để sắp xếp array và hash trong những cách khác nhau, biết thêm về hiệu suất của chúng và cách để tự cài đặt thuật toán quick sort của riêng mình. Cảm ơn bạn đã đọc bài viết!