How to save the steps the algorithm takes to order an array?

Question

Im currently trying to develop a program in Java that has to print the steps an algorithm takes to order the elements in an array (all the elements in the array each time it changes), where print means displaying it in console, saving it as a file or in a SwingComponent.

Right now im using an Arraylist< int[] > to save the steps, but it only allows me to sort less than 1k elements before throwing an exception.

Is there anyway I can save the steps for more elements?

Code

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

    }

}

You are using Bubble Sort which is O(n^2). You would be lucky to get to 1000 items. Additionally, there is no point actually storing a copy of the array, just print it out at each step. — Sinkingpoint
– Sinkingpoint, Commented Feb 9, 2014 at 1:33
Actually this is just one of 3 algorithms im working on, the same happens when tryng with Insertion and ShellSort. — Daxx2692
– Daxx2692, Commented Feb 9, 2014 at 1:36

Stephen C · Accepted Answer · 2014-02-09 15:06:07Z

Is there anyway I can save the steps for more elements?

Approach #1 - increase the heap size. Unfortunately, this doesn't scale.

Approach #2 - instead of saving the entire array after each swap, just save the details of the pair of elements that you swapped. If necessary, you can reconstruct the arrays by replaying the swap operations ... either forward from the initial array state or backwards from the final state.

Approach #3 - don't save the steps at all. Just output them to the console / file / Swing component as you sort.

On scalability.

You are using bubblesort which means that a sort of an N element array involves O(N^2) steps.
If you snapshot the entire array on each step, you need O(N^3) memory to hold them. For large N, that is a lot of memory!!
If you just store the details of the pair of array elements swapped, the memory requirement reduces to O(N^2). That is still a lot of memory.
If you don't store the details at all (because you are outputting them directly!) the memory requirement drops to O(N) for a simple implementation. (That's the amount memory needed to format the state of the array as a string. You could implement it as O(1), if necessary.)

The O(...) stuff I'm using is called "Big O" notation. Roughly speaking, O(N) means proportional to N ... as N tends towards infinity. The mathematics of this is based on Limits.

Collectives™ on Stack Overflow

How to save the steps the algorithm takes to order an array?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related