Archived

This topic is now archived and is closed to further replies.

Xorcist

What is meant by an "In-Place" Sort?

Recommended Posts

I''m a little fuzzy on this, and most of the resources I''ve come across explain it pretty bad. Can someone here give me the quick and easy behind how an "In-Place" sort differs from any other type of sorting.

Share this post


Link to post
Share on other sites
I''d imagine it would be a sort that doesn''t move the objects in memory. For example a link list can be sorted by adjusting the next and previous pointers, but the data is never moved, and pointers to the nodes are still valid.

This is good when you want to keep pointers to items, and in cases where the data is huge, and moving it all around would consume more time than anything else.

Things that aren''t linked lists (or similar data structure) can be in-place sorted by sorting a set of pointers to the data elements.

Share this post


Link to post
Share on other sites
Well I'm working on a problem where by I have to "merge" two sorted listed "in-place", and it's given that the lists are the first and second halves of a single array. In the end the entire array should be sorted (through a single merge procedure).

I've seen definitions that say "in-place" means using no auxilary memory (don't know how I'd do this with an array), using constant auxilary memory (this seems feasible given a simple "swap" context), and then I've seen examples done of "in-place" merge sorts that don't variable auxilary memory. Which is what has got me so confused. Since nothing matches up.

Kinda hard to complete a task given you don't understand exactly what guidelines your suppposed to be following.

Is this a correct definition?
http://www.nist.gov/dads/HTML/inplacesort.html




[edited by - Xorcist on October 5, 2003 7:03:48 PM]

Share this post


Link to post
Share on other sites
Anything you see on that site, you can pretty much guarantee it''s a common and/or complete description...

So, not quite like I said. Data must occupy the same memory after the sort, but I suppose the elements may occupy different parts of that memory... just that no additional memory use used aside from temp sorting storage.

BTW, Merge sort IS in-place (even using my previous definition) for linked lists. Merge sort for arrays requires extra storage, but for linked lists the only extra overhead is for a temporary new list header.

Share this post


Link to post
Share on other sites
An in-place sort basically means the sorted list is the same list as the unsorted list.

Also, a merge sort isn''t necessarily an in-place sort no matter what data structure you use. It all depends on the implementation of the algorithm, because you can always store the sorted items in a new list(be it a ll, or an array)

Kory Spansel

Share this post


Link to post
Share on other sites
In-place and sort don't belong together, that's why you're not finding reliable information on it. They may have meant stable sort (the order of equivalent elements remains in the same order). In-place typically means it does not require more memory to execute. Almost all sorts are in-place, except large merge sorts (even most merge sorts are in-place).

a defintion

[edited by - Magmai Kai Holmlor on October 6, 2003 8:44:05 PM]

Share this post


Link to post
Share on other sites
Magmai Kai Holmlor - What you said is technically true but it speaks of the optimum. This guy is obviously doing some homework problem where in-place is redundantly specified to prevent laziness. As you stated, almost all sort algorithms may be performed in-place, yet that does not lend itself as the most trivial implementation.

An in place sort must merely perform the sort without alocating additional memory, minus 1 temporary which is nearly always required for the swap operation.

I must disagree with the link definition you provided because simply occupying the same memory addresses of the original sequence, as stated in the definition, does not dictate any thing about the nature of the algorithm and how much memory it can allocate which is the very heart of the definition of inplace sorting (not allocating any addition memory during the sorting algorithm).


EDIT: Ok I read the link on the link you provided, who am I to argue with N.I.S.T., but I still disagree with the first link


[edited by - duke on October 6, 2003 9:54:03 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Magmai Kai Holmlor
In-place and sort don't belong together, that's why you're not finding reliable information on it. They may have meant stable sort (the order of equivalent elements remains in the same order). In-place typically means it does not require more memory to execute. Almost all sorts are in-place, except large merge sorts (even most merge sorts are in-place).

In-place means it requires *constant* extra memory, rather than linear extra memory. It doesn't preclude having /some/ extra memory (stack variables, if nothing else, will probably take memory).

I disagree with your claim that almost all sorts are in-place. Very often one has to expend considerable effort to achieve this. The standard quicksort algorithm, for instance, is not in-place. True, there are clever C implementations that do manage to be in-place, but any naive implementation will not be. The same is true of things such as merge sorts and radix sorts. Whilst they can be cunningly written to be in-place, typical implementations will not be.

The only sorts that come to mind that are "obviously" in-place (i.e. would be in-place even in a naive implementation) are the various O(N^2) algorithms.


[edited by - DrPizza on October 7, 2003 9:01:46 AM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
This is also one definition that is sometimes used. It has nothing to do with the algorithm, but more with the interface.

//in-place sort
array = [2,3,1]
sort(array)
print array //prints [1,2,3]

//not in-place sort:
array = [2,3,1]
array2 = sorted(array)
print array //prints [2,3,1]. was not sorted in-place
print array2 //prints [1,2,3]. the sorted array was returned

The underlying sort could be any sort algo, naturally. Some algos are just better suited for in-place sorting and some are better suited for non-in-place sorting (i.e. they put the sorting results in a separate space anyway, and to be in-place they''d have to copy this data to the original place).

Share this post


Link to post
Share on other sites