Question

Use quickselect algorithm to implement the two algorithms for finding the kth smallest integer in a set of integers.

MUST USE JAVA AND QUICKSELECT.

Algorithm 1:

Procedure SELECT( k,S)

{ if ISI =1 then return the single element in S

   else { choose an element randomly from S;

              let S1, S2, and S3 be the 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);

             }

}

Algorithm 2:

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);  

    let S1,S2,and S3 be the 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);

}

Answer 1

PROGRAM :

File: FindingKthSmallest.java

// FindingKthSmallest class implementation
import java.util.Random;
import java.util.Scanner;
public class FindingKthSmallest
{
private static Random rand = new Random();
private static Scanner keyboard = new Scanner(System.in);

// implementation of Algorithm #1
public static int select1(int k, int[] S)
{
if (S.length == 1)
return S[0];

int m = S[rand.nextInt(S.length)];
int[] S1 = new int[S.length];
int[] S2 = new int[S.length];
int[] S3 = new int[S.length];
int p = 0;
int q = 0;
int r = 0;

for (int i = 0; i < S.length; i++)
{
if (S[i] < m)
{
S1[p] = S[i];
p++;
}
else if (S[i] == m)
{
S2[q] = S[i];
q++;
}
else
{
S3[r] = S[i];
r++;
}
}

S1 = trimToSize(S1, p);
S2 = trimToSize(S2, q);
S3 = trimToSize(S3, r);

if (S1.length >= k)
return select1(k, S1);
else if (S1.length + S2.length >= k)
return m;
else
return select1(k - S1.length - S2.length, S3);
}

// implementation of Algorithm #2
public static int select2(int k, int[] S)
{
if (S.length < 50)
{
sort(S, 0, S.length - 1);
return S[k - 1];
}

for (int i = 0; i < S.length; i += 5)
{
if (i + 4 < S.length)
sort(S, i, i + 4);
else
sort(S, i, S.length - 1);
}
  
int[] M = new int[(int)Math.ceil(S.length / 5.0)];
  
for (int i = 0, j = 0; i < S.length; i += 5, j++)
{
if (i + 4 < S.length)
M[j] = S[(2 * i + 4) / 2];
else
M[j] = S[(i + S.length - 1) / 2];
}

int m = select2(M.length / 2 + 1, M);
int[] S1 = new int[S.length];
int[] S2 = new int[S.length];
int[] S3 = new int[S.length];
int p = 0;
int q = 0;
int r = 0;

for (int i = 0; i < S.length; i++)
{
if (S[i] < m)
{
S1[p] = S[i];
p++;
}
else if (S[i] == m)
{
S2[q] = S[i];
q++;
}
else
{
S3[r] = S[i];
r++;
}
}

S1 = trimToSize(S1, p);
S2 = trimToSize(S2, q);
S3 = trimToSize(S3, r);

if (S1.length >= k)
return select2(k, S1);
else if (S1.length + S2.length >= k)
return m;
else
return select2(k - S1.length - S2.length, S3);
}
  
// trimToSize helper method
private static int[] trimToSize(int[] arr, int size)
{
int[] temp = new int[size];
for (int i = 0; i < size; i++)
{
temp[i] = arr[i];
}
return temp;
}

// sort helper method
private static void sort(int arr[], int begin, int end)
{
if (begin < end)
{
int pivot = arr[end];
int i = (begin - 1);

for (int j = begin; j < end; j++)
{
if (arr[j] <= pivot)
{
i++;

int swapTemp = arr[i];
arr[i] = arr[j];
arr[j] = swapTemp;
}
}

int swapTemp = arr[i + 1];
arr[i + 1] = arr[end];
arr[end] = swapTemp;

int partitionIndex = i + 1;

sort(arr, begin, partitionIndex - 1);
sort(arr, partitionIndex + 1, end);
}
}
  
// printArray method to print the array of integers
public static void printArray(int[] S)
{
for(int i = 0; i < S.length; i++)
{
System.out.print(S[i] + "\t");
if(i % 10 == 9)
System.out.println();
}
}

// start main method
public static void main(String[] args)
{
System.out.print("Enter the size of an array: ");
int size = keyboard.nextInt();
while(size < 1)
{
System.out.println("Size of the array should be greater than 0.");
System.out.print("Enter the size of an array: ");
size = keyboard.nextInt();
}
  
System.out.print("Enter the value of k: ");
int k = keyboard.nextInt();
while(k < 1 || k > size)
{
System.out.println("Value of k should be in the range 1-" + size + ".");
System.out.print("Enter the value of k: ");
k = keyboard.nextInt();
}
  
// fill the array with the random integers in the range [100, 999]
int[] S = new int[size];
for(int i = 0; i < size; i++)
{
S[i] = 100 + rand.nextInt(900);
}
  
System.out.println("\nRandom values generated in the array:");
printArray(S);
System.out.println();
  
System.out.println(k + "th smallest value in the array using Algorithm #1: " + select1(k, S));
System.out.println(k + "th smallest value in the array using Algorithm #2: " + select2(k, S));

} // end of main method
} // end of FindingKthSmallest class

Sample Output: