В настоящее время я пытаюсь разработать программу на Java, которая должна печатать шаги, которые алгоритм берет для упорядочивания элементов в массиве (все элементы в массиве при каждом изменении), где печать означает отображение его на консоли, сохранение его как файл или в SwingComponent.Как сохранить шаги, которые алгоритм берет для упорядочивания массива?
Прямо сейчас, используя Arraylist < int []>, чтобы сохранить шаги, но это позволяет мне сортировать менее 1k элементов, прежде чем выбрасывать исключение.
Есть ли способ сохранить элементы для большего количества элементов?
Код
package tests;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class BubbleSort{
public void sort(int[] array, List<int[]> process){
int len = array.length - 1;
int i, j, tmp;
process.add(array.clone()); //Save original array
for(i = 0; i < len; ++i){
for(j = 0; j < len - i; ++j){
if(array[ j ] > array[ j + 1 ]){
tmp = array[ j ];
array[ j ] = array[ j + 1 ];
array[ j + 1 ] = tmp;
process.add(array.clone()); //Array changed, save it
}
}
}
}
//creates a random array
public static int[] randomIntegerArray(int min, int max, int amount){
int[] array = new int[ amount ];
int total = max - min;
List<Integer> numbers = new ArrayList<>(total);
int i = 0;
for(i = min; i < max; ++i){
numbers.add(i);
}
Collections.shuffle(numbers);
for(i = 0; i < amount; ++i){
array[ i ] = numbers.remove(0);
}
return array;
}
public static void main(String[] args){
BubbleSort bubbleSort = new BubbleSort();
List<int[]> process = new ArrayList<>();
int[] noError = randomIntegerArray(0, 1000, 500); //Works up ~ 900
int[] error = randomIntegerArray(0, 1000, 1000);
bubbleSort.sort(noError, process);// Works
//bubbleSort.sort(error, process);// throws java.lang.OutOfMemoryError: Java heap space in line 22
//Print steps
//for(int[] a : process){ System.out.println(Arrays.toString(a)); }
}
}
Вы используете Bubble Sort, который является O (n^2). Вам повезло бы получить 1000 предметов. Кроме того, нет смысла хранить копию массива, просто распечатайте его на каждом шаге. – Sinkingpoint
На самом деле это всего лишь один из 3 алгоритмов, над которыми работает, то же самое происходит при tryng с Insertion и ShellSort. – Daxx2692