Specialized sorting algortihm needed
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 7 of 7

Thread: Specialized sorting algortihm needed

  1. #1
    Join Date
    Nov 2011
    Posts
    4

    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

  2. #2
    Join Date
    Nov 2011
    Posts
    4

    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.

  3. #3
    Join Date
    Nov 2002
    Location
    California
    Posts
    4,553

    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 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

  4. #4
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,194

    Re: Specialized sorting algortihm needed

    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.
    Last edited by laserlight; November 10th, 2011 at 02:05 AM.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  5. #5
    Join Date
    Nov 2011
    Posts
    4

    Re: Specialized sorting algortihm needed

    Quote Originally Posted by MikeAThon View Post
    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

  6. #6
    Join Date
    Nov 2011
    Posts
    4

    Re: Specialized sorting algortihm needed

    Quote Originally Posted by laserlight View Post
    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?
    Last edited by Nilzor; November 10th, 2011 at 02:31 AM.

  7. #7
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,194

    Re: Specialized sorting algortihm needed

    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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center