7

Which is more expensive operation swap or comparison in integer array in Java ? Or they can all be thought as same ?

Context: Sorting for an almost sorted array (I am not talking about k-sorted array where each element is displaced from the right position by at most k). Even if we use insertion sort, number of comparisons by the end will be same as they would have been for any array or for worst case. Isn't it ? It is just that swaps will be fewer. Please correct if I am wrong.

Walt
  • 1,426
  • 2
  • 17
  • 30
  • 3
    Benchmark your code. – Maroun Jan 11 '15 at 12:46
  • 1
    But read this first: [How do I write a correct micro benchmark in Java](http://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java). – Tom Jan 11 '15 at 12:47

2 Answers2

6

Swap should be more expensive because it includes:

  1. Reading data from memory to cache
  2. Reading data from cache to registers
  3. Writing data back to cache

Comparison should be less expensive because it includes:

  1. Reading data from memory to cache
  2. Reading data from cache to registers
  3. Executing single compare operations on two registers (which should be a little faster than writing two integers into a cache)

But modern processors are complex and different from each other, so the best way to get the right answer is to benchmark your code.

Ivan Mushketyk
  • 8,107
  • 7
  • 50
  • 67
  • Did you not forgot 4: the very expensive conditional jump after compare? – MTilsted Jan 11 '15 at 12:57
  • 1
    A conditional jump may not be very expensive because of: branch prediction and level 1 code cache. The first one will save from cleaning the pipeline due to jump, the second one will save from memory access and operations decoding (one some architectures). – Ivan Mushketyk Jan 11 '15 at 13:02
  • 1
    But it seems that you are going into another area, where the right question would be to compare total running time of an algorithm due to huge number of factors such (order of element in an array included). While the question is about comparing running time of two operations. – Ivan Mushketyk Jan 11 '15 at 13:03
0

The number of comparisons in the insertion sort is related to how sorted the input is. The number of swaps s is closely related to the number of comparisons c. For an array of length n, c <= s+n-1 .

Dr. Chalam
  • 1