0

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]);
        }
    }

Edited by cgen: n/a

1
Contributor
1
Reply
2
Views
6 Years
Discussion Span
Last Post by cgen
This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.