Selection Sort - Ruby snippet

In this post I mentioned about selection sort. Below is the code snippet in ruby.


#selection_sort.rb
array = []
i = 0

#convert string array into integer array
ARGV.each do |x|
array[i] = x.to_i
i = i + 1
end

p "Input array:"
array.each do |x|
p x
end

for i in 0..array.length-1
# initialize to the current element
smallest = array[i]
index = i

    for j in i..array.length-1
    #find the smallest element on the RHS of current element
    if array[j] < smallest
     smallest = array[j]
        index = j
    end
    end

#swap the smallest element with the current element
tmp = array[i]
array[i] = smallest
array[index] = tmp
end


p "Sorted array:"
array.each do |x|
p x.to_i
end

Sample Run:-

>>ruby selection_sort.rb 8 5 7 1 9 3
"Input array:"
8
5
7
1
9
3
"Sorted array:"
1
3
5
7
8
9

Insertion Sort - Ruby

In this post I mentioned about insertion sort. Below is the code snippet in ruby.

#insertion_sort.rb
array = []
i = 0

#convert string array into integer array
ARGV.each do |x|
array[i] = x.to_i
i = i + 1
end

p "Input Array:"
array.each do |x|
p x
end


for i in 1..array.length-1

current = array[i] #set the current element

j = i-1 #the element just to the left of current element
index = i

while current < array[j] && j >= 0
  array[j+1] = array[j]
  index = j #save the position where the element will be inserted
  j = j-1
end
array[index] = current

#Below method is not efficient! 
=begin
  (i-1).downto(0) do |j|
      if current < array[j]
        #shift the element as in card game
         array[j+1] = array[j]
        array[j] = current
      end
  end
=end
end


p "New Array:"
array.each do |x|
p x.to_i
end

Sample Run:-

>>ruby insertion_sort.rb 9 8 1 25 0
"Input Array:"
9
8
1
25
0
"New Array:"
0
1
8
9
25

RGeo + Read shapefiles (.shp) + Ubuntu 12.04

Our objective is to read shapefiles using the RGeo gem in a Ruby program.

1. Install GEOS.
2. RGeo is a geospatial data library for Ruby.

   gem install rgeo 

3. RGeo::Shapefile is an optional module for RGeo for reading geospatial data from ESRI shapefiles.

   gem install rgeo-shapefile

Download a sample shapefile to test the code, (3 files - test.shp, test.dbf, test.shx).

Paste the following lines of code in a ruby file and run it.

require 'rgeo/shapefile'

RGeo::Shapefile::Reader.open('test.shp') do |file|
  puts "File contains #{file.num_records} records."
  file.each do |record|
    puts "Record number #{record.index}:"
    puts "  Geometry: #{record.geometry.as_text}"
    puts "  Attributes: #{record.attributes.inspect}"
  end
  file.rewind
  record = file.next
  puts "First record geometry was: #{record.geometry.as_text}"
end

If GEOS library is not installed then it may produce the following error:-

/var/lib/gems/1.9.1/gems/rgeo-shapefile 0.2.3/lib/rgeo/shapefile/reader.rb:623:in
`_read_polygon': GEOS is not available, but is required for correct interpretation
of polygons in shapefiles. (RGeo::Error::RGeoError)

Selection Sort Vs Insertion Sort

Selection Sort: Given a list, take the current element and exchange it with the smallest element on the right hand side of the current element.
Insertion Sort: Given a list, take the current element and insert it at the appropriate position of the list, adjusting the list every time you insert. It is similar to arranging the cards in a Card game.
Time Complexity of selection sort is always n(n - 1)/2, whereas insertion sort has better time complexity as its worst case complexity is n(n - 1)/2. Generally it will take lesser or equal comparisons then n(n - 1)/2.
Any suggestion to improve this article is always welcome!

Below you can find the Ruby code snippets:-
Selection Sort
Insertion Sort

Quickly ping Google/Yahoo to know your Connection Status.

1. Open notepad and jot down ping -t 209.85.171.100. Close and rename it as *.bat file. This is the IP address* of Google.

2. Send shortcut to your Desktop.Change icon(Optional).

1. 2.

Note: Don’t use IP address of Microsoft.com/Amazon.com, etc as they don’t respond to ping command.

For my broadband connection ‘Round Trip Propagation time’ of around 300-400ms(seen in snapshot above) indicates a fairly good connection speed. If you see reply from remote server, close the batch process.

*why use IP address? If the connection is not ok, the batch process will fail to execute if you simply write ping -t google.com, so you won’t be able to find the problem.