public class Partitioningextends ObjectGiven some interval boundaries, partitions arrays such that all elements falling into an interval are placed next to each other.
The algorithms partition arrays into two or more intervals. They distinguish between synchronously partitioning either one, two or three arrays. They further come in templated versions, either partitioning int arrays or double arrays.
You may want to start out reading about the simplest case: Partitioning one int array into two intervals. To do so, read
partition(int,int,int,int). Next, building upon that foundation comes a method partitioning int arrays into multiple intervals. See
partition(int,int,int,int,int,int,int)for related documentation.
All other methods are no different than the one's you now already understand, except that they operate on slightly different data types.
Partitioning into two intervals is O( N ). Partitioning into k intervals is O( N * log(k)). Constants factors are minimized. No temporary memory is allocated; Partitioning is in-place.
- See Also: