Last active
August 29, 2015 14:20
-
-
Save ahmadseleem/687a56a234e3aa3e8167 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# | |
# Check if an Array could be sorted by One-Swap. | |
# | |
# Extend Array Class... | |
class Array | |
def sorted? | |
# each_cons(2).all? { |a, b| (a <=> b) <= 0 } | |
self == self.sort | |
end | |
def swap(i, j) | |
self[i], self[j] = self[j], self[i] | |
end | |
end | |
# Example Arrays... | |
A = [1, 5, 3, 3, 7] | |
B = [1, 3, 5, 3, 4] | |
C = [1, 3, 5] | |
# The code....................... | |
def sortable_by_one? a | |
# 1 . already sorted ? | |
if a.sorted? | |
puts "Array is already sorted!" | |
return true | |
end | |
# 2 . sorted by one move ? | |
size = a.size | |
(0...size).each_cons(2) do |i, sw| | |
(sw...size).each do |sw| | |
puts " = #{i}, #{sw} ======" | |
if a.swap(i, sw) && a.sorted? | |
puts ">> ARRAY: IS SORTED. NOW!" | |
return true | |
end | |
a.swap(i, sw) | |
end | |
end | |
# 3 . Else... > FLASE | |
puts ">> ARRAY: CAN'T BE SORTED BY ONE SWAP!!!" | |
return false | |
end | |
sortable_by_one?(A) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I found a simpler way. Check my gist again.