TechCodeview

בעולם התכנות, מניפולציה של מערכים היא מיומנות בסיסית. ניתן לערבב מערך, הכולל סידור מחדש אקראי של האלמנטים שלו, כתהליך נפוץ אחד. הליך זה חיוני לדברים כמו בניית חפיסות משחקים אקראיות, הפעלת סימולציות סטטיסטיות או סתם הצגת נתונים באופן אקראי יותר. בתחילה, יש הרבה היגיון שאנחנו יכולים ליישם כדי לערבב מערך; אנו יכולים להשתמש בסוגים שונים של מסגרות אוסף כגון ArrayList, ערכות hash, רשימות מקושרות וכו'. ערבוב של מערך יכול להיעשות בצורה שונה ו

אלגוריתם לערבב מערך:

להלן האלגוריתם לערבב של מערך,

שלב 1: הַתחָלָה

שלב 2: התחל מהאלמנט האחרון של המערך וחזור אחורה לאלמנט הראשון.

שלב 3: עבור כל אלמנט באינדקס i, צור אינדקס אקראי j כך ש-j נמצא בטווח [0, i].

שלב 4: החלף את האלמנטים במדדים i ו-j.

שלב 5: חזור על שלבים 2 ו-3 עבור כל האלמנטים במערך, זז אחורה מהאלמנט האחרון לראשון.

שלב 6: סוֹף

אנחנו יכולים לערבב מערך המכיל סוגים שונים של אלמנטים כמו מספרים שלמים, תווים וכו'.

אלגוריתם ערבוב של פישר-ייטס:

תוכנית Java הבאה משמשת לערבב מערך המורכב מספרים שלמים.

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; } } } 

תְפוּקָה:

 1 3 2 4 5 

הפלט עשוי להיות שונה אם תפעיל אותו במערכת שלך מכיוון שהוא מסדר באקראי את האלמנטים ומוציא את המערך המעורב.

מורכבויות:

מורכבות החלל של אלגוריתם הדשדוש היא O(1) מכיוון שהוא אינו משתמש במבני נתונים נוספים התלויים בגודל המערך. מורכבות הזמן של אלגוריתם הדשדוש של Fisher-Yates המשמש בשיטת shuffleArray() היא O(n), כאשר n הוא מספר האלמנטים במערך.

ערבוב מערך באמצעות רשימות ב-Java:

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)); } } 

תְפוּקָה:

 [4, 1, 7, 3, 6, 5, 2] 

הפלט עשוי להיות שונה אם תפעיל אותו במערכת שלך מכיוון שהוא מסדר באקראי את האלמנטים ומוציא את המערך המעורב.

מורכבויות:

מערכת הפעלה לינוקס

מורכבות החלל היא גם O(n). הסיבה לכך היא שהשיטה Collections.shuffle() משנה את הרשימה המקורית במקום ואינה משתמשת במבני נתונים נוספים. מורכבות הזמן של קוד זה היא O(n), כאשר n הוא מספר האלמנטים במערך.

ערבב מערך המכיל תווים:

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; } } } 

תְפוּקָה:

 Shuffled Characters: [e, f, g, d, a, c, b] 

הפלט עשוי להיות שונה אם תפעיל אותו במערכת שלך מכיוון שהוא מסדר באקראי את האלמנטים ומוציא את המערך המעורב.

מורכבויות:

מורכבות החלל של אלגוריתם הדשדוש היא O(1) מכיוון שהוא אינו משתמש במבני נתונים נוספים התלויים בגודל המערך. מורכבות הזמן של התוכנית המשמשת בשיטת shuffleArray() היא O(n), כאשר n הוא מספר התווים במערך.

סיכום:

ערבוב מערך ב-Java הוא מיומנות חיונית המאפשרת למפתחים ליצור סידורים אקראיים וחסרי פניות של נתונים. במהלך החקירה הזו, כיסינו שתי גישות יעילות: שימוש בשיטת Collections.shuffle() עבור מערכים לא פרימיטיביים והטמעת אלגוריתם הדשדוש של Fisher-Yates עבור מערכים פרימיטיביים. השיטה Collections.shuffle() מפשטת את תהליך הערבול עבור אובייקטים או מערכים לא פרימיטיביים על ידי מינוף פונקציות מובנות. מצד שני, האלגוריתם של פישר-ייטס מספק דרך יעילה וחסרת פניות לערבב מערכים פרימיטיביים, ומבטיח אחידות בתמורות.