Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

Also author doesn't mention how time consuming shift is.

From my POV copy is the simplest pointer assignment operation. While swap is 3x pointer assignment operations. Which doesn't take much time. Also shift of N elemtns is Nx pointer assignment operations.

Please correct me if I'm wrong.

Please explain, why what author says is true? I don't understand.

share|improve this question
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 '12 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 '12 at 20:57

2 Answers 2

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.

share|improve this answer
    
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 '12 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. –  GlenPeterson Nov 18 '12 at 16:04

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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