Specialized sorting algortihm needed

I need a sorting algorithm which operates on a single, pre-populated array, and which is limited to perform only one operation:

-Move an item to position P, pushing all elements from position P+X to position P+X+1 (X => 0)

The algorithm must be optimized for the least possible number of operations (obviously).

Why? I'm working against a Google API which only allows me to perform this operation on their lists. The operation is a web service call. I want to minimize the number of calls.

Does this algorithm exist and have a name? Anyone want to give it a shot on a solution?

I have already implemented a dumb algorithm, but it is not optimal. Example:

List1 = [2,3,4,5,6,7,8,9,1]

Zero elements are in their correct place. A smart algorithm would move the last item to index 0 (zero), effectively pushing all other items one index down and the sorting is complete. MY algorithm checks the element at position 0, finds out it belongs in position 1 and puts it there, causing the list to now be in this state:

List1 = [3,2,4,5,6,7,8,9,1]

..I don't think I need to go on :)

No way to edit posts here? There's obviously a contradiction in my definition of the operation and the example.

The operation is better defined as:
-Move an item X to the slot after item Y, or to index 0.

This can also be seen as a removal of the item followed by an insert sort.

I think you have described a "selection sort", but I'm not sure. See http://en.wikipedia.org/wiki/Sorting_algorithm

It sounds like you need an in-place sorting algorithm (i.e., no extra storage is needed, like the extra storage needed to maintain an additional scratch copy of all of the data). If so, then the selection sort is not very efficient. The wiki page will have some better recommendations.

Also check out the animations and comparisons at the following sites:
http://www.sorting-algorithms.com/
http://www.cs.ubc.ca/~harrison/Java/sorting-demo.html

Mike

Selection sort can work in-place, so you just search for the smallest element, place it in its position, then continue searching the subsequent sub-list. It differs from conventional selection sort on arrays in that you just place the element in its position instead of swapping it with the element at that position.

That said, as for linked lists, in-place merge sort should be applicable here.

EDIT:
Actually, insertion sort is also applicable, and in fact you can use binary search to find the position and then just insert without having to expend operations to move the elements to make space for the element to be inserted. It is probably also the most intuitive given the permitted list changing operation.

EDIT #2:
Since you are trying to minimise the number of list changing operations, I do not think you need to bother with merge sort. Selection sort will do, especially if you avoid inserting a selected element in its own position. Insertion sort should have similiar performance characteristics (max n-1 operations), except that if you can do binary search, you have fewer comparisons too.

Quote:

---

Originally Posted by MikeAThon

I think you have described a "selection sort", but I'm not sure. See http://en.wikipedia.org/wiki/Sorting_algorithm

It sounds like you need an in-place sorting algorithm (i.e., no extra storage is needed, like the extra storage needed to maintain an additional scratch copy of all of the data).

---

Well... yes and no. I fetch the list from web, can use extra storage for _temporary_ work and then store the result back "in-place-wise". So conventional efficiency measurements (O-notation) don't really apply here. Well they apply of course, but only locally while determining the sort order or for other temporary work.

So actually I'm using _two_ sorting algorithms in this process. One for determining the correct order - this is done locally and by the .NET library, and the execution time is negligible compared to the second "sorting" which is the algorithm I'm asking for - writing the elements back with the operation described.

But I think you've set me on the right track here. I can really use the core of selection sort to write the elements back. Instead of asking the question "Is this element at the correct index" (having the .NET-sorted list to compare with), I should be asking "Is this element in the correct order" - only comparing it to the previous item at any time. This would at least solve my example case in one single write operation, and I think also will be optimal for all cases.

...thinking more about it, I even think this implementation will render the .NET-sorting-for-comparison unnecessary.

Thank you for your answer. I'll implement it as soon as I get time and post results back here :)

Quote:

---

Originally Posted by laserlight

EDIT #2:
Since you are trying to minimise the number of list changing operations, I do not think you need to bother with merge sort. Selection sort will do, especially if you avoid inserting a selected element in its own position. Insertion sort should have similiar performance characteristics (max n-1 operations), except that if you can do binary search, you have fewer comparisons too.

---

You're right, I'm not bothering with merge sort. The target list is not mergable anyway. Only one operation allowed. Also, "fewer comparisons" is not an issue, as the comparison operation is infinitely less costly than a write operation.

Anyway, you agree Selection sort would be the best solution given the clarifications on cost?

Quote:

---

Originally Posted by Nilzor

I'm not bothering with merge sort. The target list is not mergable anyway. Only one operation allowed.

---

Not quite: with just this list changing operation, merge can be used.

Quote:

---

Originally Posted by Nilzor

You agree this would be the best solution given the clarifications on cost?

---

I think both insertion sort and selection sort will be optimal.