class Array
Public Instance Methods
Returns a new array created by sorting self
, using bubble sort algorithm.
Comparisons for the sort will be done using the <=> operator or using an optional code block.
The block must implement a comparison between a
and b
and return an integer less than 0 when b
follows a
, 0
when a
and b
are equivalent, or an integer greater than 0 when a
follows b
.
The result is guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements will be preserved.
@return [Array] the sorted array
# File lib/array/sort/bubble_sort.rb, line 15 def bubble_sort(&block) dup.bubble_sort!(&block) end
Sorts self
in place, using bubble sort algorithm.
Comparisons for the sort will be done using the <=> operator or using an optional code block.
The block must implement a comparison between a
and b
and return an integer less than 0 when b
follows a
, 0
when a
and b
are equivalent, or an integer greater than 0 when a
follows b
.
The result is guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements will be preserved.
@return [Array] self
# File lib/array/sort/bubble_sort.rb, line 30 def bubble_sort!(&block) return self if length <= 1 n = length loop do new_n = bubble_sort_check(n, &block) n = new_n break if n.zero? end self end
Returns a new array created by sorting self
with bubble sort algorithm, using a set of keys generated by mapping the values in self through the given block.
The result is guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements will be preserved.
If no block is given, an Enumerator is returned instead.
@return [Array] if a block is given, the sorted array @return [Enumerator] if no block is given, an Enumerator
# File lib/array/sort/bubble_sort.rb, line 51 def bubble_sort_by(&block) if block_given? dup.bubble_sort_by!(&block) else to_enum :bubble_sort_by end end
Sorts self
in place with bubble sort algorithm, using a set of keys generated by mapping the values in self through the given block.
The result is guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements will be preserved.
If no block is given, an Enumerator is returned instead.
@return [Array] if a block is given, the sorted array @return [Enumerator] if no block is given, an Enumerator
# File lib/array/sort/bubble_sort.rb, line 69 def bubble_sort_by!(&_block) if block_given? bubble_sort! do |a, b| yield(a) <=> yield(b) end else to_enum :bubble_sort_by! end end
Returns a new array created by sorting self
, using heap sort algorithm.
Comparisons for the sort will be done using the <=> operator or using an optional code block.
The block must implement a comparison between a
and b
and return an integer less than 0 when b
follows a
, 0
when a
and b
are equivalent, or an integer greater than 0 when a
follows b
.
The result is not guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements is unpredictable.
@return [Array] the sorted array
# File lib/array/sort/heap_sort.rb, line 15 def heap_sort(&block) dup.heap_sort!(&block) end
Sorts self
in place, using heap sort algorithm.
Comparisons for the sort will be done using the <=> operator or using an optional code block.
The block must implement a comparison between a
and b
and return an integer less than 0 when b
follows a
, 0
when a
and b
are equivalent, or an integer greater than 0 when a
follows b
.
The result is not guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements is unpredictable.
@return [Array] self
# File lib/array/sort/heap_sort.rb, line 30 def heap_sort!(&block) return self if length <= 1 heapify(&block) (length - 1).downto(1) do |end_| swap(end_, 0) sift_down(0, end_ - 1, &block) end self end
Returns a new array created by sorting self
with heap sort algorithm, using a set of keys generated by mapping the values in self through the given block.
The result is not guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements is unpredictable.
If no block is given, an Enumerator is returned instead.
@return [Array] if a block is given, the sorted array @return [Enumerator] if no block is given, an Enumerator
# File lib/array/sort/heap_sort.rb, line 50 def heap_sort_by(&block) if block_given? dup.heap_sort_by!(&block) else to_enum :heap_sort_by end end
Sorts self
in place with heap sort algorithm, using a set of keys generated by mapping the values in self through the given block.
The result is not guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements is unpredictable.
If no block is given, an Enumerator is returned instead.
@return [Array] if a block is given, the sorted array @return [Enumerator] if no block is given, an Enumerator
# File lib/array/sort/heap_sort.rb, line 68 def heap_sort_by!(&_block) if block_given? heap_sort! do |a, b| yield(a) <=> yield(b) end else to_enum :heap_sort_by! end end
Returns a new array created by sorting self
, using insertion sort algorithm.
Comparisons for the sort will be done using the <=> operator or using an optional code block.
The block must implement a comparison between a
and b
and return an integer less than 0 when b
follows a
, 0
when a
and b
are equivalent, or an integer greater than 0 when a
follows b
.
The result is guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements will be preserved.
@return [Array] the sorted array
# File lib/array/sort/insertion_sort.rb, line 15 def insertion_sort(&block) dup.insertion_sort!(&block) end
Sorts self
in place, using insertion sort algorithm.
Comparisons for the sort will be done using the <=> operator or using an optional code block.
The block must implement a comparison between a
and b
and return an integer less than 0 when b
follows a
, 0
when a
and b
are equivalent, or an integer greater than 0 when a
follows b
.
The result is guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements will be preserved.
@return [Array] self
# File lib/array/sort/insertion_sort.rb, line 30 def insertion_sort!(&block) return self if length <= 1 (1...length).each do |i| i.downto(1) do |j| break unless sort_compare(self[j - 1], self[j], &block) == 1 swap(j - 1, j) end end self end
Returns a new array created by sorting self
with insertion sort algorithm, using a set of keys generated by mapping the values in self through the given block.
The result is guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements will be preserved.
If no block is given, an Enumerator is returned instead.
@return [Array] if a block is given, the sorted array @return [Enumerator] if no block is given, an Enumerator
# File lib/array/sort/insertion_sort.rb, line 51 def insertion_sort_by(&block) if block_given? dup.insertion_sort_by!(&block) else to_enum :insertion_sort_by end end
Sorts self
in place with insertion sort algorithm, using a set of keys generated by mapping the values in self through the given block.
The result is guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements will be preserved.
If no block is given, an Enumerator is returned instead.
@return [Array] if a block is given, the sorted array @return [Enumerator] if no block is given, an Enumerator
# File lib/array/sort/insertion_sort.rb, line 69 def insertion_sort_by!(&_block) if block_given? insertion_sort! do |a, b| yield(a) <=> yield(b) end else to_enum :insertion_sort_by! end end
Returns a new array created by sorting self
, using merge sort algorithm.
Comparisons for the sort will be done using the <=> operator or using an optional code block.
The block must implement a comparison between a
and b
and return an integer less than 0 when b
follows a
, 0
when a
and b
are equivalent, or an integer greater than 0 when a
follows b
.
The result is guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements will be preserved.
@return [Array] the sorted array
# File lib/array/sort/merge_sort.rb, line 15 def merge_sort(&block) return dup if length <= 1 divided_parts = merge_sort_divide part_a_sorted = divided_parts[0].merge_sort part_b_sorted = divided_parts[1].merge_sort merge_sort_merge part_a_sorted, part_b_sorted, &block end
Sorts self
in place, using merge sort algorithm.
Comparisons for the sort will be done using the <=> operator or using an optional code block.
The block must implement a comparison between a
and b
and return an integer less than 0 when b
follows a
, 0
when a
and b
are equivalent, or an integer greater than 0 when a
follows b
.
The result is guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements will be preserved.
@return [Array] self
# File lib/array/sort/merge_sort.rb, line 34 def merge_sort!(&block) become_clone_of merge_sort(&block) end
Returns a new array created by sorting self
with merge sort algorithm, using a set of keys generated by mapping the values in self through the given block.
The result is guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements will be preserved.
If no block is given, an Enumerator is returned instead.
@return [Array] if a block is given, the sorted array @return [Enumerator] if no block is given, an Enumerator
# File lib/array/sort/merge_sort.rb, line 48 def merge_sort_by(&_block) if block_given? merge_sort do |a, b| yield(a) <=> yield(b) end else to_enum :merge_sort_by end end
Sorts self
in place with merge sort algorithm, using a set of keys generated by mapping the values in self through the given block.
The result is guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements will be preserved.
If no block is given, an Enumerator is returned instead.
@return [Array] if a block is given, the sorted array @return [Enumerator] if no block is given, an Enumerator
# File lib/array/sort/merge_sort.rb, line 68 def merge_sort_by!(&block) if block_given? become_clone_of merge_sort_by(&block) else to_enum :merge_sort_by! end end
Returns a new array created by sorting self
, using quicksort algorithm.
Comparisons for the sort will be done using the <=> operator or using an optional code block.
The block must implement a comparison between a
and b
and return an integer less than 0 when b
follows a
, 0
when a
and b
are equivalent, or an integer greater than 0 when a
follows b
.
The result is not guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements is unpredictable.
@return [Array] the sorted array
# File lib/array/sort/quick_sort.rb, line 15 def quick_sort(&block) return dup if length <= 1 left, right = self[1..-1].partition { |y| sort_compare(first, y, &block).positive? } left.quick_sort + [first] + right.quick_sort end
Sorts self
in place, using quicksort algorithm.
Comparisons for the sort will be done using the <=> operator or using an optional code block.
The block must implement a comparison between a
and b
and return an integer less than 0 when b
follows a
, 0
when a
and b
are equivalent, or an integer greater than 0 when a
follows b
.
The result is not guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements is unpredictable.
@return [Array] self
# File lib/array/sort/quick_sort.rb, line 32 def quick_sort!(&block) become_clone_of quick_sort(&block) end
Returns a new array created by sorting self
with quicksort algorithm, using a set of keys generated by mapping the values in self through the given block.
The result is not guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements is unpredictable.
If no block is given, an Enumerator is returned instead.
@return [Array] if a block is given, the sorted array @return [Enumerator] if no block is given, an Enumerator
# File lib/array/sort/quick_sort.rb, line 46 def quick_sort_by(&_block) if block_given? quick_sort do |a, b| yield(a) <=> yield(b) end else to_enum :quick_sort_by end end
Sorts self
in place with quicksort algorithm, using a set of keys generated by mapping the values in self through the given block.
The result is not guaranteed to be stable. When the comparison of two elements returns 0
, the order of the elements is unpredictable.
If no block is given, an Enumerator is returned instead.
@return [Array] if a block is given, the sorted array @return [Enumerator] if no block is given, an Enumerator
# File lib/array/sort/quick_sort.rb, line 66 def quick_sort_by!(&block) if block_given? become_clone_of quick_sort_by(&block) else to_enum :quick_sort_by! end end
Swap two elements in the array, and returns self
.
@param index1 [Integer] The index of the first element. @param index2 [Integer] The index of the second element. @return [Array] @raise [ArgumentError] If either of the two parameters is not an Integer.
# File lib/array/sort/helper.rb, line 10 def swap(index1, index2) raise ArgumentError, 'Index must be an integer.' unless index1.is_a?(Integer) && index2.is_a?(Integer) self[index1], self[index2] = self[index2], self[index1] if index1 != index2 self end
Private Instance Methods
Clear everything in self
, and add all elements in target
.
# File lib/array/sort/helper.rb, line 30 def become_clone_of(target) clear concat target end
@private
# File lib/array/sort/bubble_sort.rb, line 82 def bubble_sort_check(length_checking, &block) new_n = 0 (1...length_checking).each do |i| next unless sort_compare(self[i - 1], self[i], &block).positive? swap i - 1, i new_n = i end new_n end
@private
# File lib/array/sort/heap_sort.rb, line 101 def check_less_than_sibling(child, end_, &block) child + 1 <= end_ && sort_compare(self[child], self[child + 1], &block) == -1 end
@private
# File lib/array/sort/heap_sort.rb, line 106 def check_max_heap_order(root, child, &block) return true unless sort_compare(self[root], self[child], &block) == -1 swap root, child false end
@private
# File lib/array/sort/heap_sort.rb, line 81 def heapify(&block) end_ = length - 1 (length / 2 - 1).downto(0) do |start| sift_down(start, end_, &block) end end
@private
# File lib/array/sort/merge_sort.rb, line 79 def merge_sort_divide mid = length / 2 part_a = self[0, mid] part_b = self[mid..-1] [part_a, part_b] end
@private
# File lib/array/sort/merge_sort.rb, line 87 def merge_sort_merge(part_a, part_b, &block) result = [] while part_a.length.positive? && part_b.length.positive? result << (sort_compare(part_a.first, part_b.first, &block).positive? ? part_b : part_a).shift end result + part_a + part_b end
@private
# File lib/array/sort/heap_sort.rb, line 89 def sift_down(start, end_, &block) root = start loop do child = root * 2 + 1 break if child > end_ child += 1 if check_less_than_sibling(child, end_, &block) break if check_max_heap_order(root, child, &block) root = child end end
Compare two elements.
If a block is provided, it will be used to compare the two elements. If not, operator +<=>+ will be used.
# File lib/array/sort/helper.rb, line 21 def sort_compare(element1, element2, &_block) if block_given? yield element1, element2 else element1 <=> element2 end end