Sort animation
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 10 of 10

Thread: Sort animation

  1. #1
    Join Date
    Nov 2001
    Posts
    29

    Sort animation

    I have been working on a simple sorting application that allows the user to select from four types of sorts, vary speed and display style. I've gotten the application to do every thing but repaint during the sort, other than that the application works fine. Could someone take a look at this and tell me how I might be able to get this to update the graphics as it is sorting?

    Thanks in advance.

    //Java core packages
    import java.awt.*;
    import java.awt.event.*;

    //Java extension packages
    import javax.swing.*;

    public class SortItem extends JFrame {
    private JPanel buttonPanel, inputPanel;
    private CustomPanel sortPanel;
    private JLabel sortMethodLabel, speedLabel, formatLabel;
    private JTextField sortMethodField, speedField, formatField, displayField,
    choiceField;
    private JButton exitButton, sortButton, resetButton;

    int sortMethod, speed, format;

    /**
    * The array that is being sorted.
    */
    int arr[];

    /**
    * The name of the algorithm with default setting.
    */
    String algName = "BubbleSortAlgorithm";

    /**
    * The sorting algorithm.
    */
    //SortAlgorithm algorithm;

    /**
    * The high water mark.
    */
    int h1 = -1;

    /**
    * The low water mark.
    */
    int h2 = -1;

    /**
    * Fill the array with random numbers from 0..n-1.
    */
    void scramble() {
    int a[] = new int[getSize().height / 2];
    double f = getSize().width / (double) a.length;
    for (int i = a.length; --i >= 0 {
    a[ i ] = (int)(i * f);
    }
    for (int i = a.length; --i >= 0 {
    int j = (int)(i * Math.random());
    int t = a[ i ];
    a[ i ] = a[ j ];
    a[ j ] = t;
    }
    arr = a;
    }

    /**
    * Pause a while, and draw the low&high water marks.
    * @see SortAlgorithm
    */
    public void pause(int H1, int H2) {
    h1 = H1;
    h2 = H2;
    repaint();
    if ( speed == 3 )
    for (int j = 0; j <= 1000000; j++ );
    if ( speed == 2 )
    for (int k = 0; k <= 4000000; k++ );
    if ( speed == 1 )
    for (int l = 0; l <= 8000000; l++ );
    }

    /**
    * Set up GUI environment.
    */
    public SortItem()
    {
    super( "Sorting Algorithms" );

    // create an instance of inner class ActionEventHandler
    ActionEventHandler handler = new ActionEventHandler();

    // set up GUI
    Container container = getContentPane();
    sortPanel = new CustomPanel();
    sortPanel.setBackground( Color.white );
    container.add( sortPanel, BorderLayout.CENTER );

    inputPanel = new JPanel();
    inputPanel.setLayout( new GridLayout( 0, 1 ) );
    container.add( inputPanel, BorderLayout.NORTH );

    displayField = new JTextField( 35 );
    displayField.setEditable( false );
    inputPanel.add( displayField );
    displayField.setText( "\tEnter your selections then click 'Sort'");

    sortMethodLabel = new JLabel( "Sort Method: 1 = Bubble; 2 = Quick; 3 = Bidirectional; 4 = Selection" );
    sortMethodField = new JTextField( 5 );
    sortMethodField.addActionListener( handler );
    inputPanel.add( sortMethodLabel );
    inputPanel.add( sortMethodField );

    speedLabel = new JLabel( "Speed: 1 = slow; 2 = medium; 3 = fast Selection = NONE" );
    speedField = new JTextField( 5 );
    speedField.addActionListener( handler );
    inputPanel.add( speedLabel );
    inputPanel.add( speedField );

    formatLabel = new JLabel( "Format: 1 = Lines; 2 = Dots Selection = NONE" );
    formatField = new JTextField( 5 );
    formatField.addActionListener( handler );
    inputPanel.add( formatLabel );
    inputPanel.add( formatField );

    choiceField = new JTextField( 35 );
    choiceField.setEditable( false );
    inputPanel.add( choiceField );
    choiceField.setText( "\t****** Bubble Sort Algorithm ******");

    sortButton = new JButton( "Sort" );
    sortButton.addActionListener( handler );

    exitButton = new JButton( "Exit" );
    exitButton.addActionListener( handler );

    resetButton = new JButton( "Reset" );
    resetButton.addActionListener( handler );

    buttonPanel = new JPanel();
    buttonPanel.setLayout( new GridLayout(1, 3 ) );
    buttonPanel.add( sortButton );
    buttonPanel.add( exitButton );
    buttonPanel.add( resetButton );
    container.add( buttonPanel, BorderLayout.SOUTH );

    scramble();
    repaint();

    setSize( 400, 500);
    setVisible( true );

    } // end constructor

    /**
    * Inner class definition for handling JTextField and JButton events.
    */
    private class ActionEventHandler
    implements ActionListener {

    // method to handle action events
    public void actionPerformed( ActionEvent event )
    {
    // user pressed exitButton
    if ( event.getSource() == exitButton )
    System.exit( 0 ); // terminate the application

    // user pressed sortButton - start sort
    else if ( event.getSource() == sortButton ){
    // run sort
    sortMethodField.setText( "" );
    speedField.setText( "" );
    formatField.setText( "" );
    if ( sortMethod == 1 ) {
    BubbleSortAlgorithm algorithm = new BubbleSortAlgorithm();
    algorithm.sort( arr );
    }
    else if ( sortMethod == 2 ) {
    QSortAlgorithm algorithm = new QSortAlgorithm();
    algorithm.sort( arr );
    }
    else if ( sortMethod == 3 ) {
    BidirBubbleSortAlgorithm algorithm = new BidirBubbleSortAlgorithm();
    algorithm.sort( arr );
    }
    else if ( sortMethod == 4 ) {
    SelectionSortAlgorithm algorithm = new SelectionSortAlgorithm();
    algorithm.sort( arr );
    }
    else
    scramble();
    repaint();
    }
    else if ( event.getSource() == resetButton ) {
    scramble();
    repaint();
    }
    // user pressed Enter key in sortMethodField - set appropriate editable properties
    else if ( event.getSource() == sortMethodField ) {
    sortMethod = Integer.parseInt( event.getActionCommand() );
    if( sortMethod == 1 ) {
    algName = "BubbleSortAlgorithm";
    choiceField.setText( "\t****** Bubble Sort Algorithm ******" );
    }
    else if( sortMethod == 2 ) {
    algName = "QSortAlgorithm";
    choiceField.setText( "\t****** Quick Sort Algorithm ******" );
    }
    else if( sortMethod == 3 ) {
    algName = "BidirBubbleSortAlgorithm";
    choiceField.setText( "\t****** Bidirectional Sort Algorithm ******" );
    }
    else if( sortMethod == 4 ) {
    algName = "SelectionSortAlgorithm";
    choiceField.setText( "\t****** Selection Sort Algorithm ******" );
    }
    sortMethodField.setText( "" );
    }

    // user pressed Enter key in speedField
    else if ( event.getSource() == speedField ) {
    speed = Integer.parseInt(event.getActionCommand());
    if ( speed < 1 || speed > 3 )
    speed = 3;
    speedLabel.setText( "Speed: 1 = slow; 2 = medium; 3 = fast Selection = " + speed );
    speedField.setText( "" );
    }

    // user pressed Enter key in formatField
    else if ( event.getSource() == formatField ) {
    format = Integer.parseInt(event.getActionCommand());
    if ( format < 1 || format > 2 )
    format = 1;
    formatLabel.setText( "Format: 1 = Lines; 2 = Dots Selection = " + format );
    formatField.setText( "" );
    }

    } // end actionPerformed method

    } // end inner class ActionEventHandler

    public static void main( String args[] )
    {
    SortItem application = new SortItem();

    application.setDefaultCloseOperation(
    JFrame.EXIT_ON_CLOSE );
    }

    /**
    * Custom drawing panel
    */
    class CustomPanel extends JPanel {

    /**
    * Paint the array of numbers as a list
    * of horizontal lines of varying lengths.
    * @param g this graphics object
    */
    public void paintComponent( Graphics g ) {

    super.paintComponent( g );
    int a[] = arr;
    int y = getSize().height - 1;

    // Erase old lines
    g.setColor(getBackground());
    for (int i = a.length; --i >= 0; y -= 2)
    g.drawLine(arr[ i ], y, getSize().width, y);


    // Draw new lines
    g.setColor(Color.black);
    y = getSize().height - 1;
    for (int i = a.length; --i >= 0; y -= 2) {
    if ( format == 2 )
    g.drawLine(arr[ i ]-1, y, arr[ i ], y);
    else
    g.drawLine(0, y, arr[ i ], y);
    }

    if (h1 >= 0) {
    g.setColor(Color.red);
    y = h1 * 2 + 1;
    g.drawLine(0, y, getSize().width, y);
    }
    if (h2 >= 0) {
    g.setColor(Color.blue);
    y = h2 * 2 + 1;
    g.drawLine(0, y, getSize().width, y);
    }
    }

    } // end class CustomPanel

    /**
    * A bubble sort demonstration algorithm
    * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
    *
    * @author James Gosling
    * @version 1.6f, 31 Jan 1995
    */
    class BubbleSortAlgorithm {
    public void sort(int a[]) {
    for (int i = a.length; --i>=0; ) {
    boolean swapped = false;
    for (int j = 0; j<i; j++) {

    if (a[ j ] > a[ j+1 ]) {
    int T = a[ j ];
    a[ j ] = a[ j+1 ];
    a[ j+1 ] = T;
    swapped = true;
    }
    pause(i,j);
    }
    if (!swapped)
    return;
    }
    }
    }

    /**
    * A quick sort demonstration algorithm
    * SortAlgorithm.java
    *
    * @author James Gosling
    * @author Kevin A. Smith
    * @version @(#)QSortAlgorithm.java 1.3, 29 Feb 1996
    */
    class QSortAlgorithm {

    /**
    * A version of pause() that makes it easier to ensure that we pause
    * exactly the right number of times.
    */
    private boolean pauseTrue(int lo, int hi) {
    pause(lo, hi);
    return true;
    }

    /** This is a generic version of C.A.R Hoare's Quick Sort
    * algorithm. This will handle arrays that are already
    * sorted, and arrays with duplicate keys.<BR>
    *
    * If you think of a one dimensional array as going from
    * the lowest index on the left to the highest index on the right
    * then the parameters to this function are lowest index or
    * left and highest index or right. The first time you call
    * this function it will be with the parameters 0, a.length - 1.
    *
    * @param a an integer array
    * @param lo0 left boundary of array partition
    * @param hi0 right boundary of array partition
    */
    void QuickSort(int a[], int lo0, int hi0)
    {
    int lo = lo0;
    int hi = hi0;
    int mid;

    if ( hi0 > lo0)
    {

    /* Arbitrarily establishing partition element as the midpoint of
    * the array.
    */
    mid = a[ ( lo0 + hi0 ) / 2 ];

    // loop through the array until indices cross
    while( lo <= hi )
    {
    /* find the first element that is greater than or equal to
    * the partition element starting from the left Index.
    */
    while( ( lo < hi0 ) && pauseTrue(lo0, hi0) && ( a[lo] < mid ))
    ++lo;

    /* find an element that is smaller than or equal to
    * the partition element starting from the right Index.
    */
    while( ( hi > lo0 ) && pauseTrue(lo0, hi0) && ( a[hi] > mid ))
    --hi;

    // if the indexes have not crossed, swap
    if( lo <= hi )
    {
    swap(a, lo, hi);
    ++lo;
    --hi;
    }
    }

    /* If the right index has not reached the left side of array
    * must now sort the left partition.
    */
    if( lo0 < hi )
    QuickSort( a, lo0, hi );

    /* If the left index has not reached the right side of array
    * must now sort the right partition.
    */
    if( lo < hi0 )
    QuickSort( a, lo, hi0 );

    }
    }

    private void swap(int a[], int i, int j)
    {
    int T;
    T = a[ i ];
    a[ i ] = a[ j ];
    a[ j ] = T;

    }

    public void sort(int a[])
    {
    QuickSort(a, 0, a.length - 1);
    }
    }

    /**
    * A bi-directional bubble sort demonstration algorithm
    * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
    *
    * @author James Gosling
    * @version 1.6f, 31 Jan 1995
    */
    class BidirBubbleSortAlgorithm {
    public void sort(int a[]) {
    int j;
    int limit = a.length;
    int st = -1;
    while (st < limit) {
    st++;
    limit--;
    boolean swapped = false;
    for (j = st; j < limit; j++) {

    if (a[ j ] > a[ j + 1 ]) {
    int T = a[ j ];
    a[ j ] = a[ j + 1 ];
    a[ j + 1 ] = T;
    swapped = true;
    }
    pause(st, limit);
    }
    if (!swapped) {
    return;
    }
    else
    swapped = false;
    for (j = limit; --j >= st {

    if (a[ j ] > a[ j + 1 ]) {
    int T = a[ j ];
    a[ j ] = a[ j + 1 ];
    a[ j + 1 ] = T;
    swapped = true;
    }
    pause(st, limit);
    }
    if (!swapped) {
    return;
    }
    }
    }
    }


    /**
    * A selection sort demonstration algorithm
    * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
    *
    * @author Jason Harrison@cs.ubc.ca
    * @version 1.0, 23 Jun 1995
    *
    */
    class SelectionSortAlgorithm {
    public void sort(int a[]) {
    for (int i = 0; i < a.length; i++) {
    int min = i;
    int j;

    /*
    * Find the smallest element in the unsorted list
    */
    for (j = i + 1; j < a.length; j++) {


    if (a[ j ] < a[ min ]) {
    min = j;
    }
    pause(i,j);
    }

    /*
    * Swap the smallest unsorted element into the end of the
    * sorted list.
    */
    int T = a[ min ];
    a[ min ] = a[ i ];
    a[ i ] = T;
    pause(i,j);
    }
    }
    }

    } // end class SortItem




  2. #2
    Join Date
    Jun 1999
    Location
    SW Missouri
    Posts
    3,450

    Re: Sort animation

    What is meant by "repaint during the sort"? What is it that the program displays that is to be repainted. You have nice comments at the detail level for your program, but you also need a high level description of what the program does. I assume its some GUI thing because of the repaint() issue.
    To save time and make it easier for someone to help, could you point out where in your code that your are having problems?
    For example if you had comments in the code that said:
    // **** HERE IS where I don't know how to ...
    and then in the beginning of the post say to look for "*** HERE" for where I'm having problems.

    Norm
    Norm

  3. #3
    Join Date
    Nov 2001
    Posts
    29

    Re: Sort animation

    Thank you Norm,

    I have attempted to explain my difficulty a bit better this time.

    /**
    * This application updates the display to reflect each change
    * during the sorting of an array. The user can select from four
    * sort algorithms, select 3 different speeds, and select two
    * different display formats.
    *
    * At the moment I am having difficulty getting the display to refresh or
    * update after each change to the array during the sorting operation.
    * Once the sort button is pressed the proper sort algorithm instance is
    * created and the array arr is sent to be sorted. In each sort algorithm
    * the pause method is called after each change to the array being sorted.
    * The pause method should pause the sort operation and update the display
    * to reflect the change, however this is where I am having difficulty.
    *
    * Please look at the pause method calls in the sorting algorithms, then the
    * pause method itself. I have the pause method calling repaint but it is not
    * repainting and I cannot figure out why.
    *
    */

    //Java core packages
    import java.awt.*;
    import java.awt.event.*;

    //Java extension packages
    import javax.swing.*;

    public class Proj2 extends JFrame {
    private JPanel buttonPanel;
    private CustomPanel sortPanel;
    private JLabel sortMethodLabel, speedLabel, formatLabel, blankLabel1,
    blankLabel2, blankLabel3, blankLabel4, blankLabel5;
    private JButton exitButton, sortButton, resetButton;
    private JRadioButton slowButton, medButton, fastButton,
    linesButton, dotsButton, bubbleButton, quickButton, bidirButton,
    selectButton;
    private ButtonGroup speedGroup, formatGroup, sortMethodGroup;

    int sortMethod = 1, speed = 3, format = 1;

    /**
    * The array that is being sorted.
    */
    int arr[];

    /**
    * The name of the algorithm with default setting.
    */
    String algName = "BubbleSortAlgorithm";

    /**
    * The sorting algorithm.
    */
    //SortAlgorithm algorithm;

    /**
    * The high water mark.
    */
    int h1 = -1;

    /**
    * The low water mark.
    */
    int h2 = -1;

    /**
    * Fill the array with random numbers from 0..n-1.
    */
    void scramble() {
    int a[] = new int[getSize().height / 2];
    double f = getSize().width / (double) a.length;
    for (int i = a.length; --i >= 0 {
    a[ i ] = (int)(i * f);
    }
    for (int i = a.length; --i >= 0 {
    int j = (int)(i * Math.random());
    int t = a[ i ];
    a[ i ] = a[ j ];
    a[ j ] = t;
    }
    arr = a;
    }

    /**
    * Pause a while, and draw the low&high water marks.
    */
    public void pause(int H1, int H2) {
    h1 = H1;
    h2 = H2;
    draw();
    if ( speed == 3 )
    for (int j = 0; j <= 1000000; j++ );
    if ( speed == 2 )
    for (int k = 0; k <= 4000000; k++ );
    if ( speed == 1 )
    for (int l = 0; l <= 8000000; l++ );
    }

    void draw() {
    repaint();
    }

    /**
    * Set up GUI environment.
    */
    public Proj2()
    {
    super( "Sorting Algorithms" );

    // create an instance of inner class ActionEventHandler
    ActionEventHandler handler = new ActionEventHandler();

    // set up GUI
    Container container = getContentPane();
    sortPanel = new CustomPanel();
    sortPanel.setBackground( Color.white );
    container.add( sortPanel, BorderLayout.CENTER );

    speedLabel = new JLabel ( " Speed" );
    formatLabel = new JLabel ( " Format" );
    sortMethodLabel = new JLabel( " Sort Method" );

    // create radio buttons
    bubbleButton = new JRadioButton( "Bubble", true );
    quickButton = new JRadioButton( "Quick", false );
    bidirButton = new JRadioButton( "Bidirectional", false );
    selectButton = new JRadioButton( "Selection", false );

    // register events for JRadioButtons
    bubbleButton.addActionListener( handler );
    quickButton.addActionListener( handler );
    bidirButton.addActionListener( handler );
    selectButton.addActionListener( handler );

    // create logical relationship between JRadioButtons
    sortMethodGroup = new ButtonGroup();
    sortMethodGroup.add( bubbleButton );
    sortMethodGroup.add( quickButton );
    sortMethodGroup.add( bidirButton );
    sortMethodGroup.add( selectButton );

    // create radio buttons
    slowButton = new JRadioButton( "Slow", false );
    medButton = new JRadioButton( "Medium", false );
    fastButton = new JRadioButton( "Fast", true );

    // register events for JRadioButtons
    slowButton.addActionListener( handler );
    medButton.addActionListener( handler );
    fastButton.addActionListener( handler );

    // create logical relationship between JRadioButtons
    speedGroup = new ButtonGroup();
    speedGroup.add( slowButton );
    speedGroup.add( medButton );
    speedGroup.add( fastButton );

    // create radio buttons
    linesButton = new JRadioButton( "Lines", true );
    dotsButton = new JRadioButton( "Dots", false );

    // register events for JRadioButtons
    linesButton.addActionListener( handler );
    dotsButton.addActionListener( handler );

    // create logical relationship between JRadioButtons
    formatGroup = new ButtonGroup();
    formatGroup.add( linesButton );
    formatGroup.add( dotsButton );

    // create sort button and register events
    sortButton = new JButton( "Sort" );
    sortButton.addActionListener( handler );

    // create exit button and register events
    exitButton = new JButton( "Exit" );
    exitButton.addActionListener( handler );

    // create reset button and register events
    resetButton = new JButton( "Reset" );
    resetButton.addActionListener( handler );

    blankLabel1 = new JLabel( " " );
    blankLabel2 = new JLabel( " " );
    blankLabel3 = new JLabel( " " );
    blankLabel4 = new JLabel( " " );
    blankLabel5 = new JLabel( " " );

    buttonPanel = new JPanel();
    buttonPanel.setLayout( new GridLayout( 4, 5 ) );
    buttonPanel.add( sortMethodLabel );
    buttonPanel.add( bubbleButton );
    buttonPanel.add( quickButton );
    buttonPanel.add( bidirButton );
    buttonPanel.add( selectButton );
    buttonPanel.add( speedLabel );
    buttonPanel.add( slowButton );
    buttonPanel.add( medButton );
    buttonPanel.add( fastButton );
    buttonPanel.add( blankLabel1 );
    buttonPanel.add( formatLabel );
    buttonPanel.add( linesButton );
    buttonPanel.add( dotsButton );
    buttonPanel.add( blankLabel2 );
    buttonPanel.add( blankLabel3 );
    buttonPanel.add( blankLabel4 );
    buttonPanel.add( sortButton );
    buttonPanel.add( exitButton );
    buttonPanel.add( resetButton );
    buttonPanel.add( blankLabel5 );
    container.add( buttonPanel, BorderLayout.SOUTH );

    scramble();
    repaint();

    setSize( 600, 400);
    setVisible( true );

    } // end constructor

    /**
    * Inner class definition for handling JTextField and JButton events.
    */
    private class ActionEventHandler
    implements ActionListener {

    // method to handle action events
    public void actionPerformed( ActionEvent event )
    {
    // user pressed exitButton
    if ( event.getSource() == exitButton )
    System.exit( 0 ); // terminate the application

    // user pressed sortButton - start sort
    else if ( event.getSource() == sortButton ){
    // run sort
    if ( sortMethod == 1 ) {
    BubbleSortAlgorithm algorithm = new BubbleSortAlgorithm();
    algorithm.sort( arr );
    }
    else if ( sortMethod == 2 ) {
    QSortAlgorithm algorithm = new QSortAlgorithm();
    algorithm.sort( arr );
    }
    else if ( sortMethod == 3 ) {
    BidirBubbleSortAlgorithm algorithm = new BidirBubbleSortAlgorithm();
    algorithm.sort( arr );
    }
    else if ( sortMethod == 4 ) {
    SelectionSortAlgorithm algorithm = new SelectionSortAlgorithm();
    algorithm.sort( arr );
    }
    else
    scramble();
    repaint();
    }
    else if ( event.getSource() == resetButton ) {
    scramble();
    repaint();
    }
    // user pressed Enter key in sortMethodField - set appropriate editable properties
    else if ( event.getSource() == bubbleButton ) {
    sortMethod = 1;
    algName = "BubbleSortAlgorithm";
    }
    else if ( event.getSource() == quickButton ) {
    sortMethod = 2;
    algName = "QSortAlgorithm";
    }
    else if ( event.getSource() == bidirButton ) {
    sortMethod = 3;
    algName = "BidirBubbleSortAlgorithm";
    }
    else if ( event.getSource() == selectButton ) {
    sortMethod = 4;
    algName = "SelectionSortAlgorithm";
    }

    // user pressed Enter key in speedField
    else if ( event.getSource() == slowButton ) {
    speed = 1;
    }
    else if ( event.getSource() == medButton ) {
    speed = 2;
    }
    else if ( event.getSource() == fastButton ) {
    speed = 3;
    }
    // user pressed Enter key in formatField
    else if ( event.getSource() == linesButton ) {
    format = 1;
    }
    else if ( event.getSource() == dotsButton ) {
    format = 2;
    }

    } // end actionPerformed method

    } // end inner class ActionEventHandler

    public static void main( String args[] )
    {
    Proj2 application = new Proj2();

    application.setDefaultCloseOperation(
    JFrame.EXIT_ON_CLOSE );
    }

    /**
    * Custom drawing panel
    */
    class CustomPanel extends JPanel {

    /**
    * Paint the array of numbers as a list
    * of horizontal lines of varying lengths.
    * @param g this graphics object
    */
    public void paintComponent( Graphics g ) {

    super.paintComponent( g );
    int a[] = arr;
    int y = getSize().height - 1;

    // Erase old lines
    g.setColor(getBackground());
    for (int i = a.length; --i >= 0; y -= 2)
    g.drawLine(arr[ i ], y, getSize().width, y);

    // Draw new lines
    g.setColor(Color.black);
    y = getSize().height - 1;
    for (int i = a.length; --i >= 0; y -= 2) {
    if ( format == 2 )
    g.drawLine(arr[ i ]-1, y, arr[ i ], y);
    else
    g.drawLine(0, y, arr[ i ], y);
    }

    if (h1 >= 0) {
    g.setColor(Color.red);
    y = h1 * 2 + 1;
    g.drawLine(0, y, getSize().width, y);
    }
    if (h2 >= 0) {
    g.setColor(Color.blue);
    y = h2 * 2 + 1;
    g.drawLine(0, y, getSize().width, y);
    }
    }

    } // end class CustomPanel

    /**
    * A bubble sort demonstration algorithm
    * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
    *
    * @author James Gosling
    * @version 1.6f, 31 Jan 1995
    */
    class BubbleSortAlgorithm {
    public void sort(int a[]) {
    for (int i = a.length; --i>=0; ) {
    boolean swapped = false;
    for (int j = 0; j<i; j++) {

    if (a[ j ] > a[ j+1 ]) {
    int T = a[ j ];
    a[ j ] = a[ j+1 ];
    a[ j+1 ] = T;
    swapped = true;
    }
    pause(i,j);
    }
    if (!swapped)
    return;
    }
    }
    }

    /**
    * A quick sort demonstration algorithm
    * SortAlgorithm.java
    *
    * @author James Gosling
    * @author Kevin A. Smith
    * @version @(#)QSortAlgorithm.java 1.3, 29 Feb 1996
    */
    class QSortAlgorithm {

    /**
    * A version of pause() that makes it easier to ensure that we pause
    * exactly the right number of times.
    */
    private boolean pauseTrue(int lo, int hi) {
    pause(lo, hi);
    return true;
    }

    /** This is a generic version of C.A.R Hoare's Quick Sort
    * algorithm. This will handle arrays that are already
    * sorted, and arrays with duplicate keys.<BR>
    *
    * If you think of a one dimensional array as going from
    * the lowest index on the left to the highest index on the right
    * then the parameters to this function are lowest index or
    * left and highest index or right. The first time you call
    * this function it will be with the parameters 0, a.length - 1.
    *
    * @param a an integer array
    * @param lo0 left boundary of array partition
    * @param hi0 right boundary of array partition
    */
    void QuickSort(int a[], int lo0, int hi0)
    {
    int lo = lo0;
    int hi = hi0;
    int mid;

    if ( hi0 > lo0)
    {

    /* Arbitrarily establishing partition element as the midpoint of
    * the array.
    */
    mid = a[ ( lo0 + hi0 ) / 2 ];

    // loop through the array until indices cross
    while( lo <= hi )
    {
    /* find the first element that is greater than or equal to
    * the partition element starting from the left Index.
    */
    while( ( lo < hi0 ) && pauseTrue(lo0, hi0) && ( a[lo] < mid ))
    ++lo;

    /* find an element that is smaller than or equal to
    * the partition element starting from the right Index.
    */
    while( ( hi > lo0 ) && pauseTrue(lo0, hi0) && ( a[hi] > mid ))
    --hi;

    // if the indexes have not crossed, swap
    if( lo <= hi )
    {
    swap(a, lo, hi);
    ++lo;
    --hi;
    }
    }

    /* If the right index has not reached the left side of array
    * must now sort the left partition.
    */
    if( lo0 < hi )
    QuickSort( a, lo0, hi );

    /* If the left index has not reached the right side of array
    * must now sort the right partition.
    */
    if( lo < hi0 )
    QuickSort( a, lo, hi0 );

    }
    }

    private void swap(int a[], int i, int j)
    {
    int T;
    T = a[ i ];
    a[ i ] = a[ j ];
    a[ j ] = T;

    }

    public void sort(int a[])
    {
    QuickSort(a, 0, a.length - 1);
    }
    }

    /**
    * A bi-directional bubble sort demonstration algorithm
    * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
    *
    * @author James Gosling
    * @version 1.6f, 31 Jan 1995
    */
    class BidirBubbleSortAlgorithm {
    public void sort(int a[]) {
    int j;
    int limit = a.length;
    int st = -1;
    while (st < limit) {
    st++;
    limit--;
    boolean swapped = false;
    for (j = st; j < limit; j++) {

    if (a[ j ] > a[ j + 1 ]) {
    int T = a[ j ];
    a[ j ] = a[ j + 1 ];
    a[ j + 1 ] = T;
    swapped = true;
    }
    pause(st, limit);
    }
    if (!swapped) {
    return;
    }
    else
    swapped = false;
    for (j = limit; --j >= st {

    if (a[ j ] > a[ j + 1 ]) {
    int T = a[ j ];
    a[ j ] = a[ j + 1 ];
    a[ j + 1 ] = T;
    swapped = true;
    }
    pause(st, limit);
    }
    if (!swapped) {
    return;
    }
    }
    }
    }


    /**
    * A selection sort demonstration algorithm
    * SortAlgorithm.java, Thu Oct 27 10:32:35 1994
    *
    * @author Jason Harrison@cs.ubc.ca
    * @version 1.0, 23 Jun 1995
    *
    */
    class SelectionSortAlgorithm {
    public void sort(int a[]) {
    for (int i = 0; i < a.length; i++) {
    int min = i;
    int j;

    /*
    * Find the smallest element in the unsorted list
    */
    for (j = i + 1; j < a.length; j++) {


    if (a[ j ] < a[ min ]) {
    min = j;
    }
    pause(i,j);
    }

    /*
    * Swap the smallest unsorted element into the end of the
    * sorted list.
    */
    int T = a[ min ];
    a[ min ] = a[ i ];
    a[ i ] = T;
    pause(i,j);
    }
    }
    }

    } // end class Proj2




  4. #4
    Join Date
    Sep 1999
    Location
    Madurai , TamilNadu , INDIA
    Posts
    1,024

    Re: Sort animation


    You might find the following link very useful. Check it out..

    http://java.sun.com/applets/jdk/1.1/...emo/index.html

    It is updating the UI in the middle of sorting.. Look at the sourcecode.


  5. #5
    Join Date
    Nov 2001
    Posts
    29

    Re: Sort animation

    Yes, I'm trying to do the same thing as the examples you pointed out but after having studied the very same ones for quite some time I am unable to duplicate them on this basic level hence my dilema.


  6. #6
    Join Date
    Jun 1999
    Location
    SW Missouri
    Posts
    3,450

    Re: Sort animation

    Much better, thank you, epecially the comments on the pause method. You want to do the repaint faster than is normally done by using the repaint() method. Try using the JComponent paintImmediately method.
    Some other comments.
    In the constructor move the scramble and repaint calls after the setVisible call.
    You should move the sorting to its own thread off of the AWT engine's thread to allow the user access to the GUI in case he wants to exit the program before it ends for example.

    Norm
    Norm

  7. #7
    Join Date
    Nov 2001
    Posts
    29

    Re: Sort animation

    Thanks very much Norm; I'll try your suggestions in the next couple of hours and let you know how it went.




  8. #8
    Join Date
    Nov 2001
    Posts
    29

    Re: Sort animation

    OK, I've added a call to paintImmediately in the draw() method which is called from the pause() method; see below.
    void draw() {
    int w = getSize().width;
    int h = getSize().height;
    paintImmediately(0, 0, w, h);
    }


    I get this error:
    Proj2.java:95: cannot resolve symbol
    symbol : method paintImmediately (int,int,int,int)
    location: class Proj2
    paintImmediately(0, 0, w, h);
    ^
    1 error

    I know that the method exists in JComponent and that it takes four parameters; is there another package that I need to import for this to work?




  9. #9
    Join Date
    Jun 1999
    Location
    SW Missouri
    Posts
    3,450

    Re: Sort animation

    What class is the code you've shown in? Does it extend JComponent?
    What object do you want to paintImmediately? Isn't it sortPanel?

    Norm
    Norm

  10. #10
    Join Date
    Sep 1999
    Location
    Madurai , TamilNadu , INDIA
    Posts
    1,024

    Re: Sort animation


    pause() method does not give a chance to the JFrame ( & JPanel ) to paint itself. You have a for loop in the pause() method. That will not yield control to your UI thread to paint itself. You are running everything in a single thread. When you call repaint(), it will not call the paint() method immediately( read the repaint() doc. for better explaination).

    The sample code in the site i gave you does the job by starting seperate thread for sorting. I just gave a quick glance at the sample code.

    1. Applet implements Runnable interface and implements run method( so that you can pass applet itself as a target to a Thread )
    2. Applet starts a new thread ( when mouse is released )and the applet instance is passed as target
    3. run method in Applet creates an instance of a sorting algorithm class and pass it's instance as parent.
    4. SortAlgorithm class is the base class of all the three sorting algorithm classes.
    5. SortAlgorithm class have a method called "pause" which inturn calls parent class (applet) pause method.
    6. pause in Applet calls repaint and stop the thread for 20 milliseconds(?). Remember "Thread.sleep()" let the current thread(which is the sorting thread, not the UI thread ) sleep for some specified time. This will give the time for UI thread to call paint and paint itself.

    This is how it works. The key element here is the sorting Thread. Give special attention to that thread in the sample code.


Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center