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: lets 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)

Here is some code that someone helped me with I need to be able to test all 3 arrays at the same time a sorted, nearlysorted and random array. I also need the times to be displayed for each array.

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.

I am not sure how to get the arrays to display all 3 with test times displayed?