Say I had an input $\langle3,17,15,9,1\rangle$, could I for example begin by comparing 1 with 3 so that 1 appeared at the start of the sorted sequence straight away or would I first have to compare 3 and 17 and then continue working from left to right with consecutive numbers? If the latter is correct, do I then have to keep returning to the start to continue comparing elements until I reach the fully sorted array? If this is the case, how is it possible to sort the input in $n-1$ (4) steps?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
You can make the comparisons in any order you want. If there was only one possible sequence of comparisons, there'd be only one possible sorting algorithm!
But note that, to specify an algorithm, you have to specify it in terms of operations that your model of computation supports. For example, althouh you as an intelligent human can say "compare 1 with 3", to specify an algorithm, you'd need to be able to describe how to choose the elements to be compared next. Of course, you could try to say "compare the smallest with the second-smallest" but, then, you'd have to give an algorithm for finding those two elements which would, itself, probably use further comparisons. And, of course, if you already knew which were the smallest two, you wouldn't need to compare them anyway.
answered Mar 14, 2015 at 15:05