#Chris Nixon
#Algorithms II
#Fri. Jan. 27th, 2011
#Homework 2
 
class Sort2DMesh
  def initialize
    #creates our initial mesh as an instance variable to be used throughout our class
    @mesh = [[6, 1, 5, 7, 4, 3, 2, 9],[4, 3, 4, 5, 3, 9, 5, 8], [3, 7, 8, 6, 4, 2, 9, 3],[1, 7, 5, 3, 9, 6, 3, 8], [1, 6, 9, 3, 7, 3, 3, 1], [1, 6, 4, 3, 6, 6, 3, 9], [9, 8, 4, 2, 1, 8, 3, 8], [1, 2, 5, 7, 9, 4, 4, 9]]
  end
 
  def sort_mesh
    print_mesh("Initial mesh:") #prints out the intial mesh
    0.upto(Math.log2(@mesh.length**2)) do |x| #goes from 0 upto log_2_n: where n is 64, so upto 8 in this case #Shikha - The ceil of log2 should be taken. And also, you can directly pass @mesh.length to the functions/
      if x % 2 == 0 #if even value of x do the even odd row sort and print out the resulting mesh
        even_odd_row_sort(@mesh.length**2)
        print_mesh("Even odd row sort:")
      else #if odd value of x do the even odd column sort and print out the resulting mesh
        even_odd_column_sort(@mesh.length**2)
        print_mesh("Even odd column sort:")
      end
    end
    print_mesh("Final mesh:") #after performing the even odd row/column sorts print out the final mesh
    print_snake(@mesh.length**2) #prints out a string in snake order
    discussion #prints out a discussion of the complexity of the sort2dmesh
  end
 
  def even_odd_row_sort(n)
    Math.sqrt(n).to_i.times do #q times we iterate through our rows in parallel to sort
      0.upto(Math.sqrt(n)-1) do |row| #do in parallel
        if row % 2 == 0
          0.upto(Math.sqrt(n)-2) do |col|
            if @mesh[row][col] > @mesh[row][col+1]
              temp = @mesh[row][col+1] #holds a temp value to be exchanged
              @mesh[row][col+1] = @mesh[row][col]
              @mesh[row][col] = temp
            end
          end
        else
          0.upto(Math.sqrt(n)-2) do |col|
            if @mesh[row][col] < @mesh[row][col+1]
              temp = @mesh[row][col+1] #holds a temp value to be exchanged
              @mesh[row][col+1]= @mesh[row][col]
              @mesh[row][col] = temp
            end
          end
        end
      end
    end
  end
 
  def even_odd_column_sort(n)
    Math.sqrt(n).to_i.times do #q times we iterate through our columns in parallel to sort
      0.upto(Math.sqrt(n)-1) do |col| #do in parallel
        if col % 2 == 0
          0.upto(Math.sqrt(n)-2) do |row|
            if @mesh[row][col] > @mesh[row+1][col]
              temp = @mesh[row+1][col] #holds a temp value to be exchanged
              @mesh[row+1][col] = @mesh[row][col]
              @mesh[row][col] = temp
            end
          end
        else
          0.upto(Math.sqrt(n)-2) do |row|
            if @mesh[row][col] > @mesh[row+1][col]
              temp = @mesh[row+1][col] #holds a temp value to be exchanged
              @mesh[row+1][col]= @mesh[row][col]
              @mesh[row][col] = temp
            end
          end
        end
      end
    end
  end
 
  #prints out the mesh and a given message
  def print_mesh(message)
    puts "#{message}"
    @mesh.each_index do |row|
      @mesh.each_index do |column|
        print "#{@mesh[row][column]}"
      end
      puts
    end
  end
 
  #prints out a string of the snake order of the final mesh
  def print_snake(n)
    puts "Snake order:"
    snake_string = ""
    0.upto(Math.sqrt(n)-1) do |x|
      if x % 2 == 0
        0.upto(Math.sqrt(n).to_i-1) do |col|
          snake_string << "#{@mesh[x][col]}, "
        end
      else
        from = Math.sqrt(n).to_i - 1
        from.downto(0) do |col|
          snake_string << "#{@mesh[x][col]}, "
        end
      end
    end
    puts "#{snake_string[0..-3]}"
  end
 
  #discusses the sort2dmesh function and the complexity
  def discussion
    puts "For the sorting a 2D mesh the W(n) = sqrt(n)*log(n) + sqrt(n). EvenOddRowSort (line 23) and\nEvenOddColumnSort (line 47) each perform sqrt(n) parallel comparison steps."
    puts "The Sort2dMesh or in our case sort_mesh (line 7) function itself involes log_2_(n) + 1 steps.\nThis is how we get the worst case complexity as mentioned before."
  end
end
 
Sort2DMesh.new.sort_mesh
 

I0NocmlzIE5peG9uCiNBbGdvcml0aG1zIElJCiNGcmkuIEphbi4gMjd0aCwgMjAxMQojSG9tZXdvcmsgMgoKY2xhc3MgU29ydDJETWVzaAogIGRlZiBpbml0aWFsaXplCiAgICAjY3JlYXRlcyBvdXIgaW5pdGlhbCBtZXNoIGFzIGFuIGluc3RhbmNlIHZhcmlhYmxlIHRvIGJlIHVzZWQgdGhyb3VnaG91dCBvdXIgY2xhc3MKICAgIEBtZXNoID0gW1s2LCAxLCA1LCA3LCA0LCAzLCAyLCA5XSxbNCwgMywgNCwgNSwgMywgOSwgNSwgOF0sIFszLCA3LCA4LCA2LCA0LCAyLCA5LCAzXSxbMSwgNywgNSwgMywgOSwgNiwgMywgOF0sIFsxLCA2LCA5LCAzLCA3LCAzLCAzLCAxXSwgWzEsIDYsIDQsIDMsIDYsIDYsIDMsIDldLCBbOSwgOCwgNCwgMiwgMSwgOCwgMywgOF0sIFsxLCAyLCA1LCA3LCA5LCA0LCA0LCA5XV0KICBlbmQKCiAgZGVmIHNvcnRfbWVzaAogICAgcHJpbnRfbWVzaCgiSW5pdGlhbCBtZXNoOiIpICNwcmludHMgb3V0IHRoZSBpbnRpYWwgbWVzaAogICAgMC51cHRvKE1hdGgubG9nMihAbWVzaC5sZW5ndGgqKjIpKSBkbyB8eHwgI2dvZXMgZnJvbSAwIHVwdG8gbG9nXzJfbjogd2hlcmUgbiBpcyA2NCwgc28gdXB0byA4IGluIHRoaXMgY2FzZSAjU2hpa2hhIC0gVGhlIGNlaWwgb2YgbG9nMiBzaG91bGQgYmUgdGFrZW4uIEFuZCBhbHNvLCB5b3UgY2FuIGRpcmVjdGx5IHBhc3MgQG1lc2gubGVuZ3RoIHRvIHRoZSBmdW5jdGlvbnMvCiAgICAgIGlmIHggJSAyID09IDAgI2lmIGV2ZW4gdmFsdWUgb2YgeCBkbyB0aGUgZXZlbiBvZGQgcm93IHNvcnQgYW5kIHByaW50IG91dCB0aGUgcmVzdWx0aW5nIG1lc2gKICAgICAgICBldmVuX29kZF9yb3dfc29ydChAbWVzaC5sZW5ndGgqKjIpCiAgICAgICAgcHJpbnRfbWVzaCgiRXZlbiBvZGQgcm93IHNvcnQ6IikKICAgICAgZWxzZSAjaWYgb2RkIHZhbHVlIG9mIHggZG8gdGhlIGV2ZW4gb2RkIGNvbHVtbiBzb3J0IGFuZCBwcmludCBvdXQgdGhlIHJlc3VsdGluZyBtZXNoCiAgICAgICAgZXZlbl9vZGRfY29sdW1uX3NvcnQoQG1lc2gubGVuZ3RoKioyKQogICAgICAgIHByaW50X21lc2goIkV2ZW4gb2RkIGNvbHVtbiBzb3J0OiIpCiAgICAgIGVuZAogICAgZW5kCiAgICBwcmludF9tZXNoKCJGaW5hbCBtZXNoOiIpICNhZnRlciBwZXJmb3JtaW5nIHRoZSBldmVuIG9kZCByb3cvY29sdW1uIHNvcnRzIHByaW50IG91dCB0aGUgZmluYWwgbWVzaAogICAgcHJpbnRfc25ha2UoQG1lc2gubGVuZ3RoKioyKSAjcHJpbnRzIG91dCBhIHN0cmluZyBpbiBzbmFrZSBvcmRlcgogICAgZGlzY3Vzc2lvbiAjcHJpbnRzIG91dCBhIGRpc2N1c3Npb24gb2YgdGhlIGNvbXBsZXhpdHkgb2YgdGhlIHNvcnQyZG1lc2gKICBlbmQKCiAgZGVmIGV2ZW5fb2RkX3Jvd19zb3J0KG4pCiAgICBNYXRoLnNxcnQobikudG9faS50aW1lcyBkbyAjcSB0aW1lcyB3ZSBpdGVyYXRlIHRocm91Z2ggb3VyIHJvd3MgaW4gcGFyYWxsZWwgdG8gc29ydAogICAgICAwLnVwdG8oTWF0aC5zcXJ0KG4pLTEpIGRvIHxyb3d8ICNkbyBpbiBwYXJhbGxlbAogICAgICAgIGlmIHJvdyAlIDIgPT0gMAogICAgICAgICAgMC51cHRvKE1hdGguc3FydChuKS0yKSBkbyB8Y29sfAogICAgICAgICAgICBpZiBAbWVzaFtyb3ddW2NvbF0gPiBAbWVzaFtyb3ddW2NvbCsxXQogICAgICAgICAgICAgIHRlbXAgPSBAbWVzaFtyb3ddW2NvbCsxXSAjaG9sZHMgYSB0ZW1wIHZhbHVlIHRvIGJlIGV4Y2hhbmdlZAogICAgICAgICAgICAgIEBtZXNoW3Jvd11bY29sKzFdID0gQG1lc2hbcm93XVtjb2xdCiAgICAgICAgICAgICAgQG1lc2hbcm93XVtjb2xdID0gdGVtcAogICAgICAgICAgICBlbmQKICAgICAgICAgIGVuZAogICAgICAgIGVsc2UKICAgICAgICAgIDAudXB0byhNYXRoLnNxcnQobiktMikgZG8gfGNvbHwKICAgICAgICAgICAgaWYgQG1lc2hbcm93XVtjb2xdIDwgQG1lc2hbcm93XVtjb2wrMV0KICAgICAgICAgICAgICB0ZW1wID0gQG1lc2hbcm93XVtjb2wrMV0gI2hvbGRzIGEgdGVtcCB2YWx1ZSB0byBiZSBleGNoYW5nZWQKICAgICAgICAgICAgICBAbWVzaFtyb3ddW2NvbCsxXT0gQG1lc2hbcm93XVtjb2xdCiAgICAgICAgICAgICAgQG1lc2hbcm93XVtjb2xdID0gdGVtcAogICAgICAgICAgICBlbmQKICAgICAgICAgIGVuZAogICAgICAgIGVuZAogICAgICBlbmQKICAgIGVuZAogIGVuZAoKICBkZWYgZXZlbl9vZGRfY29sdW1uX3NvcnQobikKICAgIE1hdGguc3FydChuKS50b19pLnRpbWVzIGRvICNxIHRpbWVzIHdlIGl0ZXJhdGUgdGhyb3VnaCBvdXIgY29sdW1ucyBpbiBwYXJhbGxlbCB0byBzb3J0CiAgICAgIDAudXB0byhNYXRoLnNxcnQobiktMSkgZG8gfGNvbHwgI2RvIGluIHBhcmFsbGVsCiAgICAgICAgaWYgY29sICUgMiA9PSAwCiAgICAgICAgICAwLnVwdG8oTWF0aC5zcXJ0KG4pLTIpIGRvIHxyb3d8CiAgICAgICAgICAgIGlmIEBtZXNoW3Jvd11bY29sXSA+IEBtZXNoW3JvdysxXVtjb2xdCiAgICAgICAgICAgICAgdGVtcCA9IEBtZXNoW3JvdysxXVtjb2xdICNob2xkcyBhIHRlbXAgdmFsdWUgdG8gYmUgZXhjaGFuZ2VkCiAgICAgICAgICAgICAgQG1lc2hbcm93KzFdW2NvbF0gPSBAbWVzaFtyb3ddW2NvbF0KICAgICAgICAgICAgICBAbWVzaFtyb3ddW2NvbF0gPSB0ZW1wCiAgICAgICAgICAgIGVuZAogICAgICAgICAgZW5kCiAgICAgICAgZWxzZQogICAgICAgICAgMC51cHRvKE1hdGguc3FydChuKS0yKSBkbyB8cm93fAogICAgICAgICAgICBpZiBAbWVzaFtyb3ddW2NvbF0gPiBAbWVzaFtyb3crMV1bY29sXQogICAgICAgICAgICAgIHRlbXAgPSBAbWVzaFtyb3crMV1bY29sXSAjaG9sZHMgYSB0ZW1wIHZhbHVlIHRvIGJlIGV4Y2hhbmdlZAogICAgICAgICAgICAgIEBtZXNoW3JvdysxXVtjb2xdPSBAbWVzaFtyb3ddW2NvbF0KICAgICAgICAgICAgICBAbWVzaFtyb3ddW2NvbF0gPSB0ZW1wCiAgICAgICAgICAgIGVuZAogICAgICAgICAgZW5kCiAgICAgICAgZW5kCiAgICAgIGVuZAogICAgZW5kCiAgZW5kCgogICNwcmludHMgb3V0IHRoZSBtZXNoIGFuZCBhIGdpdmVuIG1lc3NhZ2UKICBkZWYgcHJpbnRfbWVzaChtZXNzYWdlKQogICAgcHV0cyAiI3ttZXNzYWdlfSIKICAgIEBtZXNoLmVhY2hfaW5kZXggZG8gfHJvd3wKICAgICAgQG1lc2guZWFjaF9pbmRleCBkbyB8Y29sdW1ufAogICAgICAgIHByaW50ICIje0BtZXNoW3Jvd11bY29sdW1uXX0iCiAgICAgIGVuZAogICAgICBwdXRzCiAgICBlbmQKICBlbmQKCiAgI3ByaW50cyBvdXQgYSBzdHJpbmcgb2YgdGhlIHNuYWtlIG9yZGVyIG9mIHRoZSBmaW5hbCBtZXNoCiAgZGVmIHByaW50X3NuYWtlKG4pCiAgICBwdXRzICJTbmFrZSBvcmRlcjoiCiAgICBzbmFrZV9zdHJpbmcgPSAiIgogICAgMC51cHRvKE1hdGguc3FydChuKS0xKSBkbyB8eHwKICAgICAgaWYgeCAlIDIgPT0gMAogICAgICAgIDAudXB0byhNYXRoLnNxcnQobikudG9faS0xKSBkbyB8Y29sfAogICAgICAgICAgc25ha2Vfc3RyaW5nIDw8ICIje0BtZXNoW3hdW2NvbF19LCAiCiAgICAgICAgZW5kCiAgICAgIGVsc2UKICAgICAgICBmcm9tID0gTWF0aC5zcXJ0KG4pLnRvX2kgLSAxCiAgICAgICAgZnJvbS5kb3dudG8oMCkgZG8gfGNvbHwKICAgICAgICAgIHNuYWtlX3N0cmluZyA8PCAiI3tAbWVzaFt4XVtjb2xdfSwgIgogICAgICAgIGVuZAogICAgICBlbmQKICAgIGVuZAogICAgcHV0cyAiI3tzbmFrZV9zdHJpbmdbMC4uLTNdfSIKICBlbmQKCiAgI2Rpc2N1c3NlcyB0aGUgc29ydDJkbWVzaCBmdW5jdGlvbiBhbmQgdGhlIGNvbXBsZXhpdHkKICBkZWYgZGlzY3Vzc2lvbgogICAgcHV0cyAiRm9yIHRoZSBzb3J0aW5nIGEgMkQgbWVzaCB0aGUgVyhuKSA9IHNxcnQobikqbG9nKG4pICsgc3FydChuKS4gRXZlbk9kZFJvd1NvcnQgKGxpbmUgMjMpIGFuZFxuRXZlbk9kZENvbHVtblNvcnQgKGxpbmUgNDcpIGVhY2ggcGVyZm9ybSBzcXJ0KG4pIHBhcmFsbGVsIGNvbXBhcmlzb24gc3RlcHMuIgogICAgcHV0cyAiVGhlIFNvcnQyZE1lc2ggb3IgaW4gb3VyIGNhc2Ugc29ydF9tZXNoIChsaW5lIDcpIGZ1bmN0aW9uIGl0c2VsZiBpbnZvbGVzIGxvZ18yXyhuKSArIDEgc3RlcHMuXG5UaGlzIGlzIGhvdyB3ZSBnZXQgdGhlIHdvcnN0IGNhc2UgY29tcGxleGl0eSBhcyBtZW50aW9uZWQgYmVmb3JlLiIKICBlbmQKZW5kCgpTb3J0MkRNZXNoLm5ldy5zb3J0X21lc2gK