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.
//This is a java program to find kth smallest element form the randomly generated sequence using partitioning import java.util.Random; import java.util.Scanner; public class Kth_Smallest_Partitioning { public static int N = 20; public static int[] A = new int[N]; public static void swap(int dex1, int dex2) { int temp = A[dex1]; A[dex1] = A[dex2]; A[dex2] = temp; } public static int partition(int start, int end) { int i = start + 1; int j = i; int pivot = start; for (; i < end; i++) { if (A[i] < A[pivot]) { swap(i, j); j++; } } if (j <= end) swap(pivot, (j - 1)); return j - 1; } public static void quick_sort(int start, int end, int K) { int part; if (start < end) { part = partition(start, end); if (part == K - 1) System.out.println("kth smallest element : " + A[part]); if (part > K - 1) quick_sort(start, part, K); else quick_sort(part + 1, end, K); } return; } public static void main(String args[]) { Random random = new Random(); for (int i = 0; i < N; i++) A[i] = random.nextInt(1000); System.out.println("The original sequence is: "); for (int i = 0; i < N; i++) System.out.print(A[i] + " "); Scanner sc = new Scanner(System.in); System.out.println("\nEnter the Kth smallest you want to find: "); int k = sc.nextInt(); quick_sort(0, N, k); sc.close(); } }
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
Related posts:
What is a POJO Class?
Hướng dẫn Java Design Pattern – Prototype
Giới thiệu Json Web Token (JWT)
Java Program to Perform Arithmetic Operations on Numbers of Size
Java Program to Implement an Algorithm to Find the Global min Cut in a Graph
Spring Autowiring of Generic Types
Queue và PriorityQueue trong Java
Java Program to find the number of occurrences of a given number using Binary Search approach
Java Program to Sort an Array of 10 Elements Using Heap Sort Algorithm
Java Program to Check Whether Topological Sorting can be Performed in a Graph
Java Program to Perform String Matching Using String Library
Java Program to Find kth Largest Element in a Sequence
Java Program to Implement Ternary Search Tree
Guide to PriorityBlockingQueue in Java
Introduction to the Java NIO2 File API
Java Program to Implement Tarjan Algorithm
Converting Between an Array and a Set in Java
Rest Web service: Filter và Interceptor với Jersey 2.x (P2)
Hướng dẫn Java Design Pattern – Interpreter
Spring Cloud AWS – EC2
Zipping Collections in Java
Spring Boot - Tomcat Deployment
Java Program to Implement VList
Java toString() Method
Java Program to Print the Kind of Rotation the AVL Tree is Undergoing
Hướng dẫn Java Design Pattern – Chain of Responsibility
Java Program to Solve a Matching Problem for a Given Specific Case
Java Program to Check if a Given Graph Contain Hamiltonian Cycle or Not
Using a Custom Spring MVC’s Handler Interceptor to Manage Sessions
Java Program to Check Whether an Input Binary Tree is the Sub Tree of the Binary Tree
So sánh HashMap và Hashtable trong Java
Java Program to Find Median of Elements where Elements are Stored in 2 Different Arrays