-
April 10th, 2002, 08:20 AM
#1
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
-
April 10th, 2002, 09:05 AM
#2
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
-
April 10th, 2002, 10:35 AM
#3
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
-
April 10th, 2002, 01:20 PM
#4
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.
-
April 10th, 2002, 02:15 PM
#5
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.
-
April 10th, 2002, 04:48 PM
#6
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
-
April 10th, 2002, 05:40 PM
#7
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.
-
April 10th, 2002, 06:13 PM
#8
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?
-
April 11th, 2002, 08:54 AM
#9
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
-
April 11th, 2002, 09:42 AM
#10
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|