2

From Lafore's "Data Structures and Algorithms in Java": (about insertion sort (which uses copy + shift instead of swap (used in bubble and selection sort)))

However, a copy isn’t as time-consuming as a swap, so for random data this algo- rithm runs twice as fast as the bubble sort and faster than the selectionsort.

Additionally, the author doesn't mention how time consuming shift is.

It seems that copying is the simplest pointer assignment operation. While swap is 3 pointer assignment operations, which don't take much time. Further, shift of N elements is N pointer assignment operations.

Can someone explain this seeming inconsistency?

2
  • 1
    To provide another view on swaps in terms of general computing and not just Java, for example on x86 native code there exists a XCHG instruction which effectively swaps or exchanges two values within a single clock cycle. I am not sure if Java Bytecode has such an instruction though, or if there's a Java VM implementation which could delegate a swap to a single XCHG instruction on x86 - but at least I think there's nothing which would prevent that from happening - which would mean that a swap operation would actually be just as fast as overwriting a variable with another.
    – zxcdw
    Nov 14, 2012 at 15:52
  • AFAIK, Java 5 has 'compareAndSet' atomic operation (which is used in concurrent applications), so I believe that it can optimize swap to be a single instruction. Because of this I'm even more confused about what author says.
    – dhblah
    Nov 17, 2012 at 20:57

2 Answers 2

2

a copy isn’t as time-consuming as a swap

Let's compare a copy to a swap:

int[] a = ...
int idx = ...

// copy:
a[idx] = a[idx + 1];

// swap:
int temp = a[idx];
a[idx] = a[idx + 1];
a[idx + 1] = temp;

Swap allocates a temporary variable performs and three copies - one from the array to the temporary variable, one from one index at the array to another, and one from the temporary variable back to the array. Therefore a swap is at least 3 times as expensive as a copy.

Shifting elements in an array (as opposed to shifting bits in a primitive integer type) is expensive because it is repeated copying:

for (int i = shiftEnd - 1; i >= shiftStart; i--) {
  a[i + 1] = a[i];
}

You can see here that when (shiftEnd - shiftStart) > 3 a shift will perform more copy operations than a swap.

Let's look at the same example with an array of pointers to objects instead of primitive ints:

Object[] a = ...

// copy the pointer to an object from one array element to another
a[idx] = a[idx + 1]; 

// swap the pointer to an object between array elements
Object temp = a[idx];
a[idx] = a[idx + 1];
a[idx + 1] = temp;

You will notice that these operations are exactly the same whether dealing with primitives or objects. The List version is more expensive due to the method-call overhead of accessing the list. Most List implementations use multiple arrays to allow resizing of the list which is more expensive than using a single, fixed-length primitive array.

1
  • While copying is faster than swapping for primitives, or for .NET or Java heap-object references, in languages like C++ a swap operation may sometimes be much faster than a copy. Further, while the list-related interfaces in Java and .NET don't happen to support a Swap operation, a method to swap two items in a list could be used without the caller having to know the type in question, which would allow code which can sort a ReadablePermutableList<Animal> to also work on a ReadablePermutableList<SiameseCat>.
    – supercat
    Mar 17, 2015 at 22:03
1

You aren't doing one swap/copy you are doing roughly n log(n) swaps/copies. So you get 3n log(n) assignments for swapping or n log(n) + n assignments for copy.

2
  • Well, if compare bubble sort and insertion sort, in case of bubble sort we're doing n^2 swaps (n*(n-1)/2 to be precise, but for big O notation it doesn't matter), right? in case of insertion sort we're doing n^2 copies. So in first case we're doing 9n^2 copies (if 3 copies = 1 swap), and in second case we're doing n^2 copies. So anyway, for big O notation, we're doing same amount of copies and because copy as I believe is very fast 9n^2 is almost the same as n^2. Please correct me if I'm wrong.
    – dhblah
    Nov 17, 2012 at 20:49
  • Yes, big O notation ignores constant factors. Thus your 9n^2 algorithm will be 9 times as expensive as your n^2 for every sufficiently large value of n even though they have the same big O notation. Big O only cares that they grow at the same rate as n increases, even if one algorithm is always more expensive than the other. Maybe you will some day run on a machine that has a swap operation that's faster than it's copy operation? Big O doesn't care (Honey Badger Don't Care!). It's only interested in growth as n increases. Nov 18, 2012 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.