Implement kSmall, finding the smallest item in an array, as a java method. Use t
ID: 3751028 • Letter: I
Question
Implement kSmall, finding the smallest item in an array, as a java method. Use the first item of the array as the pivot. Develop a test plan for this method. Include a box trace on a small sized problem to show the algorithm works. For actual operational testing, include details on your array(s) under test; size, randomness, generation method. Design tests to determine performance difference between unsorted, nearly sorted and sorted arrays. I need writing the code I keep getting stuck. I also need help with the testing class.
Pseudocode algorithm for the kSmall method
// Assume all values in S are unique.
kSmall(int [] S, int k): int (value of k-smallest element)
pivot = arbitrary element from S: let’s use the first element.
S1 = < all elements from S less than pivot > // these two steps will require some thought
S2 = < all elements from S greater than pivot > // and need to be implemented
if k <= S1.length
return kSmall(S1, k)
else if k == S1.length + 1
return pivot
else
return kSmall(S2, k – S1.length – 1)
Explanation / Answer
class KthSmallst
{
// This function returns k'th smallest element in arr[l..r]
// using QuickSort based method. ASSUMPTION: ALL ELEMENTS
// IN ARR[] ARE DISTINCT
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 a random element and
// get position of pivot element in sorted array
int pos = firstelementPartition(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;
}
// Utility method to swap arr[i] and arr[j]
void swap(int arr[], int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 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. This function
// is used by firstelementPartition()
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, j);
i++;
}
}
swap(arr, i, r);
return i;
}
// Picks a first element as pivot element between l and r and
int firstelementPartition(int arr[], int l, int r)
{
int n = r-l+1;
int pivot = (int)(Math.random()) * (n-1);
swap(arr, l + pivot, r);
return partition(arr, l, r);
}
// Driver method to test above
public static void main(String args[])
{
KthSmallst ob = new KthSmallst();
int arr[] = {12, 3, 5, 7, 4, 19, 26};
int n = arr.length,k = 3;
System.out.println("K'th smallest element is "+
ob.kthSmallest(arr, 0, n-1, k));
}
}
*** you dont actually need to calculate s1 and s2 sizes the index of the pivot in final sorted list will help you get those sizes.
** but if you take pivot as first element sorted array will be the worst case as you will be checking for each element in a sequential way. dry run code for sorted array you can understand the reason. its better to randomize the pivot element index rather than taking first one.
* regarding the testing plan you can directly use System.currentTimeMillis() to get the current time before execution of logic and get after execution of logic. get the difference to get time taken for running code.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.