The only operations you can do is take the number in the front and insert it anywhere else in the list. I figured out that you can always do the sorting in less than or equal to n-1 moves. But I need a constructive proof, the process which will produce the optimal result.

  • $\begingroup$ I'm not sure what you need if you "already figured it out"? A proof that $n-1$ cannot be made smaller? Or do you have a proof that $n-1$ is enough, but not in a constructive way? $\endgroup$ – Ingix Jan 20 at 16:23
  • $\begingroup$ Well, I meant I'm pretty sure that n-1 is the upper bound. But I want the algorithm that will produce the answer for a particular permutation. $\endgroup$ – Shafin Ahmed Jan 20 at 16:24
  • $\begingroup$ @saulspatz your process is wrong. Consider a list with 1 as the front element and unsorted n-1 elements in the back, you can't sort the other elements if you don't move 1. $\endgroup$ – Shafin Ahmed Jan 20 at 16:26
  • $\begingroup$ @ShafinAhmed Okay, I see what you mean now. $\endgroup$ – saulspatz Jan 20 at 16:32
  • $\begingroup$ It sounds like you're doing a poor version of a bubble sort. It's a shame you can't do a string sort because it is much more efficient. $\endgroup$ – poetasis Jan 20 at 16:54

Let the original list be $a_1,a_2,\ldots,a_n$. Let $1 \le k < n$ be the biggest index that fulfills $a_k > a_{k+1}$; if the list is already correctly ordered, set $k=0$.

Then the minimum number of operations you need to order that list is $k$.

Proof: After each operation, the relative position of 2 elements ($x,y$) that were both not the first element in this operation has not changed. If $x$ was before $y$ in the list before the operation, the same is true afterwards.

Each list element only advances at most 1 position into the direction of the first position with each operation. That means the $i$-th operation can only move an element from the first position that was originally at an index $i$ or lower. So after $k-1$ operations, the elements $a_k$ and $a_{k+1}$ have not yet been the first elements in an operation, so they are still in their original order.

Using the definition of $k$, this means after $k-1$ operations we still have 2 list elements in an incorrect order, as $a_k$ still comes before $a_{k+1}$, so at least $k$ operations are needed.

OTOH, it can be done in $k$ moves: Initially, consider the list from indices $1$ to $k$ the 'unordered' list part, while the list from indices $k+1$ to $n$ is the 'ordered' part. Note that by the definition of $k$ the ordered list part is initially actually correctly ordered. In each of the following $k$ operations, the unordered list part will shrink by 1, while the ordered list part increases by 1. Simply send the currently first element into the ordered list such that it will stay ordered. After $k$ operations, the whole list is ordered.

An example: Let the inital list order be $[3,2,1,4]$ We have $k=2$. I'll denote the dividing line between the unordered part and the ordered part with a $|$, so the list is initially


We send the $3$ to the position it should have with regards to $1$ and $4$:


Finally, we send $2$ to the correct place:


and the list is completely ordered!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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