Programlama dünyasında dizileri değiştirmek temel bir beceridir. Bir dizi, ortak bir işlem olarak öğelerinin rastgele yeniden düzenlenmesini içeren şekilde karıştırılabilir. Bu prosedür, rastgele oyun desteleri oluşturmak, istatistiksel simülasyonlar yürütmek veya verileri yalnızca daha rastgele görüntülemek gibi şeyler için gereklidir. Başlangıçta bir diziyi karıştırmak için uygulayabileceğimiz pek çok mantık vardır; ArrayList, karma kümeleri, bağlantılı listeler vb. gibi farklı türde toplama çerçeveleri kullanabiliriz. Bir dizinin karıştırılması farklı şekilde yapılabilir ve
Bir Diziyi Karıştırmak için Algoritma:
Bir dizinin karıştırılması için algoritma aşağıdadır,
AŞAMA 1: BAŞLANGIÇ
ADIM 2: Dizinin son elemanından başlayıp ilk elemanına doğru ilerleyin.
AŞAMA 3: i indeksindeki her öğe için, j'nin [0, i] aralığında olmasını sağlayacak şekilde rastgele bir j indeksi oluşturun.
ADIM 4: i ve j endekslerindeki elemanların yerlerini değiştirin.
ADIM 5: Son öğeden ilk öğeye doğru ilerleyerek dizideki tüm öğeler için 2. ve 3. adımları tekrarlayın.
ADIM 6: SON
Tamsayılar, karakterler vb. gibi farklı türdeki öğeleri içeren bir diziyi karıştırabiliriz.
Fisher-yates Karıştırma Algoritması:
Tam sayılardan oluşan bir diziyi karıştırmak için aşağıdaki Java programı kullanılır.
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; } } } Çıktı:
1 3 2 4 5
Öğeleri rastgele düzenlediği ve karıştırılmış diziyi çıkardığı için sisteminizde çalıştırırsanız çıktı farklı olabilir.
Karmaşıklıklar:
Karıştırma algoritmasının uzay karmaşıklığı O(1)'dir çünkü dizinin boyutuna bağlı herhangi bir ekstra veri yapısı kullanmaz. shuffleArray() yönteminde kullanılan Fisher-Yates shuffle algoritmasının zaman karmaşıklığı O(n)'dir; burada n, dizideki öğelerin sayısıdır.
Java'da Listeleri Kullanarak Diziyi Karıştırmak:
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)); } } Çıktı:
[4, 1, 7, 3, 6, 5, 2]
Öğeleri rastgele düzenlediği ve karıştırılmış diziyi çıkardığı için sisteminizde çalıştırırsanız çıktı farklı olabilir.
Karmaşıklıklar:
Java numaralandırmaları
Uzay karmaşıklığı da O(n)'dir. Bunun nedeni Collections.shuffle() yönteminin orijinal listeyi yerinde değiştirmesi ve herhangi bir ek veri yapısı kullanmamasıdır. Bu kodun zaman karmaşıklığı O(n)'dir; burada n, dizideki öğelerin sayısıdır.
Karakterleri İçeren Karışık Dizi:
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; } } } Çıktı:
Shuffled Characters: [e, f, g, d, a, c, b]
Öğeleri rastgele düzenlediği ve karıştırılmış diziyi çıkardığı için sisteminizde çalıştırırsanız çıktı farklı olabilir.
Karmaşıklıklar:
Karıştırma algoritmasının uzay karmaşıklığı O(1)'dir çünkü dizinin boyutuna bağlı herhangi bir ekstra veri yapısı kullanmaz. shuffleArray() yönteminde kullanılan programın zaman karmaşıklığı O(n)'dir; burada n, dizideki karakter sayısıdır.
Çözüm:
Java'da bir diziyi karıştırmak, geliştiricilere rastgele ve tarafsız veri düzenlemeleri oluşturma gücü veren çok önemli bir beceridir. Bu araştırma boyunca iki etkili yaklaşımı ele aldık: ilkel olmayan diziler için Collections.shuffle() yöntemini kullanmak ve ilkel diziler için Fisher-Yates shuffle algoritmasını uygulamak. Collections.shuffle() yöntemi, yerleşik işlevlerden yararlanarak nesneler veya ilkel olmayan diziler için karıştırma işlemini basitleştirir. Öte yandan, Fisher-Yates algoritması, ilkel dizileri karıştırmak için etkili ve tarafsız bir yol sağlayarak permütasyonlarda tekdüzelik sağlar.