# Sort Lab1

This program requires knowledge of various sort algorithms

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.

## simpleBubble.java

Finish writing the bubbleSort method. Hint
```
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");
}

}

```

## simpleSelection.java

Hint
```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");
}

}

```

## SimpleInsertion.java

Hint
```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");
}

}

```

## SimpleMerge.java

This is an example of implementing the Merge Sort for an array of int[]. More Explanation Here
```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>();
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++)
{
}
for (int i=middle;i<a.size();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)){
left.remove(0);
}else {
right.remove(0);
}
}
//Since left or right ran out, we attach the remainder to the result
while (left.size()>0)
{
left.remove(0);
}
while (right.size()>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");

}

}

```

## SimpleQuickSort.java

Hint
```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>();
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){
} else {
}
}
//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:
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");
}

}
```

## 8-Point Version Output

Make a Project in your favorite IDE and run and compare times with different sized lists.

## 9 Point Version

Adapt each algorithm to work with an array of Strings rather than int. You can make your own String array:
```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());
}
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);
```

## 10 Point Version

Overload the selectionSort method and the insertionSort method to sort an ArrayList (as in the mergeSort method).

## 11 Point Version

Make a Selection, Insertion or Merge Sort Applet like this one for the BubbleSort:

## SortApplet

Here is a graphing demonstration of a bubbleSort
```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()
{

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

```