프로그래밍의 세계에서 배열을 조작하는 것은 기본적인 기술입니다. 하나의 공통 프로세스로서 요소를 무작위로 재배열하는 것을 포함하여 배열을 섞을 수 있습니다. 이 절차는 무작위 게임 데크 구축, 통계 시뮬레이션 실행 또는 데이터를 더 무작위로 표시하는 등의 작업에 필수적입니다. 처음에는 배열을 섞는 데 적용할 수 있는 논리가 많이 있습니다. ArrayList, 해시 세트, 연결 목록 등과 같은 다양한 유형의 컬렉션 프레임워크를 사용할 수 있습니다. 배열의 셔플링은 다르게 수행될 수 있으며
배열을 섞는 알고리즘:
다음은 배열 셔플 알고리즘입니다.
1 단계: 시작
2 단계: 배열의 마지막 요소부터 시작하여 첫 번째 요소로 뒤로 이동합니다.
3단계: 인덱스 i의 각 요소에 대해 j가 [0, i] 범위에 있도록 임의 인덱스 j를 생성합니다.
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)입니다. shuffleArray() 메서드에 사용된 Fisher-Yates 셔플 알고리즘의 시간 복잡도는 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() 메서드는 내장된 기능을 활용하여 객체 또는 기본이 아닌 배열의 순서 섞기 프로세스를 단순화합니다. 반면에 Fisher-Yates 알고리즘은 기본 배열을 섞는 효율적이고 편견 없는 방법을 제공하여 순열의 균일성을 보장합니다.