static int expandPartition()

in commons-numbers-arrays/src/main/java/org/apache/commons/numbers/arrays/QuickSelect.java [2307:2405]

• 66 lines of code
• 16 McCabe index (conditional complexity)

    static int expandPartition(int[] a, int left, int right, int start, int end,
        int pivot0, int pivot1, int[] upper) {
        // 3-way partition of the data using a pivot value into
        // less-than, equal or greater-than.
        // Based on Sedgewick's Bentley-McIroy partitioning: always swap i<->j then
        // check for equal to the pivot and move again.
        //
        // Move sentinels from start and end to left and right. Scan towards the
        // sentinels until >=,<=. Swap then move == to the pivot region.
        //           <-i                           j->
        // |l |        |            |p0  p1|       |             | r|
        // |>=|   ???  |     <      |  ==  |   >   |     ???     |<=|
        //
        // When either i or j reach the edge perform finishing loop.
        // Finish loop for a[j] <= v replaces j with p1+1, optionally moves value
        // to p0 for < and updates the pivot range p1 (and optionally p0):
        //                                             j->
        // |l                       |p0  p1|           |         | r|
        // |         <              |  ==  |       >   |   ???   |<=|

        final int v = a[pivot0];
        // Use start/end as sentinels (requires start != end)
        int vi = a[start];
        int vj = a[end];
        a[start] = a[left];
        a[end] = a[right];
        a[left] = vj;
        a[right] = vi;

        int i = start + 1;
        int j = end - 1;

        // Positioned for pre-in/decrement to write to pivot region
        int p0 = pivot0 == start ? i : pivot0;
        int p1 = pivot1 == end ? j : pivot1;

        while (true) {
            do {
                --i;
            } while (a[i] < v);
            do {
                ++j;
            } while (a[j] > v);
            vj = a[i];
            vi = a[j];
            a[i] = vi;
            a[j] = vj;
            // Move the equal values to pivot region
            if (vi == v) {
                a[i] = a[--p0];
                a[p0] = v;
            }
            if (vj == v) {
                a[j] = a[++p1];
                a[p1] = v;
            }
            // Termination check and finishing loops.
            // Note: This works even if pivot region is zero length (p1 == p0-1 due to
            // length 1 pivot region at either start/end) because we pre-inc/decrement
            // one side and post-inc/decrement the other side.
            if (i == left) {
                while (j < right) {
                    do {
                        ++j;
                    } while (a[j] > v);
                    final int w = a[j];
                    // Move upper bound of pivot region
                    a[j] = a[++p1];
                    a[p1] = v;
                    // Move lower bound of pivot region
                    if (w != v) {
                        a[p0] = w;
                        p0++;
                    }
                }
                break;
            }
            if (j == right) {
                while (i > left) {
                    do {
                        --i;
                    } while (a[i] < v);
                    final int w = a[i];
                    // Move lower bound of pivot region
                    a[i] = a[--p0];
                    a[p0] = v;
                    // Move upper bound of pivot region
                    if (w != v) {
                        a[p1] = w;
                        p1--;
                    }
                }
                break;
            }
        }

        upper[0] = p1;
        return p0;
    }