Class: Array

Inherits:
Object
  • Object
show all
Defined in:
lib/array/sort/helper.rb,
lib/array/sort/heap_sort.rb,
lib/array/sort/merge_sort.rb,
lib/array/sort/quick_sort.rb,
lib/array/sort/bubble_sort.rb,
lib/array/sort/insertion_sort.rb

Instance Method Summary collapse

Instance Method Details

#bubble_sort(&block) ⇒ 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.

Returns:

  • (Array) —

    the sorted array



15
16
17
 
# File 'lib/array/sort/bubble_sort.rb', line 15

def bubble_sort(&block)
  dup.bubble_sort!(&block)
end

#bubble_sort!(&block) ⇒ Array

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.

Returns:



30
31
32
33
34
35
36
37
38
39
 
# 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

#bubble_sort_by(&block) ⇒ Array, Enumerator

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.

Returns:

  • (Array) —

    if a block is given, the sorted array

  • (Enumerator) —

    if no block is given, an Enumerator



51
52
53
54
55
56
57
 
# 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

#bubble_sort_by!(&_block) ⇒ Array, Enumerator

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.

Returns:

  • (Array) —

    if a block is given, the sorted array

  • (Enumerator) —

    if no block is given, an Enumerator



69
70
71
72
73
74
75
76
77
 
# 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

#heap_sort(&block) ⇒ Array

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.

Returns:

  • (Array) —

    the sorted array



15
16
17
 
# File 'lib/array/sort/heap_sort.rb', line 15

def heap_sort(&block)
  dup.heap_sort!(&block)
end

#heap_sort!(&block) ⇒ Array

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.

Returns:



30
31
32
33
34
35
36
37
38
 
# 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

#heap_sort_by(&block) ⇒ Array, Enumerator

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.

Returns:

  • (Array) —

    if a block is given, the sorted array

  • (Enumerator) —

    if no block is given, an Enumerator



50
51
52
53
54
55
56
 
# 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

#heap_sort_by!(&_block) ⇒ Array, Enumerator

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.

Returns:

  • (Array) —

    if a block is given, the sorted array

  • (Enumerator) —

    if no block is given, an Enumerator



68
69
70
71
72
73
74
75
76
 
# 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

#insertion_sort(&block) ⇒ Array

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.

Returns:

  • (Array) —

    the sorted array



15
16
17
 
# File 'lib/array/sort/insertion_sort.rb', line 15

def insertion_sort(&block)
  dup.insertion_sort!(&block)
end

#insertion_sort!(&block) ⇒ Array

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.

Returns:



30
31
32
33
34
35
36
37
38
39
 
# 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

#insertion_sort_by(&block) ⇒ Array, Enumerator

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.

Returns:

  • (Array) —

    if a block is given, the sorted array

  • (Enumerator) —

    if no block is given, an Enumerator



51
52
53
54
55
56
57
 
# 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

#insertion_sort_by!(&_block) ⇒ Array, Enumerator

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.

Returns:

  • (Array) —

    if a block is given, the sorted array

  • (Enumerator) —

    if no block is given, an Enumerator



69
70
71
72
73
74
75
76
77
 
# 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

#merge_sort(&block) ⇒ Array

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.

Returns:

  • (Array) —

    the sorted array



15
16
17
18
19
20
21
 
# 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

#merge_sort!(&block) ⇒ Array

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.

Returns:



34
35
36
 
# File 'lib/array/sort/merge_sort.rb', line 34

def merge_sort!(&block)
  become_clone_of merge_sort(&block)
end

#merge_sort_by(&_block) ⇒ Array, Enumerator

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.

Returns:

  • (Array) —

    if a block is given, the sorted array

  • (Enumerator) —

    if no block is given, an Enumerator



48
49
50
51
52
53
54
55
56
 
# 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

#merge_sort_by!(&block) ⇒ Array, Enumerator

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.

Returns:

  • (Array) —

    if a block is given, the sorted array

  • (Enumerator) —

    if no block is given, an Enumerator



68
69
70
71
72
73
74
 
# 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

#quick_sort(&block) ⇒ Array

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.

Returns:

  • (Array) —

    the sorted array



15
16
17
18
19
 
# 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

#quick_sort!(&block) ⇒ Array

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.

Returns:



32
33
34
 
# File 'lib/array/sort/quick_sort.rb', line 32

def quick_sort!(&block)
  become_clone_of quick_sort(&block)
end

#quick_sort_by(&_block) ⇒ Array, Enumerator

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.

Returns:

  • (Array) —

    if a block is given, the sorted array

  • (Enumerator) —

    if no block is given, an Enumerator



46
47
48
49
50
51
52
53
54
 
# 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

#quick_sort_by!(&block) ⇒ Array, Enumerator

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.

Returns:

  • (Array) —

    if a block is given, the sorted array

  • (Enumerator) —

    if no block is given, an Enumerator



66
67
68
69
70
71
72
 
# 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(index1, index2) ⇒ Array

Swap two elements in the array, and returns self.

Parameters:

  • index1 (Integer) —

    The index of the first element.

  • index2 (Integer) —

    The index of the second element.

Returns:

Raises:

  • (ArgumentError) —

    If either of the two parameters is not an Integer.



10
11
12
13
14
 
# 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