Skip to content

Instantly share code, notes, and snippets.

@hugomaiavieira
Created August 6, 2015 15:35
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save hugomaiavieira/de0d56848d229f27e193 to your computer and use it in GitHub Desktop.
MyArray
class MyArray < Array
def initialize(array=[])
super(self.class.ordenar(array))
end
# Utilizando o algorítimo quicksort
def self.ordenar(array)
return array if array.size <=1
pivot = array[0]
menores = ordenar(array.select { |item| item < pivot })
# Para pegar os iguais, seria `select { |item| item == pivot }`. Contudo,
# não precisamos de repetidos, então pode ser uma lista apenas com o pivot
iguais = [pivot]
maiores = ordenar(array.select { |item| item > pivot })
menores + iguais + maiores
end
def add(item)
return if index(item) # ignorar repetidos
indice = index(bsearch{ |x| x > item}) || -1
insert(indice, item)
self
end
end
### testes
def assert(got, expected)
puts(got == expected || "expected #{expected}, got #{got}")
end
myarray = MyArray.new([3,5,1,6,3,2,5,7])
assert(myarray, [1, 2, 3, 5, 6, 7])
assert(myarray.add(8), [1, 2, 3, 5, 6, 7, 8])
assert(myarray.add(4).add(0).add(-1), [-1, 0, 1, 2, 3, 4, 5, 6, 7, 8])
assert(MyArray.new.add(1), [1])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment