class Array

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

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