
November 9th, 2011, 09:37 AM
#1
Specialized sorting algortihm needed
I need a sorting algorithm which operates on a single, prepopulated 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

November 9th, 2011, 09:47 AM
#2
Re: Specialized sorting algortihm needed
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.

November 9th, 2011, 09:21 PM
#3
Re: Specialized sorting algortihm needed
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 inplace 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.sortingalgorithms.com/
http://www.cs.ubc.ca/~harrison/Java/sortingdemo.html
Mike

November 10th, 2011, 01:47 AM
#4
Re: Specialized sorting algortihm needed
Selection sort can work inplace, so you just search for the smallest element, place it in its position, then continue searching the subsequent sublist. 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, inplace 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 n1 operations), except that if you can do binary search, you have fewer comparisons too.
Last edited by laserlight; November 10th, 2011 at 02:05 AM.

November 10th, 2011, 02:12 AM
#5
Re: Specialized sorting algortihm needed
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 inplace 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 "inplacewise". So conventional efficiency measurements (Onotation) 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 .NETsorted 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 .NETsortingforcomparison unnecessary.
Thank you for your answer. I'll implement it as soon as I get time and post results back here

November 10th, 2011, 02:23 AM
#6
Re: Specialized sorting algortihm needed
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 n1 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?
Last edited by Nilzor; November 10th, 2011 at 02:31 AM.

November 10th, 2011, 02:32 AM
#7
Re: Specialized sorting algortihm needed
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.
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.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
