Every work day when quitting time approaches (around 05:00 PM) I check my to-do list. One thing I had for the day was to check is there is a method in a Java class to shuffle the contents of an array. This is a nice mechanism to have in your toolbox. For example, if you want to load a binary tree search (BST) and the data is sorted, the tree will basically load like a linked list. In a BST you can typically find an element in O(log(n)). But if the elements were inserted sorted, the search is performed in O(n) which is slower than O(log(n)). In such cases you can just shuffle the array and then load the BST.
I am not going to load a BST in this port. If interested in such code, you can take a look at “Binary Tree Sum” post in this blog.
(base) C:\Users\John>python Python 3.7.3 (default, Mar 27 2019, 17:13:21) [MSC v.1915 64 bit (AMD64)] :: Anaconda, Inc. on win32 Type "help", "copyright", "credits" or "license" for more information. >>> import random >>> array = [1, 2, 3, 4, 5] >>> print(array) [1, 2, 3, 4, 5] >>> random.shuffle(array) >>> print(array) [4, 3, 1, 2, 5] >>>
In Python you can simply shuffle the contents of an array. In this example we define an array of five integers. To make sure all is well we display the array. We then shuffle the array and display the results. It is that simple.
>>> from sklearn.utils import shuffle >>> array = [1, 2, 3, 4, 5] >>> print(array) [1, 2, 3, 4, 5] >>> array = shuffle(array) >>> print(array) [4, 1, 5, 2, 3] >>>
This is a different way to shuffle the same array. In the previous example we used the random library. In this example we will use the sklearn.utils library. As you can see the steps are very similar to the previous example.
With that in mind let’s write some code to shuffle an array of integers in Java 8. We will develop the code using the Visual Studio Code IDE.
main <<< initial arr: [-7, 8, 2, -4, 0, 3, 5] main <<< sorted arr: [-7, -4, 0, 2, 3, 5, 8] main <<< shuffled arr: [8, 0, 3, -4, -7, 2, 5]
Apparently we display an array of integers in the order it was given to us. We seem to sort the array and display it. On the third line it seems that we have shuffled the contents of the array and are displaying it.
/**
* Test scaffolding.
*/
public static void main(String[] args) {
// **** declare array of int ****
int[] arr = { -7, 8, 2, -4, 0, 3, 5 };
// **** display array ****
System.out.println("main <<< initial arr: " + Arrays.toString(arr));
// **** sort the array ****
Arrays.sort(arr);
// **** display sorted array ****
System.out.println("main <<< sorted arr: " + Arrays.toString(arr));
// **** shuffle the array ****
arr = shuffle(arr);
// **** display shuffled array ****
System.out.println("main <<< shuffled arr: " + Arrays.toString(arr));
}
As expected we declared an array of integers in no specific order. The contents of the array are displayed.
We then sort the array and display the values of the sorted array. As we mentioned if we would not load a BST, the values will be added in a linear fashion resulting in searches executing in O(n). If we need to load the BST we should first shuffle the array.
In the next step we shuffle the array and then display it..
/**
* Shuffle an array of integers.
* Runs in O(n) time.
*/
static int[] shuffle(int[] arr) {
// **** used to shuffle the array ****
List<Integer> al = new ArrayList<Integer>();
// **** populate the array list: O(n) ****
for (int i = 0; i < arr.length; i++) {
al.add(arr[i]);
}
// **** shuffle the array list: O(log(n)) ****
Collections.shuffle(al);
// **** copy the array list elements to the array: O(n) ****
for (int i = 0; i < al.size(); i++) {
arr[i] = al.get(i);
}
// **** returned shuffled array ****
return arr;
}
This method takes in an array of integers. We define an array list because we need a collection. Note that if we would be loading the values we should have loaded them into a list. That would eliminate the need to go to a collection and get back from it.
We load the list with the values of the array. We then shuffle the list.
We now need to go back from the list into the array. After we populate the array we return it to the caller.
I forgot to start a repo in GitHub before writing the code. I could copy the Solution.java to a temp folder, create a repo in GitHub, clone the repo and then copy the Solutions.java folder. Finally we could commit and push the single file. As I am typing this sentence I decided to do what I described instead of just creating the repo and copying it the final code.
# **** **** C:\Users\John\workspace7>git clone https://github.com/JohnCanessa/ShuffleArray.git Cloning into 'ShuffleArray'... remote: Enumerating objects: 3, done. remote: Counting objects: 100% (3/3), done. remote: Compressing objects: 100% (2/2), done. remote: Total 3 (delta 0), reused 0 (delta 0), pack-reused 0 Unpacking objects: 100% (3/3), done. # **** **** C:\Users\John\workspace7>cd ShuffleArray # **** **** C:\Users\John\workspace7\ShuffleArray>dir /A 03/02/2020 06:15 PM <DIR> . 03/02/2020 06:15 PM <DIR> .. 03/02/2020 06:15 PM <DIR> .git 03/02/2020 06:15 PM 134 README.md # **** **** C:\Users\John\workspace7\ShuffleArray>git status On branch master Your branch is up to date with 'origin/master'. nothing to commit, working tree clean
After copying the Solutions.java file to my c:\temp folder I deleted the ShuffleArray folder from my workspace. I then went to GitHub and created the ShuffleArray repository. Edited a README.md file and saved it.
Back in my Windows machine I cloned the repo. The folder ShuffleArray was created and populated by cloning the contents of GitHub. I the copied the Solutions.java file from my temporary folder.
# **** ****
C:\Users\John\workspace7\ShuffleArray>git status
On branch master
Your branch is up to date with 'origin/master'.
Untracked files:
(use "git add <file>..." to include in what will be committed)
Solution.java
nothing added to commit but untracked files present (use "git add" to track)
# **** ****
C:\Users\John\workspace7\ShuffleArray>git add Solution.java
# **** ****
C:\Users\John\workspace7\ShuffleArray>git status
On branch master
Your branch is up to date with 'origin/master'.
Changes to be committed:
(use "git reset HEAD <file>..." to unstage)
new file: Solution.java
# **** ****
C:\Users\John\workspace7\ShuffleArray>git commit -m "first version"
[master 1e2485e] first version
1 file changed, 61 insertions(+)
create mode 100644 Solution.java
# **** ****
C:\Users\John\workspace7\ShuffleArray>git status
On branch master
Your branch is ahead of 'origin/master' by 1 commit.
(use "git push" to publish your local commits)
nothing to commit, working tree clean
# **** ****
C:\Users\John\workspace7\ShuffleArray>git push origin master
Enumerating objects: 4, done.
Counting objects: 100% (4/4), done.
Delta compression using up to 8 threads
Compressing objects: 100% (3/3), done.
Writing objects: 100% (3/3), 800 bytes | 66.00 KiB/s, done.
Total 3 (delta 0), reused 0 (delta 0)
To https://github.com/JohnCanessa/ShuffleArray.git
1707f44..1e2485e master -> master
# **** ****
C:\Users\John\workspace7\ShuffleArray>git log
commit 1e2485e23ad1725ad603607397257184526de353 (HEAD -> master, origin/master, origin/HEAD)
Author: JohnCanessa <john.canessa@gmail.com>
Date: Mon Mar 2 18:17:43 2020 -0600
first version
commit 1707f44209e32b30fbfb02bfba5c78a4b854862e
Author: John Canessa <8019504+JohnCanessa@users.noreply.github.com>
Date: Mon Mar 2 18:14:57 2020 -0600
Create README.md
Since all was previously done in the software, we just needed to commit the changes. After that was done we synchronized the repositories. I checked on GitHub and all was fine. I will update the README.md file with the link to this post after I post it using WordPress.
he entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to serve of assistance with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private message using the following address: john.canessa@gmail.com. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, refresh your knowledge and enhance your developer toolset!
One last thing, thanks to all 366 subscribers to my blog!!!
John
Twitter: @john_canessa