-1

I watched a video disscussing a shuffling algorithm that runs at O(nlogn) The following python code is given:

def shuffle(arr):
      rand_values = [random.random() for i in range(len(arr))]
      rand_indexes = [i for i in range(len(arr))]
      rand_indexes.sort(key=lambda i: rand_values[i])
      arr = [arr[i] for i in rand_indexes]

In the method an array of random values is created eg [57,12,84,5,71] An array of index is created eg [0,1,2,3,4] Then the index array is sorted accroing to the rand values eg [3,1,0,4,2] Finally the array is shuffled using the random indexes array eg if arr = [H,o,w,d,y] it would be shuffled as [d,o,H,y,w]

I am trying to get the same algrothim working in Java so it still runs in O(nlogn) without using any packages besides Random

What I have at the moment:

public void shuffle(Object[] a) {
        if (a.length < 2) {
            return;
        }

        int size = a.length;
        Random rand = new Random();
        Comparable[] randValues = new Comparable[size];
        for (int i = 0; i < size; i++) {
            randValues[i] = rand.nextInt(Integer.MAX_VALUE);
        }
        
        Object randIndex[] = new Object[a.length];
        for (int i = 0; i < size; i++) {
            randIndex[i] = i;
        }
        
        Comparable[] sortedArr = mergesort(randValues);
        //mergesort is a seperate sorting method with param Comparable[] a
        for (int i = 0; i < size; i++) {
                randIndex[i] = sortedArr[i];
            }
        
        for (int i = 0; i < size; i++) {
            int index = (int) randIndex[i];
            a[i] =  a[index];
        }
        
    }

Currently, I am stuck trying to sort the randIndex array based of the random values.

starball
  • 20,030
  • 7
  • 43
  • 238
Jael
  • 1
  • 2

1 Answers1

0

You can achieve this using the built-in sorting capabilities and the Comparator interface.

import java.util.Random;
import static java.util.stream.Collectors.*;

String[] names = {"James", "Oliver", "Liam", "Noah", "Ethan", "Lucas", "Henry", "Owen", "Leo", "Mason"};
Random rand = new Random();

Arrays.sort(names, comparing(s -> rand.nextInt()));

The static Comparators.comparing function creates a Comparator from a given lambda function that, in this case, merely needs to return some random number.

David Jones
  • 2,879
  • 2
  • 18
  • 23