The focus of this assignment is the sort Algorithms . After seeing and hearing about the four basic sorting algorithms (bubble, selection, insertion and merge), this lab will help put these ideas to use. Here we have a starter code for each of these. They all will create an int array of any size and fill it up with random numbers from 1 to 10.
public class SimpleBubble {
/**
* Returns an array of n random integers
* from 1 to 10
* @param n is the size of the array desired
* @return an array of n random integers from 1 to 10
*/
private static int[] randomArray(int n)
{
int[] result = new int[n];
for (int i=0;i<n;i++) result[i]=1+(int)(10*Math.random());
return result;
}
/**
* sorts an int array
* @param a the array of integers, unsorted
* @return a sorted array of integers
*/
private static int[] bubbleSort(int[] a)
{
boolean notDoneYet=true;
while (notDoneYet)
{
notDoneYet=false;
for (int i=0;i<a.length-1;i++)
{
if(a[i+1]<a[i])
{
notDoneYet=true;
int buffy=a[i];
a[i]=a[i+1];
a[i+1]=buffy;
}
}
}
return a;
}
public static void main (String[] args){
int[] a = randomArray(15);
System.out.println("Before sort:");
for (int item:a) System.out.print(item+" ");
long time=System.currentTimeMillis();
a = bubbleSort(a);
time=System.currentTimeMillis()-time;
System.out.println("\nAfter sort:");
for (int item:a) System.out.print(item+" ");
System.out.println("\nlapsed time:"+(time)+" milliseconds");
}
}
public class SimpleSelection {
/**
* Returns an array of n random integers
* from 1 to 10
* @param n is the size of the array desired
* @return an array of n random integers from 1 to 10
*/
private static int[] randomArray(int n)
{
int[] result = new int[n];
for (int i=0;i<n;i++) result[i]=1+(int)(10*Math.random());
return result;
}
/**
* sorts an int array
* @param a the array of integers, unsorted
* @return a sorted array of integers
*/
private static int[] selectionSort(int[] a)
{
for (int i=0; i< a.length-1; i++)
{
//presume the first index has the lowest value
int min=i;
//look at the remainder of the list to see if
//we can do better
for (int j=i+1; j< a.length; j++)
if (a[j]<a[min]) min=j;
//swap
int buffy=a[i];
a[i]=a[min];
a[min]=buffy;
}
return a;
}
public static void main (String[] args){
int[] a = randomArray(15);
System.out.println("Before sort:");
for (int item:a) System.out.print(item+" ");
long time=System.currentTimeMillis();
a = selectionSort(a);
time=System.currentTimeMillis()-time;
System.out.println("\nAfter sort:");
for (int item:a) System.out.print(item+" ");
System.out.println("\nlapsed time:"+(time)+" milliseconds");
}
}
public class SimpleInsertion {
/**
* Returns an array of n random integers
* from 1 to 10
* @param n is the size of the array desired
* @return an array of n random integers from 1 to 10
*/
private static int[] randomArray(int n)
{
int[] result = new int[n];
for (int i=0;i<n;i++) result[i]=1+(int)(10*Math.random());
return result;
}
/**
* sorts an int array
* @param a the array of integers, unsorted
* @return a sorted array of integers
*/
private static int[] insertionSort(int[] a)
{
for (int i=1; i < a.length ; i++)
{
int value=a[i];
int j=i-1;
while (j>=0 && a[j]>value)
{
a[j+1]=a[j];
j=j-1;
}
a[j+1]=value;
//Comment next line to hide progress
System.out.println("\nStep "+i+":");
for (int item:a) System.out.print(item+" ");
}
return a;
}
public static void main (String[] args){
int[] a = randomArray(15);
System.out.println("Before sort:");
for (int item:a) System.out.print(item+" ");
long time=System.currentTimeMillis();
a = insertionSort(a);
time=System.currentTimeMillis()-time;
System.out.println("\nAfter sort:");
for (int item:a) System.out.print(item+" ");
System.out.println("\nlapsed time:"+(time)+" milliseconds");
}
}
import java.util.ArrayList;
public class SimpleMerge {
/**
* Returns an array of n random integers
* from 1 to 10
* @param n is the size of the array desired
* @return an array of n random integers from 1 to 10
*/
private static ArrayList<Integer> randomArrayList(int n)
{
ArrayList<Integer> result = new ArrayList<Integer>();
for (int i=0;i<n;i++) result.add(1+(int)(10*Math.random()));
return result;
}
/**
* sorts an int array
* @param a the array of integers, unsorted
* @return a sorted array of integers
*/
public static ArrayList<Integer> mergeSort(ArrayList<Integer> a)
{
if (a.size()<=1) return a;
int middle=a.size()/2;
ArrayList<Integer> left=new ArrayList<Integer>();
ArrayList<Integer> right=new ArrayList<Integer>();
for (int i=0;i<middle; i++)
{
left.add(a.get(i));
}
for (int i=middle;i<a.size();i++)
{
right.add(a.get(i));
}
//Comment out the line below to hide the progress:
System.out.println("left ="+left+"\tright="+right);
left =mergeSort(left);
right=mergeSort(right);
ArrayList<Integer> result=merge(left,right);
//Comment out the line below to hide the progress:
System.out.println("after merge = "+result);
return result;
}
private static ArrayList<Integer> merge(ArrayList<Integer> left, ArrayList<Integer> right)
{
ArrayList<Integer> result=new ArrayList<Integer>();
while (left.size()>0 && right.size()>0)
{
if (left.get(0)<= right.get(0)){
result.add(left.get(0));
left.remove(0);
}else {
result.add(right.get(0));
right.remove(0);
}
}
//Since left or right ran out, we attach the remainder to the result
while (left.size()>0)
{
result.add(left.get(0));
left.remove(0);
}
while (right.size()>0)
{
result.add(right.get(0));
right.remove(0);
}
return result;
}
public static void main (String[] args){
System.out.print("Merge sort");
ArrayList<Integer> a = randomArrayList(5);
System.out.println("Before sort:");
System.out.println(a);
long time=System.currentTimeMillis();
a = mergeSort(a);
time=System.currentTimeMillis()-time;
System.out.println("\nAfter sort:");
System.out.print(a);
System.out.println("\nlapsed time:"+(time)+" milliseconds");
}
}
import java.util.ArrayList;
public class SimpleQuickSort {
/**
* Returns an array of n random integers
* from 1 to 10
* @param n is the size of the array desired
* @return an array of n random integers from 1 to 10
*/
private static ArrayList<Integer> randomArrayList(int n)
{
ArrayList<Integer> result = new ArrayList<Integer>();
for (int i=0;i<n;i++) result.add(1+(int)(10*Math.random()));
return result;
}
/**
* sorts an int array
* @param a the array of integers, unsorted
* @return a sorted array of integers
*/
public static ArrayList<Integer> quickSort(ArrayList<Integer> a)
{
if (a.size()<=1) return a;
int halfway=a.size()/2;//the choice of the pivot is arbitrary
int pivot=a.get(halfway);
a.remove(halfway);
ArrayList<Integer> less=new ArrayList<Integer>();
ArrayList<Integer> more=new ArrayList<Integer>();
for(int i=0; i<a.size(); i++)
{
if (a.get(i)<pivot){
less.add(a.get(i));
} else {
more.add(a.get(i));
}
}
//Comment out the line below to hide the progress:
//System.out.println("\npivot="+pivot+"\tless ="+less+"\tmore="+more);
//Divide and conquer:
less=quickSort(less);
more=quickSort(more);
//Now we concatenate the result:
less.add(pivot);
for (int i=0; i<more.size(); i++) less.add(more.get(i));
return less;
}
public static void main (String[] args){
ArrayList<Integer> a = randomArrayList(10);
System.out.println("Before sort:");
for (int item:a) System.out.print(item+" ");
long time=System.currentTimeMillis();
a = quickSort(a);
time=System.currentTimeMillis()-time;
System.out.println("\nAfter sort:");
for (int item:a) System.out.print(item+" ");
System.out.println("\nlapsed time:"+(time)+" milliseconds");
}
}
String[] a={ "Apple", "Zebra" , "Dog", "Chimp" };
or use a random string generator:
private static String[] randomStringArray(int n)
{
String alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
String[] result = new String[n];
for (int i=0;i<i++){
int s=(int)(26*Math.random());
result[i]=alphabet.substring(s,s+1);
return result;
}
}
or
public static ArrayList<String> randomStringArray(int n)
{
String alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
ArrayList<String> result = new ArrayList<String>();
for (int i=0;i<n;i++){
int s=(int)(26*Math.random());
result.add(alphabet.substring(s,s+1));
}
return result;
}
Since String is an object, not a simple data type, you cannot use the "<" comparison operator. Instead use the compareTo method.
For example:
String word1="Apple"; String word2="Banana"; if (word1.compareTo(word2) < 0 ) System.out.println( word1 + " is less than "+ word2);
import java.applet.Applet;
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Image;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.awt.event.MouseEvent;
import java.awt.event.MouseListener;
import javax.swing.Timer;
@SuppressWarnings("serial")
public class SortApplet extends Applet implements MouseListener, ActionListener
{
Timer timer;
int[] a= { 5,1,9,2,3,4,8,6,7};
int appletWidth, appletHeight;
Image virtualMem;
Graphics gBuffer;
String message;
int step=0; // the current step
boolean nothingChanged;
public void init()
{
addMouseListener(this);
timer = new Timer(1000, this);
nothingChanged=false;
appletWidth = getWidth();
appletHeight = getHeight();
virtualMem = createImage(appletWidth,appletHeight);
gBuffer = virtualMem.getGraphics();
gBuffer = virtualMem.getGraphics();
gBuffer.setColor(Color.white);
gBuffer.fillRect(0,0,appletWidth,appletHeight);
message="Click Mouse to Restart";
}
public void paint(Graphics g)
{
gBuffer.setColor(Color.white);
gBuffer.fillRect(0,0,appletWidth,appletHeight);
gBuffer.setColor(Color.black);
gBuffer.drawString("Bubble Sort Demo", 20, 20);
gBuffer.drawString(message, 20, 40);
for (int i=0; i< a.length; i++ ){
if (step==i || step==(i+1)) {
gBuffer.setColor(Color.blue);
} else {
gBuffer.setColor(Color.red);
}
gBuffer.fillRect(20+i*20, 200-a[i]*15, 18, a[i]*15);
}
//Now we send the result to the screen
g.drawImage(virtualMem,0,0,this);
}
/**
* MOUSE LISTENER STUFF:
*
* Since we are implementing the MouseListener Interface
* There are some required methods we need to declare here, even
* if there is nothing to do if that mouse event occurs:
*/
public void mouseEntered(MouseEvent e) {}
public void mouseExited(MouseEvent e) {}
public void mouseClicked(MouseEvent e) {}
public void mouseReleased(MouseEvent e) {}
public void mousePressed(MouseEvent e)
{
if (timer.isRunning() )
{
timer.stop();
if (message=="done"){
for (int i=0;i<a.length;i++) {
a[i]=1+(int)(Math.random()*9.0);
}
step=0;
}
message="Stopped";
}else{
timer.start();
message="Started";
}
//if (b.contains(x,y) ) b.changeColor();
repaint();
}
/**
* ActionListener is an interface and
* requires the actionPerformed() method
* to be defined..in this case we
* look for a timer event
*/
public void actionPerformed(ActionEvent e)
{
Object source = e.getSource();
if (source == timer)
// the passage of time, so we do the next thing
{
if (step< a.length-1 && a[step]>a[step+1]){
int swappedValue=a[step+1];
a[step+1]=a[step];
a[step]=swappedValue;
nothingChanged=false;
message=a[step]+" is bigger than "+a[step+1]+" so we swap "+step+"th and "+(step+1)+"th positions";
} else
if (step< a.length-1) message=a[step]+" is less than "+a[step+1]+" no swap needed";
step++;
if (step>=a.length-1){
if (nothingChanged){
message="done";
}else{
nothingChanged=true;
step=0;
}
}
}
repaint();
}
public void update(Graphics g){
paint(g);
}
}