From 9ab0197bb096f9b75207c0301378106f6b87f87e Mon Sep 17 00:00:00 2001 From: mo khan Date: Mon, 21 Jul 2014 22:32:46 -0600 Subject: implement quick find. --- lib/quick_find.rb | 23 +++++++++++++++++++ spec/quick_find_spec.rb | 60 +++++++++++++++++++++++++++++++++++++++++++++++++ spec/spec_helper.rb | 1 + 3 files changed, 84 insertions(+) create mode 100644 lib/quick_find.rb create mode 100644 spec/quick_find_spec.rb diff --git a/lib/quick_find.rb b/lib/quick_find.rb new file mode 100644 index 0000000..419ed8b --- /dev/null +++ b/lib/quick_find.rb @@ -0,0 +1,23 @@ +class QuickFind + def initialize(size) + @items = [] + size.times.each do |n| + @items[n] = n + end + end + + def connected?(x, y) + @items[x] == @items[y] + end + + def union(x, y) + x_value = @items[x] + y_value = @items[y] + + @items.size.times do |n| + if @items[n] == x_value + @items[n] = y_value + end + end + end +end diff --git a/spec/quick_find_spec.rb b/spec/quick_find_spec.rb new file mode 100644 index 0000000..88929e3 --- /dev/null +++ b/spec/quick_find_spec.rb @@ -0,0 +1,60 @@ +require "spec_helper" + +describe QuickFind do + subject { QuickFind.new(10) } + + it "is not connected by default" do + 10.times do |n| + expect(subject.connected?(n, n+1)).to be_false + end + end + + it "is connected" do + subject.union(0, 1) + expect(subject.connected?(0, 1)).to be_true + end + + it "unions and connects properly" do + subject.union(4, 3) + expect(subject.connected?(4, 3)).to be_true + expect(subject.connected?(3, 4)).to be_true + + subject.union(3, 8) + expect(subject.connected?(3, 8)).to be_true + + subject.union(6, 5) + expect(subject.connected?(6, 5)).to be_true + + subject.union(9, 4) + expect(subject.connected?(9, 4)).to be_true + + subject.union(2, 1) + expect(subject.connected?(2, 1)).to be_true + + subject.union(8, 9) + expect(subject.connected?(8, 9)).to be_true + + expect(subject.connected?(5, 0)).to be_false + subject.union(5, 0) + expect(subject.connected?(5, 0)).to be_true + expect(subject.connected?(6, 0)).to be_true + expect(subject.connected?(5, 6)).to be_true + + subject.union(7, 2) + subject.union(6, 1) + + tuples = [ + [0, 5], + [5, 6], + [6, 1], + [1, 2], + [2, 7], + [8, 3], + [3, 4], + [4, 9], + ] + tuples.each do |tuple| + expect(subject.connected?(tuple.first, tuple.last)).to be_true + end + end +end diff --git a/spec/spec_helper.rb b/spec/spec_helper.rb index 6cfb317..7d79f94 100644 --- a/spec/spec_helper.rb +++ b/spec/spec_helper.rb @@ -1,5 +1,6 @@ require 'benchmark' require_relative '../lib/in_order_traversal' +require_relative '../lib/quick_find' require_relative '../lib/sorting/bubble_sort' require_relative '../lib/sorting/insertion_sort' -- cgit v1.2.3 From 800887ed8f6a63a3270691ce5917f7ff75137f45 Mon Sep 17 00:00:00 2001 From: mo khan Date: Tue, 22 Jul 2014 22:15:29 -0600 Subject: implement quick union. --- lib/quick_union.rb | 20 ++++++++++++++++++++ spec/quick_union_spec.rb | 33 +++++++++++++++++++++++++++++++++ spec/spec_helper.rb | 1 + 3 files changed, 54 insertions(+) create mode 100644 lib/quick_union.rb create mode 100644 spec/quick_union_spec.rb diff --git a/lib/quick_union.rb b/lib/quick_union.rb new file mode 100644 index 0000000..62aec94 --- /dev/null +++ b/lib/quick_union.rb @@ -0,0 +1,20 @@ +class QuickUnion + def initialize(size) + @items = Array.new(size) { |n| n } + end + + def union(x, y) + @items[x] = root_of(y) + end + + def connected?(x, y) + root_of(x) == root_of(y) + end + + private + + def root_of(x) + x = @items[x] until @items[x] == x + x + end +end diff --git a/spec/quick_union_spec.rb b/spec/quick_union_spec.rb new file mode 100644 index 0000000..362d2f2 --- /dev/null +++ b/spec/quick_union_spec.rb @@ -0,0 +1,33 @@ +require "spec_helper" + +describe QuickUnion do + subject { QuickUnion.new(10) } + + it "is not connected" do + expect(subject.connected?(0, 1)).to be_false + end + + it "is connected" do + subject.union(4, 3) + subject.connected?(4, 3).should be_true + subject.union(3, 8) + subject.connected?(3, 8).should be_true + subject.union(6, 5) + subject.connected?(6, 5).should be_true + + subject.union(9, 4) + subject.connected?(9, 4).should be_true + + subject.union(2, 1) + subject.connected?(8, 9).should be_true + subject.connected?(5, 4).should be_false + subject.union(5, 0) + subject.connected?(5, 0).should be_true + subject.union(7, 2) + subject.connected?(7, 2).should be_true + subject.union(6, 1) + subject.connected?(6, 1).should be_true + subject.union(7, 3) + subject.connected?(7, 3).should be_true + end +end diff --git a/spec/spec_helper.rb b/spec/spec_helper.rb index 7d79f94..60746c2 100644 --- a/spec/spec_helper.rb +++ b/spec/spec_helper.rb @@ -1,6 +1,7 @@ require 'benchmark' require_relative '../lib/in_order_traversal' require_relative '../lib/quick_find' +require_relative '../lib/quick_union' require_relative '../lib/sorting/bubble_sort' require_relative '../lib/sorting/insertion_sort' -- cgit v1.2.3 From 91cc49048409f9dc6bbf28bf520de43c533e612f Mon Sep 17 00:00:00 2001 From: mo khan Date: Mon, 28 Jul 2014 20:23:10 -0600 Subject: optimize performance of quick union by maintaining balance. --- lib/quick_union.rb | 13 ++++++++++++- 1 file changed, 12 insertions(+), 1 deletion(-) diff --git a/lib/quick_union.rb b/lib/quick_union.rb index 62aec94..f8a966b 100644 --- a/lib/quick_union.rb +++ b/lib/quick_union.rb @@ -1,10 +1,21 @@ class QuickUnion def initialize(size) @items = Array.new(size) { |n| n } + @size = Array.new(size, 0) end def union(x, y) - @items[x] = root_of(y) + i = root_of(x) + j = root_of(y) + return if (i == j) + + if @size[i] < @size[j] + @items[i] = j + @size[j] = @size[j] + @size[i] + else + @items[j] = i + @size[i] = @size[i] + @size[j] + end end def connected?(x, y) -- cgit v1.2.3 From e05094711fe1a42b18af85b64958bb4c2da35848 Mon Sep 17 00:00:00 2001 From: mo khan Date: Thu, 31 Jul 2014 21:12:58 -0600 Subject: extract lets --- spec/sorting/efficiency_spec.rb | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/spec/sorting/efficiency_spec.rb b/spec/sorting/efficiency_spec.rb index 46bf5de..86505fd 100644 --- a/spec/sorting/efficiency_spec.rb +++ b/spec/sorting/efficiency_spec.rb @@ -1,6 +1,10 @@ require "spec_helper" describe "Algorithm efficiency" do + let(:bubble_sort) { BubbleSort.new } + let(:insertion_sort) { InsertionSort.new } + let(:merge_sort) { MergeSort.new } + let(:quick_sort) { QuickSort.new } it "should sort an array of 100 numbers" do run(100) @@ -21,10 +25,10 @@ describe "Algorithm efficiency" do def run(n) numbers = Array.new(n) { rand(n) } Benchmark.bmbm do |x| - x.report("#{n}-bubble") { BubbleSort.new.sort(numbers) } - x.report("#{n}-insertion") { InsertionSort.new.sort(numbers) } - x.report("#{n}-merge") { MergeSort.new.sort(numbers) } - x.report("#{n}-quick") { QuickSort.new.sort(numbers) } + x.report("#{n}-bubble") { bubble_sort.sort(numbers) } + x.report("#{n}-insertion") { insertion_sort.sort(numbers) } + x.report("#{n}-merge") { merge_sort.sort(numbers) } + x.report("#{n}-quick") { quick_sort.sort(numbers) } x.report("#{n}-ruby") { numbers.sort } end end -- cgit v1.2.3