19
$\begingroup$

I'm looking for a sorting algorithm for int arrays that doesn't allocate any byte other than the size of the array, and is limited to two instructions:

  1. SWAP: swap the next index with the current one;

  2. MOVE: moves the cursor to +1 or -1 index;

That is, you can't swap non neighboring indexes, nor swap the index 100, after you just swapped index 10. What is the most efficient algorithm - i.e., the one that uses the less amount of total moves?

|cite|improve this question
$\endgroup$
  • 13
    $\begingroup$ Not that strange, it is a physical machine which will sort a list of carts glued to a looong tape that is rolled up. The machine can only move the the tape forward or backward, and can only swap neighboring cards, of corse. In the real world you can't teleport around, so, those are the restrictions... $\endgroup$ – MaiaVictor Mar 28 '16 at 12:43
  • 2
    $\begingroup$ So, when you say that you want an algorithm that doesn't allocate any byte other than the size of the array, I guess you refer only to element storage, right? I can still allocate counters and such? $\endgroup$ – Darkhogg Mar 28 '16 at 12:46
  • 5
    $\begingroup$ Oh, sure. Of course. You can alloc some additional structures. You can even alloc the whole array and do a lot of really heavy computation and that counts as 0 cost. The only thing you need to minimize is the number of SWAP/MOVEs of the actual physical machine, because it is slow. Bubble sort is the best I could came up with, but I guessed there should be better options. $\endgroup$ – MaiaVictor Mar 28 '16 at 12:49
  • 1
    $\begingroup$ I don't think there is such an algorithm. Without any extra memory, you'll have no way to store any control state. $\endgroup$ – Raphael♦ Mar 28 '16 at 13:13
  • 1
    $\begingroup$ @svrm: yeah, then with unlimited RAM and the ability to copy the tape into RAM and do arbitrary computation on it for free, the algorithm "try everything and apply the best" is optimal in terms of number of moves of the tape. Unlikely to be practical, but that's because in practice the runtime would be squillions of years, not 0 ;-) If it costs N moves to copy a tape of length N into RAM, then naive brute force might not be optimal but it's within N of optimal. But none of this is specific to your problem: many problems when stated this way could be solved "offline" using a bogus algorithm. $\endgroup$ – Steve Jessop Mar 29 '16 at 13:07
13
$\begingroup$

Consider cocktail shaker sort, which is a bidirectional version of bubble sort. You bubblesort from low to high, and then (this is the added part) you bubblesort from high to low, repeat until done. This is still $O(n^2)$, but it makes significantly fewer passes on average, because small elements near the high end of the array will be moved to their final position in a single pass rather than N passes. Also, you can keep track of the lowest and highest positions where a swap occurred; subsequent passes need not scan beyond those points.

|cite|improve this answer
$\endgroup$
4
$\begingroup$

The number of swaps of adjacent elements needed to order an array is equal to the number of inversions in the array. With n elements in total, there are at most n*(n-1)/2 inversions, so bubble sort gives the asymptotically optimal number of swaps in this model.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Actually, bubble sort will give exactly the optimal number of swaps. However, for each permutation there are several ways to do the optimal number of swaps, and it is not obvious which one reduces the total number of moves. (By bubble sort I mean "pick the largest non-sorted and move it to the end of sorted") $\endgroup$ – Peter Kravchuk Mar 28 '16 at 22:02
4
$\begingroup$

The only algorithm with the two operators that you have mentioned which is quite efficient is the bubble sort. The complexity of the algorithm is $O(n^2)$ in the worst case.

I also assume apart from the two operations, we can also check whether we are at the rightmost (Op 3) or leftmost position (Op 4), either by use of sentinels $-\infty$ and $+\infty$ or by some operation on the list. Also we should have a comparison operation (Op 5) given separately or combined with swap operation. If the comparison operation is combined with the swap operation then it must tell us whether the swap was performed or not.

The algorithm that does not uses a boolean flag to know whether we have swapped any element or not, is given below (the trick to keep the information in the state of the machine, rather than memory):

Start:
    Do until we are not at the leftmost position (Op 4)
        move left (Op 2b)

Check:
    If we are at rightmost position (Op 3)
        goto Finished:
    If current value is larger than next value (Op 5)
        goto Unfinished:
    move right (Op 2a)
    Repeat Check:

Unfinished:
    If we are at rightmost position (Op 3)
        goto Start:
    If current value is larger than next value (Op 5)
        swap the elements (Op 1) and move right (Op 2a)
    Repeat Unfinished:

Finished:
    The list is sorted now, output it.

The solution of Eric Lippert, the gnome sort also works, because basically it is a two way bubble sort.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ What about insertion sort? $\endgroup$ – Darkhogg Mar 28 '16 at 12:42
  • $\begingroup$ Bubble sort needs at least two loop counters which are already more than allowed. $\endgroup$ – Raphael♦ Mar 28 '16 at 13:12
  • 1
    $\begingroup$ No, you can go left and right, and then right to left, until there is no change (which is maximum n times) without using counter. You don't even need extra space for a boolean flag to note if there is a change. If there is a change you just jump to another subroutine which does the same, except that it is another subroutine. $\endgroup$ – Shreesh Mar 28 '16 at 13:51
  • 1
    $\begingroup$ And of course, I assume you can read blank at both the ends so you may know that it is beginning or end of list. Also, I assume we read both the current and next element to know whether we need to swap. $\endgroup$ – Shreesh Mar 28 '16 at 13:58
  • 1
    $\begingroup$ Or, if we modify the operator swap as "swap if not in ascending order". $\endgroup$ – Shreesh Mar 28 '16 at 14:36

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.