U svijetu programiranja, manipuliranje nizovima temeljna je vještina. Niz se može miješati, što uključuje nasumično preuređivanje njegovih elemenata, kao jedan uobičajeni proces. Ovaj je postupak neophodan za stvari kao što je izrada nasumičnih špilova za igranje, izvođenje statističkih simulacija ili samo nasumičniji prikaz podataka. U početku, postoji mnogo logike koju možemo primijeniti na miješanje niza; možemo koristiti različite vrste okvira skupljanja kao što su ArrayList, hash setovi, povezani popisi, itd. miješanje niza može se učiniti drugačije i
Algoritam za miješanje niza:
Slijedi algoritam za miješanje niza,
KORAK 1: POČETAK
KORAK 2: Počnite od posljednjeg elementa niza i idite unatrag do prvog elementa.
3. KORAK: Za svaki element s indeksom i, generirajte slučajni indeks j tako da je j u rasponu [0, i].
4. KORAK: Zamijenite elemente na indeksima i i j.
KORAK 5: Ponovite korake 2 i 3 za sve elemente u nizu, krećući se unatrag od zadnjeg elementa do prvog.
KORAK 6: KRAJ
Možemo miješati niz koji sadrži različite vrste elemenata poput cijelih brojeva, znakova itd.
Fisher-yatesov algoritam miješanja:
Sljedeći Java program koristi se za miješanje niza koji se sastoji od cijelih brojeva.
ArrayShuffle.java
import java.util.Random; public class ArrayShuffler { public static void main(String[] args) { // Sample array of integers int[] array = {1, 2, 3, 4, 5}; // Shuffle the array shuffleArray(array); // Print the shuffled array for (int num : array) { System.out.print(num + ' '); } } public static void shuffleArray(int[] array) { Random rand = new Random(); for (int i = array.length - 1; i > 0; i--) { // Generate a random index between 0 and i (inclusive) int j = rand.nextInt(i + 1); // Swap the elements at indices i and j int temp = array[i]; array[i] = array[j]; array[j] = temp; } } } Izlaz:
1 3 2 4 5
Izlaz se može razlikovati ako ga izvršite u svom sustavu jer nasumično raspoređuje elemente i ispisuje izmiješani niz.
Složenosti:
Prostorna složenost algoritma shuffle je O(1) jer ne koristi nikakve dodatne strukture podataka koje ovise o veličini niza. Vremenska složenost Fisher-Yatesovog algoritma miješanja koji se koristi u metodi shuffleArray() je O(n), gdje je n broj elemenata u nizu.
Miješanje niza pomoću popisa u Javi:
ShuffleArray.java
import java.util.Arrays; import java.util.Collections; import java.util.List; public class ShuffleArray { public static void main(String[] args) { Integer[] intArray = {1, 2, 3, 4, 5, 6, 7}; List intList = Arrays.asList(intArray); Collections.shuffle(intList); intList.toArray(intArray); // This line will not resize the array System.out.println(Arrays.toString(intArray)); } } Izlaz:
[4, 1, 7, 3, 6, 5, 2]
Izlaz se može razlikovati ako ga izvršite u svom sustavu jer nasumično raspoređuje elemente i ispisuje izmiješani niz.
Složenosti:
python rstrip
Složenost prostora je također O(n). To je zato što metoda Collections.shuffle() mijenja izvorni popis na mjestu i ne koristi nikakve dodatne strukture podataka. Vremenska složenost ovog koda je O(n), gdje je n broj elemenata u nizu.
Nasumični niz koji sadrži znakove:
ShuffleCharacters.java
import java.util.Arrays; import java.util.Random; public class ShuffleCharacters { public static void main(String[] args) { char[] charArray = {'a', 'b', 'c', 'd', 'e', 'f', 'g'}; shuffleArray(charArray); System.out.println('Shuffled Characters: ' + Arrays.toString(charArray)); } public static void shuffleArray(char[] array) { Random rand = new Random(); for (int i = array.length - 1; i > 0; i--) { int j = rand.nextInt(i + 1); // Swap characters at indices i and j char temp = array[i]; array[i] = array[j]; array[j] = temp; } } } Izlaz:
Shuffled Characters: [e, f, g, d, a, c, b]
Izlaz se može razlikovati ako ga izvršite u svom sustavu jer nasumično raspoređuje elemente i ispisuje izmiješani niz.
Složenosti:
Prostorna složenost algoritma shuffle je O(1) jer ne koristi nikakve dodatne strukture podataka koje ovise o veličini niza. Vremenska složenost programa koji se koristi u metodi shuffleArray() je O(n), gdje je n broj znakova u nizu.
Zaključak:
Miješanje niza u Javi ključna je vještina koja razvojnim programerima omogućuje stvaranje nasumičnog i nepristranog rasporeda podataka. Kroz ovo istraživanje pokrili smo dva učinkovita pristupa: korištenje metode Collections.shuffle() za neprimitivne nizove i implementaciju Fisher-Yatesovog algoritma za miješanje za primitivne nizove. Metoda Collections.shuffle() pojednostavljuje postupak miješanja za objekte ili neprimitivne nizove iskorištavanjem ugrađenih funkcija. S druge strane, Fisher-Yatesov algoritam pruža učinkovit i nepristran način miješanja primitivnih nizova, osiguravajući uniformnost u permutacijama.