Random number generation with no duplicate values for insertion sort

Question

Hello i have been working on insertion sort on set of numbers. i am able to add them to the array for performing the sorting but i was not able to generate unique values with large set of numbers to performing sorting(i:e)for 1000 values .is there any possibility i can generate unique random numbers for performing the sorting without adding values to the array?

public class InsertionBinary
{

    public static void main(String Args [])
    {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 24};
        print(nums);
        insertionsort(nums);
        print(nums);
        int loc = binarySearch(nums, 3);
        System.out.println("2 is in position" + loc);
    }

    private static void swap(int[] list, int from, int to)
    {
        int temp = list[from];
        list[from] = list[to];
        list[to] = temp;
    }

    private static void print(int[] list)
    {
        for (int i = 0; i < list.length - 1; i++)
            System.out.
        print(list[i] + ", ");
        System.out.println(list[list.length - 1]);
    }


    private static void insertionsort(int[] list)
    {
        int key;
        int spot;
        for (int pass = 1; pass < list.length; pass++)
        {
            key = list[pass];
            for (spot = pass - 1; spot >= 0 && list[spot] > key; spot--)
                list[spot + 1] = list[spot];
            list[spot + 1] = key;

        }
    }
}

Refer to http://stackoverflow.com/questions/4040001/creating-random-numbers-with-no-duplicates — nayakam, Feb 02 '15 at 05:39

score 3 · Answer 1 · edited May 23 '17 at 11:50

3

If all you want is a set of unique numbers for sorting, I would say the easiest approach would be to generate an array of size N containing the numbers 0 though N-1 (or 1 through N if you prefer) using a loop:

int size = 1000;
int[] nums = new int[size];
for(int i = 0; i < size; i++) {
    nums[i] = i;
}

Then all you need to do is shuffle it, which you can do using your already-implemented swap() method and this helpful answer:

Random shuffling of an array

This has the advantage that it will run in O(n) time (instead of potentially infinite time if you're picking random numbers and then only inserting them if they're not already there).

Edit: You could also use Java's built-in shuffle method https://docs.oracle.com/javase/6/docs/api/java/util/Collections.html#shuffle(java.util.List)

edited May 23 '17 at 11:50

Community

1
1

answered Feb 02 '15 at 05:49

tytk

2,082
3
27
39

Although shuffling is a nice solution, but OP said he want 1000 random number not random numbers between 0 and 1000, so first of all you must change your size, also if maximum number is too big like 1billion or so shuffling is not a good answer, because it take time to fill the array and more important than that, it take huge amount of ram for no reason! Just do the math ;) – Lrrr Feb 02 '15 at 06:33
@AliAmiri ,@tytk Thanks for helping ..as i said thousand values it should be within 1000 with random shuffling not any thousand random values. and about the shuffle method ,is it like i have define a new method and perform the operation ? – Learningprog Feb 02 '15 at 06:58
@Learningprog where did you said not any thousand random number?! you just said you want 1000 unique random number : "generate unique values with large set of numbers to performing sorting(i:e)for 1000 values." also 1000 unique random number between 0 and 1000 is all the numbers between 0 and 1000! there is nothing random about it! – Lrrr Feb 02 '15 at 07:02
@AliAmiri i apologize for that ,i didn't mention clearly !! – Learningprog Feb 02 '15 at 07:05
@Learningprog yes you could define your own shuffle method (see the link I included) or with a little modification (use a list instead of an array) you can use the built in Java shuffle method (see other link) – tytk Feb 02 '15 at 07:10
@tytk I did perform the shuffle method and able to generate random numbers for the no of values i wanted .But when i run ,it generates 1000 values in a sequential order and then shows the shuffled values,for sorting it should be like the shuffled values to be to be shown first and then sorted in squantial order – Learningprog Feb 02 '15 at 07:30
Try this: generate array in sequential order (the code I gave you). Print. Shuffle the array (using links I provided). Print. Pass the array into your spring algorithm. Print. – tytk Feb 02 '15 at 15:03

score 1 · Answer 2 · answered Feb 02 '15 at 05:37

1

you can use Math.random() and also add one condition that will check, array contains that number or not, if not contains then add otherwise don't add.

answered Feb 02 '15 at 05:37

Prashant

2,556
2
20
26

score 1 · Answer 3 · answered Feb 02 '15 at 05:38

One simple solution is using Set generate your random numbers and insert them in a Set, set wont allow duplicate numbers, something like this :

Random rnd= new Random();
Set<Integer> randomSet = new LinkedHashSet<Integer>();
while (randomSet.size() < 1000)
{
    Integer randomNum = rnd.nextInt(max) + 1;
    randomSet.add(randomNum);
}

but it may take infinite time to generate a set like this in theory, but its probability is very low.

Random number generation with no duplicate values for insertion sort

3 Answers3