Skip to main content
explained the final swap
Source Link
David Harkness
  • 8.8k
  • 1
  • 26
  • 44

Micro-Optimization

The final swap when picking the median is a micro-optimization that moves the pivot into the partition where it would eventually be placed, bypassing a needless comparison with itself.

Given the layout before the swap,

[ left . . . . . pivot . . . . . right ]

these facts,

  1. left < pivot
  2. pivot < right
  3. pivot = pivot

and this partitioning logic:

for every element
    if (element < pivot)
        move element to left half
    else
        move element to right half

we can make some minor optimizations by skipping the comparison for left, right, and pivot since we know into which partition they should land. The first two are already in their correct partitions, so we start by shifting in the looping terminals one slot. By performing a swap to place pivot into the second-to-last slot, we can skip comparing it as well. Here it must be placed at the far right end of the partition, next to right.

swap(arr, middle, right - 1);

which leaves this new layout:

[ left . . . . . . . . . . pivot right ]
       ^ partition these ^

If the partition comparison used <= instead of <, you'd swap the pivot into the second slot instead.

swap(arr, middle, left + 1);

[ left pivot . . . . . . . . . . right ]
             ^ partition these ^

Timing Variations

Timing Variations

Micro-Optimization

The final swap when picking the median is a micro-optimization that moves the pivot into the partition where it would eventually be placed, bypassing a needless comparison with itself.

Given the layout before the swap,

[ left . . . . . pivot . . . . . right ]

these facts,

  1. left < pivot
  2. pivot < right
  3. pivot = pivot

and this partitioning logic:

for every element
    if (element < pivot)
        move element to left half
    else
        move element to right half

we can make some minor optimizations by skipping the comparison for left, right, and pivot since we know into which partition they should land. The first two are already in their correct partitions, so we start by shifting in the looping terminals one slot. By performing a swap to place pivot into the second-to-last slot, we can skip comparing it as well. Here it must be placed at the far right end of the partition, next to right.

swap(arr, middle, right - 1);

which leaves this new layout:

[ left . . . . . . . . . . pivot right ]
       ^ partition these ^

If the partition comparison used <= instead of <, you'd swap the pivot into the second slot instead.

swap(arr, middle, left + 1);

[ left pivot . . . . . . . . . . right ]
             ^ partition these ^

Timing Variations

Source Link
David Harkness
  • 8.8k
  • 1
  • 26
  • 44

Sorting the Three

You only need at most three swaps to sort the three elements:

  • at most two swaps to place the smallest element into the first slot since it must be compared to the other two, and
  • at most one swap to order the remaining two elements.

How does this line up with there being 3! permutations? Consider that each permutation requires at most two swaps to create. The worst case is (3, 2, 1) which takes only one swap to create from (1, 2, 3)--swap 1 and 3--requires all three swaps to revert using the brute-force algorithm:

3 2 1    // swap 3 and 2
2 3 1    // swap 2 and 1
1 3 2    // swap 3 and 2
1 2 3

I'm sure someone here can provide a nice proof, but I'm satisfied by examination that it is correct and sufficient.

Timing Variations

The runtime of sorting algorithms can be greatly affected by the initial order of the elements. Each algorithm has a best and worst case initial ordering. For example, Bubble Sort requires \$O(n^2)\$ swaps when given the elements in reverse order and none when already sorted.

Even by sorting one million arrays, when you run the program again you start with a new random seed which produces an entirely different set of random arrays. One seed may produce a higher percentage of worst cases. You can remove this element by choosing a random seed to use on every run with Random.setSeed.

In addition to that--and probably responsible for more of the outliers--you are calculating wall clock time. If the system swaps out your program to do other work, the clock keeps running. You can mitigate this by timing at the system level (e.g. using time on Linux) which will track wall clock, CPU, and system time.

Finally, the smaller arrays will involve a higher ratio of overhead compared to the actual sorting work. I recommend fewer repetitions with larger arrays, say sort 10,000 arrays of size 10,000. You may also want to consider creating initial arrays by shuffling the numbers \$(1..N)\$ to remove the unpredictable effects of equal elements.