Java – Serpent Algorithm thats implement Cipher

If the array is randomly shuffled, then in theory, one item in the list is as good as another, which means we can pick according to what is most convenient for us. However, it should be said that a middle item would be better suited when the array is almost sorted (or otherwise quicksort would take O(n^2) time). The reason for us to take the middle item is because it is likely representative of an item in which half is less and half is more in this case, and if it were random, it wouldn't make much difference otherwise, would it?

For the sake of this example, lets assume the array is randomly shuffled and so we arbitrarily name the right-most item in the list as the pivot. Starting from the left, compare that number with the pivot. If the number is less than the pivot, go to the next number. If the number is greater than the pivot then you do the following:

If the pivot is not adjacent to the current number, then the pivot switches with its left neighbor. The current number then swaps with the new slot created to the right of the new pivot. If the pivot is adjacent to the current number, then it simply switches position with the current number.

Continue these steps until the index of the current number is equal to or greater than the index of the pivot. Once this is done, perform a recursive call to a sublist of everything on the left side of the pivot and another call to a sublist of everything on the right side of the pivot (assuming length of sublist is 2 or greater).

Lets look at an example:

1 4 8 9 2 3 5

5 is our pivot. Starting with index 0, we get the following operations:

1 4 8 9 2 3 5
^           *
1 4 8 9 2 3 5
  ^         *
1 4 3 9 2 5 8
    ^     *
1 4 3 9 2 5 8
    ^     *
1 4 3 2 5 9 8
      ^ * 
1 4 3 2 5 9 8
      ^ * 

End of first pass: Recursive call to left-hand sublist:

1 4 3 2 
^     *
1 3 2 4 
  ^ *  
1 2 3 4 
  ^ *  

And recursive call to right-hand sublist:

9 8  
^ *
8 9  
* ^

I hope that clarifies things. Notice how if the current number was greater than the pivot, the current number did not increment. This is because it is replaced with another number which has not yet been handled, and so it too must be checked. I know it isn't exactly what you were doing with middle pivot, but this works just as well.

Unit tests should treat the classes they test as black boxes. The only thing which matters is that its public methods behave the way it is expected. How the class achieves this through internal state and private methods does not matter.

When you feel that it is impossible to create meaningful tests this way, it is a sign that your classes are too powerful and do too much. You should consider to move some of their functionality to separate classes which can be tested separately.