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:
Java Program to Check Whether it is Weakly Connected or Strongly Connected for a Directed Graph
How to Read a Large File Efficiently with Java
Guava – Join and Split Collections
Most commonly used String methods in Java
Retrieve User Information in Spring Security
An Intro to Spring Cloud Security
Marker Interface trong Java
Updating your Password
Giới thiệu Google Guice – Injection, Scope
Java Program to Solve the Fractional Knapsack Problem
Java Program to Implement Pagoda
Java Program to Implement Kosaraju Algorithm
Java Program to Implement the Vigenere Cypher
Java Program to Use rand and srand Functions
Java Program to Implement HashSet API
Java Program to implement Bit Set
Spring Cloud AWS – EC2
Concatenating Strings In Java
Spring Boot - Interceptor
Thực thi nhiều tác vụ cùng lúc như thế nào trong Java?
Java Program to Check Cycle in a Graph using Topological Sort
Converting Iterator to List
Handle EML file with JavaMail
A Guide to Concurrent Queues in Java
Pagination and Sorting using Spring Data JPA
How to Iterate Over a Stream With Indices
A Guide to Java HashMap
Spring WebClient Requests with Parameters
Java Program to Implement the String Search Algorithm for Short Text Sizes
Java Concurrency Interview Questions and Answers
Java Program to Implement Red Black Tree
Spring Boot - Tracing Micro Service Logs