In JAVA Implement iterative and recursively add explanation as well. Algorithm #

Question

In JAVA

Implement iterative and recursively add explanation as well.

Algorithm #2 idea: use "partition” (from Ouick Sort) procedure repeatedly until we find the kth smallest element. pivot position pivot 1st sub-list 2nd sub-list For each iteration: If pivot position i k Done! If pivot position i to select (k-i)h element in the 2nd sub-list If pivot position i > k to select kth element in the 1st sub-list. Best-Case is O(n) (when pivot is the kth smallest one) Worst-Case will call partition O(n) times, each time takes O(n), so Worst-Case is O(n2) procedure Algorththm#2 (4, n, k) //A is array, n is # ofarray, k is key begin m1; loop call Partition (m,j, pivotposition); case: k-pivotposition: k

Explanation / Answer

KthSmallest .java

public class KthSmallest {

    private static 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;       
      
    }

    public static int kSmall(int k, int[] arr, int first, int last){
      
           int pos = partition(arr, first, last);

           // If position is same as k
           if (pos - first == k - 1)
               return arr[pos];

           // If position is more, recur for left subarray
           if (pos - first > k - 1)
               return kSmall(k, arr, first, pos - 1);
           // Else recur for right subarray
           return kSmall(k - pos + first - 1, arr, pos + 1, last);
    }
    public static void swap(int a, int b)
    {
        int temp = a;
        a = b;
        b = temp;
    }
}

KSmallTester .java

import java.util.*;

public class KSmallTester {

    public final static int SIZE_OF_ARRAY = 10;
    public final static String PROMPT = "Please enter an integer k, 1<=k<=" +
        SIZE_OF_ARRAY + ", or 'R' to refill the array: ";

    public static void printArray(int[] array) {

        System.out.println("");
        System.out.print("array = [");
        for (int i=0; i < SIZE_OF_ARRAY-1; i++)
            System.out.print(""+ array[i]+" | ");
        System.out.println(""+ array[SIZE_OF_ARRAY-1]+"]");
        System.out.println("-------------------------------------------------"
                         + "-------------------");
    }

    public static void randFillArray(int[] array) {
        Random random = new Random();

        for (int i=0; i < SIZE_OF_ARRAY; i++)
            array[i] = random.nextInt(100);
    }

    public static void main(String argv[]) {
        int k = 1, kthSmallest = 0;
        int[] array = new int[SIZE_OF_ARRAY];
        int[] arrayTmp = new int[SIZE_OF_ARRAY];

        randFillArray(array);
        printArray(array);

        String choice=null;
        Scanner sc=new Scanner(System.in);
      
        do
       {
           System.out.println(PROMPT);
           choice = sc.nextLine();

           if (choice.equalsIgnoreCase("R")) {
               randFillArray(array);
               printArray(array);
           } else if (choice.equalsIgnoreCase("q")) {
               System.exit(0);
           } else {
               int kth = Integer.parseInt(choice);
               // Create a deep copy of array
               for (int i = 0; i < SIZE_OF_ARRAY; i++) {
                   arrayTmp[i] = array[i];
               }

               int kthSmall = KthSmallest.kSmall(kth, arrayTmp, 0, SIZE_OF_ARRAY - 1);
               System.out.println("Kth Smallest Element : " + kthSmall);
           }

       }
        while(choice!=null);

    }

}

output

array = [92 | 8 | 6 | 63 | 57 | 77 | 84 | 67 | 99 | 68]
--------------------------------------------------------------------
Please enter an integer k, 1<=k<=10, or 'R' to refill the array:
2
Kth Smallest Element : 8
Please enter an integer k, 1<=k<=10, or 'R' to refill the array:
4
Kth Smallest Element : 63
Please enter an integer k, 1<=k<=10, or 'R' to refill the array:
6
Kth Smallest Element : 77
Please enter an integer k, 1<=k<=10, or 'R' to refill the array:
R

array = [23 | 6 | 34 | 49 | 68 | 41 | 52 | 57 | 16 | 14]
--------------------------------------------------------------------
Please enter an integer k, 1<=k<=10, or 'R' to refill the array:
6
Kth Smallest Element : 41
Please enter an integer k, 1<=k<=10, or 'R' to refill the array:

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.