If I am loading a whole load of items (un-ordered words from a file or something) would it be more efficient to load them all to a Ruby array, and then use the built in sort!
method or to do a binary lookup for the place of each item in the list as I load it, and add it in that position.
Basic code:
array = []
lines.each do |line|
array.push line
end
array.sort!
vs
array = []
lines.each do |line|
array.insert(find_index(line), line)
end
find_index()
would lookup the correct index for the item in the array using a binary search.
Best Answer
array.insert
isO(n)
for insertions in the middle (because it has to copy a part of the array), making the second variantO(n^2)
, whilepush
isO(1)
, andsort!
isO(n log n)
, so the first variant is onlyO(n log n)
. Also the first variant looks cleaner.