I came across some code I wrote that was prefixed with the term 'in-place'. I had forgotten what it meant so to refresh my memory: it transforms input using a "constant amount of extra storage space" [1]. Lafore defines it as "meaning beside the initial array, very little extra memory is required." [2]
Sedgewick [3] uses the example of a mergesort where "it would be much more desirable to have an in-place method so that we could sort the first half of the array in place, then sort the second half of the array in place, then do the merge of the two halves by moving the items around within the array, without using a significant amount of extra space."
Cuckoo hashing is also an in-place algorithm.
[1] Wikipedia.
[2] Data Structure and Algorithms in Java, Robert Lafore
[3] Algorithms, Sedgewick.
Sedgewick [3] uses the example of a mergesort where "it would be much more desirable to have an in-place method so that we could sort the first half of the array in place, then sort the second half of the array in place, then do the merge of the two halves by moving the items around within the array, without using a significant amount of extra space."
Cuckoo hashing is also an in-place algorithm.
[1] Wikipedia.
[2] Data Structure and Algorithms in Java, Robert Lafore
[3] Algorithms, Sedgewick.
No comments:
Post a Comment