FINDING KTH SMALLEST IN THE SET S ONLY USE ONE ARRAY WHICH CONTAIN ALL THE INTEG
ID: 3753089 • Letter: F
Question
FINDING KTH SMALLEST IN THE SET S
ONLY USE ONE ARRAY WHICH CONTAIN ALL THE INTEGERS***
Implement the algorithm into java for finding the kth smallest integer using only one array that contains all the integers.
Procedure SELECT(k,S)
{ if ISI<50 then { sort S; return the kth smallest element;}
else
{ divide S into ISI/5 sequences of 5 elements each with up
to four leftover elements;
sort each 5-element sequence;
let M be the sequence of the medians of the 5-element sets;
let m= SELECT( M/2, M); // where M/2 indicates the //smallest integer greater than M/2
let S1,S2,and S3 be he sequences of elements in S
less than, equal to, and greater than m, respectively;
if IS1I >=k then return SELECT(k,S1)
else
if (IS1I + IS2I >=k then return m
else return SELECT(k-IS1I-IS2I , S3); }
Explanation / Answer
Answer is :
i have used QuickSort method
import java.util.Arrays;
import java.util.Collections;
class GFG
{
// It considers the last element as pivot
// and moves all smaller element to left of
// it and greater elements to right
public static int partition(Integer [] arr, int l,
int r)
{
int x = arr[r], i = l;
for (int j = l; j <= r - 1; j++)
{
if (arr[j] <= x)
{
//Swapping arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
}
}
//Swapping arr[i] and arr[r]
int temp = arr[i];
arr[i] = arr[r];
arr[r] = temp;
return i;
}
// This function returns k'th smallest element
// in arr[l..r] using QuickSort based method.
// ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
public static int kthSmallest(Integer[] 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 position is more, recur for
// left subarray
if (pos-l > k-1)
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 Integer.MAX_VALUE;
}
// Driver program to test above methods
public static void main(String[] args)
{
Integer array1[] = new Integer[]{12, 3, 5, 7, 4, 19, 26};
int k = 1;
System.out.print( "K'th smallest element in a array is " +
kthSmallest(array1, 0, array1.length - 1,k ) );
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.