I'm finding it difficult to implement an in-place algorithm for bucket sort. The question and my attempt are below. Can anyone give me a hint or an explanation of how I can implement in-place bucket sort?
Q: Use the bucket sort idea to sort in-place an array of n records whose keys are a permutation of 1, 2, ..., n. Show that your algorithm takes time proportional to n.
public static void bucketSortInplace(int[] a)
{
System.out.println("size:" + a.length);
for (int i = 0; i <= a.length-1; i++)
{
int k = a[i];
System.out.println("key:" + k);
if (k == a.length)
{
int temp = a[a.length - 1];
//System.out.println("temp:" + temp);
a[a.length - 1] = a[i];
a[i] = temp;
} else if (k == a[k])
break;
else {
int temp = a[k-1];
// System.out.println("temp:" + temp);
a[k-1] = a[i];
a[i] = temp;
}
}
}
//tester
public static void main(String[] args)
{
int[] a = {6, 4, 2, 1, 3, 5};
bucketSortInplace(a);
for (int i = 0; i <= a.length-1; i++)
{
System.out.print(a[i]);
}
}