Java Program to Find kth Smallest Element in Array using Partitioning

This is a java program to find kth smallest element form the given sequence of numbers. This could be solved by using Quick sort algorithm, where we partition around the pivot element, the entire sequence of numbers is broken down to two, we arrange the number such that numbers smaller than pivot is kept in the first sequence and numbers larger than the pivot is kept in the second sequence. During this comparison we find the kth smallest element.

Here is the source code of the Java Program to Find kth Smallest Element by the Method of Partitioning the Array. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to find kth smallest element form the randomly generated sequence using partitioning
  2. import java.util.Random;
  3. import java.util.Scanner;
  4.  
  5. public class Kth_Smallest_Partitioning 
  6. {
  7.     public static int N = 20;
  8.     public static int[] A = new int[N];
  9.  
  10.     public static void swap(int dex1, int dex2) 
  11.     {
  12.         int temp = A[dex1];
  13.         A[dex1] = A[dex2];
  14.         A[dex2] = temp;
  15.     }
  16.  
  17.     public static int partition(int start, int end) 
  18.     {
  19.         int i = start + 1;
  20.         int j = i;
  21.         int pivot = start;
  22.         for (; i < end; i++) 
  23.         {
  24.             if (A[i] < A[pivot]) 
  25.             {
  26.                 swap(i, j);
  27.                 j++;
  28.             }
  29.         }
  30.         if (j <= end)
  31.             swap(pivot, (j - 1));
  32.  
  33.         return j - 1;
  34.     }
  35.  
  36.     public static void quick_sort(int start, int end, int K) {
  37.         int part;
  38.         if (start < end) 
  39.         {
  40.             part = partition(start, end);
  41.             if (part == K - 1)
  42.                 System.out.println("kth smallest element : " + A[part]);
  43.             if (part > K - 1)
  44.                 quick_sort(start, part, K);
  45.             else
  46.                 quick_sort(part + 1, end, K);
  47.         }
  48.         return;
  49.     }
  50.  
  51.     public static void main(String args[]) 
  52.     {
  53.         Random random = new Random();
  54.         for (int i = 0; i < N; i++)
  55.             A[i] = random.nextInt(1000);
  56.  
  57.         System.out.println("The original sequence is:  ");
  58.         for (int i = 0; i < N; i++)
  59.             System.out.print(A[i] + " ");
  60.         Scanner sc = new Scanner(System.in);
  61.         System.out.println("\nEnter the Kth smallest you want to find: ");
  62.         int k = sc.nextInt();
  63.  
  64.         quick_sort(0, N, k);
  65.         sc.close();
  66.     }
  67. }

Output:

$ javac Kth_Smallest_Partitioning.java
$ java Kth_Smallest_Partitioning
 
The original sequence is:  
811 30 934 118 942 89 855 917 474 194 630 887 916 997 851 550 917 841 343 202 
Enter the Kth smallest you want to find: 
3
kth smallest element : 118

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.