K'th Smallest/Largest Element in Unsorted Array | Set 1 - GeeksforGeeks

K'th Smallest/Largest Element in Unsorted Array | Set 1 - GeeksforGeeks

Given an array and a number k where k is smaller than size of array, we need to find the k’th largest element in the given array. It is given that ll array elements are distinct.

Method 4 (QuickSelect) 
In QuickSort, we pick a pivot element, then move the pivot element to its correct position and partition the array around it. The idea is, not to do complete quicksort, but stop at the point where pivot itself is k’th smallest element. Also, not to recur for both left and right sides of pivot, but recur for one of them according to the position of pivot. The worst case time complexity of this method is O(n²), but it works in O(n) on average.

int kthSmallest(int arr[], int l, int r, int k)

{

    // If k is smaller than number of elements in array

    if (k > 0 && k <= r - l + 1)

    {

        // Partition the array around last element and get

        // position of pivot element in sorted array

        int pos = partition(arr, l, r);

        // If position is same as k

        if (pos-l == k-1)

            return arr[pos];

        if (pos-l > k-1)  // If position is more, recur for left subarray

            return kthSmallest(arr, l, pos-1, k);

        // Else recur for right subarray

        return kthSmallest(arr, pos+1, r, k-pos+l-1);

    }

    // If k is more than number of elements in array

    return INT_MAX;

}

// Standard partition process of QuickSort().  It considers the last

// element as pivot and moves all smaller element to left of it

// and greater elements to right

int partition(int arr[], int l, int r)

{

    int x = arr[r], i = l;

    for (int j = l; j <= r - 1; j++)

    {

        if (arr[j] <= x)

        {

            swap(&arr[i], &arr[j]);

            i++;

        }

    }

    swap(&arr[i], &arr[r]);

    return i;

}

When we can't change the original array:
http://python.dzone.com/articles/computer-algorithms-order

Design an algorithm to find the smallest K numbers in an array

https://github.com/careercup/CtCI-6th-Edition/tree/master/Java/Ch%2017.%20Hard/Q17_14_Smallest_K

Approach 4: Selection Rank Algorithm (if elements are not unique)

The major change that needs to be made is to the partition function. When we partition the array around a pivot element, we now partition it into three chunks: less than pi vat, equal to pi vat, and greater than pivot.

public static class PartitionResult {
  int leftSize;
  int middleSize;
  public PartitionResult(int left, int middle) {
    this.leftSize = left;
    this.middleSize = middle;
  }
}

public static int[] smallestK(int[] array, int k) {
  if (k <= 0 || k > array.length) throw new IllegalArgumentException();
 
  int threshold = rank(array, k - 1);
  int[] smallest = new int[k];
  int count = 0;
  for (int a : array) {
    if (a < threshold) {
      smallest[count] = a;
      count++;
    }
  }
 
  while (count < k) {
    smallest[count] = threshold;
    count++;
  }
 
  return smallest;
}

/* Find value with rank k in array. */
public static int rank(int[] array, int k) {
  if (k >= array.length) {
    throw new IllegalArgumentException();
  }
  return rank(array, k, 0, array.length - 1);
}

/* Find value with rank k in sub array between start and end. */
private static int rank(int[] array, int k, int start, int end) {
  /* Partition array around an arbitrary pivot. */
  int pivot = array[randomIntInRange(start, end)];
  PartitionResult partition = partition(array, start, end, pivot);
  int leftSize = partition.leftSize;
  int middleSize = partition.middleSize;
 
  if (k < leftSize) { // Rank k is on left half
    return rank(array, k, start, start + leftSize - 1);
  } else if (k < leftSize + middleSize) { // Rank k is in middle
    return pivot; // middle is all pivot values
  } else { // Rank k is on right
    return rank(array, k - leftSize - middleSize, start + leftSize + middleSize, end);
  }
}

/* Partition result into < pivot, equal to pivot -> bigger than pivot. */
private static PartitionResult partition(int[] array, int start, int end, int pivot) {
  int left = start; /* Stays at (right) edge of left side. */
  int right = end;  /* Stays at (left) edge of right side. */
  int middle = start; /* Stays at (right) edge of middle. */
  while (middle <= right) {
    if (array[middle] < pivot) {
      /* Middle is smaller than the pivot. Left is either
       * smaller or equal to the pivot. Either way, swap
       * them. Then middle and left should move by one.
       */
      swap(array, middle, left);
      middle++;
      left++;
    } else if (array[middle] > pivot) {
      /* Middle is bigger than the pivot. Right could have
       * any value. Swap them, then we know that the new
       * right is bigger than the pivot. Move right by one.
       */
      swap(array, middle, right);
      right--;
    } else if (array[middle] == pivot) {
      /* Middle is equal to the pivot. Move by one. */
      middle++;
    }
  }
  /* Return sizes of left and middle. */
  return new PartitionResult(left - start, right - left + 1);
}

Approach 3: Selection Rank Algorithm (if elements are unique)
public static int[] smallestK(int[] array, int k) {
  if (k <= 0 || k > array.length) {
    throw new IllegalArgumentException();
  }
 
  int threshold = rank(array, k - 1);
  int[] smallest = new int[k];
  int count = 0;
  for (int a : array) {
    if (a <= threshold) {
      smallest[count] = a;
      count++;
    }
  }
  return smallest;
}

/* Get item with rank. */
public static int rank(int[] array, int rank) {
  return rank(array, 0, array.length - 1, rank);
}

/* Get element with rank between left and right indices. */
public static int rank(int[] array, int left, int right, int rank) {
  int pivot = array[randomIntInRange(left, right)];
  int leftEnd = partition(array, left, right, pivot); // returns end of left partition
  int leftSize = leftEnd - left + 1;
  if (rank == leftSize - 1) {
    return max(array, left, leftEnd);
  } else if (rank < leftSize) {
    return rank(array, left, leftEnd, rank);
  } else {
    return rank(array, leftEnd + 1, right, rank - leftSize);
  }
}

/* Partition array around pivot such that all elements <= pivot
 * come before all elements > pivot. */
public static int partition(int[] array, int left, int right, int pivot) {
  while (left <= right) {
    if (array[left] > pivot) {
      /* Left is bigger than pivot. Swap it to the right
       * side, where we know it should be. */
      swap(array, left, right);
      right--;
    } else if (array[right] <= pivot) {
      /* Right is smaller than the pivot. Swap it to the
       * left side, where we know it should be. */
      swap(array, left, right);
      left++;
    } else {
      /* Left and right are in correct places. Expand both
       * sides. */
      left++;
      right--;
    }
  }
  return left - 1;
}
/* Get random integer within range, inclusive. */
public static int randomIntInRange(int min, int max) {
  Random rand = new Random();
  return rand.nextInt(max + 1 - min) + min;
}

public static class MaxHeapComparator implements Comparator<Integer> {
   public int compare(Integer x, Integer y) {
       return y - x;
   }
}

public static int[] smallestK(int[] array, int k) {
if (k <= 0 || k > array.length) {
throw new IllegalArgumentException();
}

PriorityQueue<Integer> heap = getKMaxHeap(array, k);
return heapToIntArray(heap);
}

/* Convert heap to int array. */
public static int[] heapToIntArray(PriorityQueue<Integer> heap) {
int[] array = new int[heap.size()];
while (!heap.isEmpty()) {
array[heap.size() - 1] = heap.poll();
}
return array;
}

/* Create max heap of smallest k elements. */
public static PriorityQueue<Integer> getKMaxHeap(int[] array, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<Integer>(k, new MaxHeapComparator());
for (int a : array) {
if (heap.size() < k) { // If space remaining
heap.add(a);
} else if (a < heap.peek()) { // If full and top is small
heap.poll(); // remove highest
heap.add(a); // insert new element
}
}
return heap;
}

public static int[] smallestK(int[] array, int k) {
  if (k <= 0 || k > array.length) {
    throw new IllegalArgumentException();
  }
 
  /* Sort array. */
  Arrays.sort(array);
 
  /* Copy first k elements. */
  int[] smallest = new int[k];
  for (int i = 0; i < k; i++) {
    smallest[i] = array[i];
  }
  return smallest;
}
Read full article from K'th Smallest/Largest Element in Unsorted Array | Set 1 - GeeksforGeeks