What is meant by an "In-Place" Sort?
Author
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.
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.
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.
yeah,
sorts like merge sort are not inplace as they sepparate the array into separate subgroups to sort smaller and smaller arrays
(recursion).
sorts like merge sort are not inplace as they sepparate the array into separate subgroups to sort smaller and smaller arrays
(recursion).
Author
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]
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]
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.
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.
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
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
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]
a defintion
[edited by - Magmai Kai Holmlor on October 6, 2003 8:44:05 PM]
One key example of a sort that is NOT in-place is a radix sort.
How appropriate. You fight like a cow.
How appropriate. You fight like a cow.
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]
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]
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]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
