Randomized Selection Algorithm

Question

I am trying to implement a randomized selection algorithm where an array is filled with random numbers and the user selects a location and the program returns the value coinciding with the location in the sorted version of the array without actually sorting the array.

The problem is that the program is giving the value of the element at the given location but in the unsorted array.

import java.util.*;

public class RandomizedSelection {

    public static void main(String[] args) {
        int maxSize = 10; // max size of the array
        int[] arr = new int[maxSize];

        // fill array with random numbers between the range of 0-200
        for (int i = 0; i < maxSize; i++) {
            int n = (int)(java.lang.Math.random()*199); 
            arr[i] = n;
        }

        System.out.println("There is an array of 100 elements in the range" +
                            " of 0 - 200. Select a location to view" +
                            " the value.");

        Scanner in = new Scanner(System.in);
        int userChoice = in.nextInt(); // get user's choice of i

        int loc = randomizedSelect(arr, 0, arr.length-1, userChoice);

        System.out.println(loc);

        System.out.println("The array was:\n" + Arrays.toString(arr));
    }

    public static int randomizedSelect(int[] array, int p, int r, int i) {
        if (p == r)
            return array[p];

        if (i == 0)
            return -1;

            int mid = randomizedPartition(array, p, r);
            int k = mid - p + 1;

            if (k == i) 
                return array[mid];
            else if (i < k)
                return randomizedSelect(array, p, mid-1, i);
            else
                return randomizedSelect(array, mid+1, r, i-k);

    }

    public static int randomizedPartition(int[] array, int start, int end) {
        Random rand = new Random();
        int pivotIdx = rand.nextInt((end - start) + 1) + start;
        int pivot = array[pivotIdx];

        swap(array[pivotIdx], array[end]);
        pivotIdx = end;

        int i = start - 1;

        for (int j = start; j <= end-1; j++) {
            if (array[j] <= pivot) {
                i++;
                swap(array[i], array[j]);
            }
        }
        swap(array[i+1], array[pivotIdx]);
        return i+1;
    }

    public static void swap(int i, int j) {
        int temp = i;
        i = j;
        j = temp;
    }       
}

The output of this program if the user selects a location choice 4 is: 50 The array was: [195, 24, 111, 50, 37, 128, 196, 117, 167, 195]

The sorted array should be: [24, 37, 50, 111, 117, 128, 167, 195, 195, 196]
which should make location choice 4 equal to 111, not 50.

David Waters · Accepted Answer · 2014-10-15 01:38:36Z

2

Try out putting your sorted array, or a least how the array looks at the end of each call to randomizedPartition. You will find that the array has not changed from when the it was created.

Now try looking at your array after each call to swap, again you will notice that the array is unchanged by the swap method. So now we know the swap method is not working like you would want.

Why could that be?

Have you read about pass-by-reference vs pass-by-value?

For primitives java uses passe-by-value not reference so the i & j parameters of the swap method are copies of the values stored in the array, changing the value of i or j will not effect the array at all.

Try changing the signature of swap to

private static void swap(int[] array, int indexI, int indexJ) {...}

Change the body of the swap method to move elements in the array, and see how that goes.

By the way your code will be much better with better variable names. Also the range on your random number generator for initialising the array is incorrect.

edited Oct 15, 2014 at 1:38

answered Oct 15, 2014 at 0:25

David Waters

12k7 gold badges44 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Giovanni Over a year ago

Thank you so much for clearing that up. I've adjusted the swap method to move elements in the array, and now I am getting an array index out of bounds error. Would that have to do with the above mentioned incorrect range on my random number generator for initializing the array?

David Waters Over a year ago

No the random number generator will not be causing your index out of bounds error. Find the line in error from the stack trace. then just before that line output the values that your using to index into the array. If any of them are greater then or equal to maxSize you will get an error. Try attaching a debugger and see where these values come from. For debugging it may be easier to work with a fixed seed for your random number generator rand = new Random(1); // Remove the 1 before release this will make the random numbers the same each time.

Collectives™ on Stack Overflow

Randomized Selection Algorithm

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related