K-Smallest Elements In An Array
Find the k-smallest elements in an array of A of n elements.
Kth Index Algorithm:
- Find pivot_index using partition
- Iterate till k-l !=
- if k-1 < pivot_index then
- Set end = pivot_index – 1
- else
- Set start = pivot_index + 1
- Recursively call with start and end
- if k-1 < pivot_index then
- return pivot_index
Partition Algorithm:
- Set pivot = array[end]
- Set pivot_index = start
- Iterate from start to end of
- If array[i] < pivot then
- Swap ith index data with pivot_index data
- Increase pivot_index by 1
- If array[i] < pivot then
- Swap pivot_index with end_index
- return pivot_index
Source Code:
Github: KSmallestFinder.java
Output:
Before sort: 7 3 18 9 1 2 15 12 5 After sort: 1 2 3 5 7 9 12 15 18