1

If the definition of a decrease by one strategy is:

"A strategy where the size of the problem to be solved is steadily decreased by one element on each iteration."

Would that mean that insertion sort isn't a decrease by one algorithm? As it needs to compare all elements that have already been sorted, therefore taking more then one iteration to sort each element.

Or would the definition refer to the fact that it iterates through each element sorting each one, one by one?

1 Answer 1

1

According to that definition, I would say that insertion sort is not decrease-by-one algorithm, by the reason that you have already mentioned. That is, you can't call Insertion Sort method after one pass of the algorithm on smaller subset of the data, as you need all the data to do the insertion.

I believe the definition does not refer to the fact that "an algorithm iterates through each element one by one", as most algorithms involving arrays will do that, but rather to make the problem into a smaller subproblem which can be solved in exactly the same way, but with less data. Bubble sort is a decrease-by-one algorithm, since in each pass we put the maximum element in place, then we do bubble sort on the rest N-1 elements in the exact same way.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.