import java.util.Arrays;

public class QuickSelect {

    // The ideal time complexity is n + n/2 + n/4 + ...=O(n)
    // The worst case is n + n-1 + n-2 + ...n - k=O(n * k)

    // But in the majority of cases, its efficiency outperform quick sort because it just works
    // on certain partitions meanwhile quick sort sorts all the partitions. This reduces the expected
    // complexity from O(n log n) to O(n), with a worst case of O(n * k).

    public static void main(String[] args) {
        int[] a = {90, 90, 67, 3, 3, 8, 43, 89, 90, 90, 1, 4, 5, 7, 5};
        a = new int[]{1,2,3,4,5,6};

        System.out.println("Before: " + Arrays.toString(a));

        int k = 4;

        quickSelect(a, 0, a.length - 1, k);

        System.out.println("After: " + Arrays.toString(a));

        System.out.println("Find " + k + "th smallest " + a[k-1]);
    }


    private static void quickSelect(int[] a, int left, int right, int k) {

        // Narrow down the search scope only stop when it reaches a range only with one element.

        if (left == right && left == k - 1) {
            return;
        }

        int pivot = (left + right) / 2;

        int i = left;
        int j = right;

        while (i < j) {
            while (i < j && a[i] <= a[pivot]) {
                i++;
            }

            while (i < j && a[j] > a[pivot]) {
                j--;
            }

            // literally, i can not be greater than j
            if (i >= j) {
                break;
            }

            swap(a, i, j);

            i++;
            j--;
        }

        // k in the left section
        if (i > k) {
            quickSelect(a, left, i - 1, k);
        }

        // k in the right section
        if (i < k) {
            quickSelect(a, i + 1, right, k);
        }
    }

    private static void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}
Copyright © iovi.com 2017 all right reserved,powered by GitbookLast Modification: 2019-12-05 13:22:08

results matching ""

    No results matching ""