Find k smallest integer in an array
Here is my code, it works for finding the 1-7 smallest integers, but 8 and 9. It returns null when I find the 8 smallest numbers in the array. Can anyone help me where is the problem? I am using quicksort here. Many thanks!
update: I figured out the problem, which is an array in the main function. After I move on to the next view,
int[] arr = {2, 3, 1, 7, 5, 6, 20, 8, 4, 9};
and
if(front>=end) return input;
Now it works!
import java.util.Arrays;
import java.io.*;
class quicksort{
public static void main(String[] args){
int[] arr = new int[9];
arr[0] = 7;
arr[1] = 2;
arr[2] = 4;
arr[3] = 8;
arr[4] = 3;
arr[5] = 5;
arr[6] = 1;
arr[7] = 0;
arr[8] = 10;
System.out.println((Arrays.toString(findKSamllest(arr,8))));
}
public static int partition(int[] input, int front, int end){
int pivot = input[front];
while(front < end){
while(input[front]<pivot)
front++;
while(input[end]>pivot)
end--;
swap(input,front,end);
}
return front;
}
public static void swap(int[] input, int s, int l){
int temp = input[s];
input[s] = input[l];
input[l] = temp;
}
public static int[] findK(int[] input, int front, int end, int k){
if(front>=end) return null;
int pivot = partition(input,front,end);
//System.out.println(pivot);
if(k==pivot){
return Arrays.copyOfRange(input,0,pivot);
}
else {
if(k<pivot)
return findK(input,front,pivot,k);
return findK(input,pivot+1,end,k);
}
}
public static int[] findKSamllest(int[] input, int k){
return findK(input, 0, input.length-1, k);
}
}
source to share
Rise on the shoulders of giants and use the libraries already available:
Arrays.sort(myArray);
int[] returnArray = new int(NUM_ITEMS_TO_RETURN);
for (int i=0; i < NUM_ITEMS_TO_RETURN; i++)
{
returnArray[i] = myArray[i];
}
return returnArray;
Obviously, you need to do some error checking, such as that the initial array is greater than or equal to the number of elements returned, but this is trivial.
source to share
You could save a little time and impress your teacher with the fantastic new Java 8 API.
It provides threads and useful functions to accomplish this task in one (long) line, or 5 if it should be read-)
final List<Integer> sortedKList = Arrays.asList(7, 2, 4, 8, 3, 5, 1, 0, 10)
.stream()
.sorted()
.limit(7)
.collect(Collectors.toList());
Then you can view your result:
sortedKList.forEach(System.out::println);
source to share