public class SortAnalyzer {
public static int[] numberArray() {
int indexes = 5000;
int[] arr = new int[indexes];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 10000);
}
return arr;
}
public static float[] main(String[] args) {
int[] arr1 = numberArray();
int[] arr2 = new int[5000];
int[] arr3 = new int[5000];
int[] arr4 = new int[5000];
System.arraycopy(arr1, 0, arr2, 0, 500);
System.arraycopy(arr1, 0, arr3, 0, 500);
System.arraycopy(arr1, 0, arr4, 0, 500);
float[] times = new float[4];
String str = "";
long start = System.nanoTime();
bubbleSort(arr1);
long end = System.nanoTime();
str += ((end - start) + "ns | ");
times [0] = (end - start);
start = System.nanoTime();
mergeSort(arr2);
end = System.nanoTime();
str += ((end - start) + "ns | ");
times [1] = (end - start);
start = System.nanoTime();
selectionSort(arr3);
end = System.nanoTime();
str += ((end - start) + "ns | ");
times [2] = (end - start);
start = System.nanoTime();
insertionSort(arr4);
end = System.nanoTime();
str += ((end - start) + "ns");
times [3] = (end - start);
System.out.println(str);
return times;
}
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int current = arr[i];
int j = i - 1;
while (j >= 0 && current < arr[j]) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
}
public static void selectionSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
public static void mergeSort(int[] arr) {
if (arr.length > 1) {
int[] left = leftHalf(arr);
int[] right = rightHalf(arr);
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
}
public static int[] leftHalf(int[] arr) {
int size1 = arr.length / 2;
int[] left = new int[size1];
for (int i = 0; i < size1; i++) {
left[i] = arr[i];
}
return left;
}
public static int[] rightHalf(int[] arr) {
int size1 = arr.length / 2;
int size2 = arr.length - size1;
int[] right = new int[size2];
for (int i = 0; i < size2; i++) {
right[i] = arr[i + size1];
}
return right;
}
public static int[] merge(int[] result, int[] left, int[] right) {
int i1 = 0;
int i2 = 0;
for (int i = 0; i < result.length; i++) {
if (i2 >= right.length || (i1 < left.length && left[i1] <= right[i2])) {
result[i] = left[i1];
i1++;
} else {
result[i] = right[i2];
i2++;
}
}
return result;
}
}
float[] means = new float[4];
for (int i = 0; i < 12; i++) {
float[] a = SortAnalyzer.main(null);
for (int j = 0; j < 4; j++) {
means[j] += a[j];
}
}
for (int i = 0; i < 4; i++) {
means[i] /= 12;
means[i] = Math.round(means[i] * 1000) / 1000;
}
System.out.println("Averages: ");
System.out.println("Bubble: " + means[0] + "ns");
System.out.println("Merge: " + means[1] + "ns");
System.out.println("Selection: " + means[2] + "ns");
System.out.println("Insertion: " + means[3] + "ns");
import java.util.HashMap;
import java.lang.Integer;
import java.util.Scanner;
public class HashTest {
public static void main(String[] args) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
int[] arr = new int[500000];
for (int i = 0; i < 500000; i++) {
Integer value = (int) (Math.random() * 500000);
map.put(value, value);
arr[i] = value;
}
double total_lut = 0;
double total_bst = 0;
// get num to search for from scanner
Scanner sc = new Scanner(System.in);
System.out.println("Search for a number: ");
Integer num = sc.nextInt();
for (int i = 0; i < 12; i++) {
// check look up time for hash map
String str = "| ";
long lut = (lookUp(map, num));
total_lut += lut;
str += (lut + "ns | ");
// copy array, check binary search time
int[] array1 = new int[500000];
System.arraycopy(arr, 0, array1, 0, arr.length);
long bst = (binarySearchTime(array1, num));
total_bst += bst;
str += (bst + "ns | ");
System.out.println(str);
}
System.out.println("Average: " + (total_lut / 12) + "ns | " + (total_bst / 12) + "ns");
}
public static long lookUp(HashMap<Integer, Integer> map, Integer value) {
long start = System.nanoTime();
map.containsKey(value);
long end = System.nanoTime();
return (end - start);
}
public static long binarySearchTime(int[] arr, Integer value) {
long start = System.nanoTime();
// binary search
int low = 0;
int high = arr.length - 1;
int mid = (low + high) / 2;
while (low <= high) {
if (arr[mid] < value) {
low = mid + 1;
} else if (arr[mid] == value) {
break;
} else {
high = mid - 1;
}
mid = (low + high) / 2;
}
long end = System.nanoTime();
return (end - start);
}
}
HashTest.main(null);
public class LinkedList<T> {
private T data;
private LinkedList<T> prevNode, nextNode;
/**
* Constructs a new element
*
* @param data, data of object
* @param node, previous node
*/
public LinkedList(T data, LinkedList<T> node)
{
this.setData(data);
this.setPrevNode(node);
this.setNextNode(null);
}
/**
* Clone an object,
*
* @param node object to clone
*/
public LinkedList(LinkedList<T> node)
{
this.setData(node.data);
this.setPrevNode(node.prevNode);
this.setNextNode(node.nextNode);
}
/**
* Setter for T data in DoubleLinkedNode object
*
* @param data, update data of object
*/
public void setData(T data)
{
this.data = data;
}
/**
* Returns T data for this element
*
* @return data associated with object
*/
public T getData()
{
return this.data;
}
/**
* Setter for prevNode in DoubleLinkedNode object
*
* @param node, prevNode to current Object
*/
public void setPrevNode(LinkedList<T> node)
{
this.prevNode = node;
}
/**
* Setter for nextNode in DoubleLinkedNode object
*
* @param node, nextNode to current Object
*/
public void setNextNode(LinkedList<T> node)
{
this.nextNode = node;
}
/**
* Returns reference to previous object in list
*
* @return the previous object in the list
*/
public LinkedList<T> getPrevious()
{
return this.prevNode;
}
/**
* Returns reference to next object in list
*
* @return the next object in the list
*/
public LinkedList<T> getNext()
{
return this.nextNode;
}
}
public class Stack<T> {
private LinkedList<T> upper;
private int size;
public Stack() {
this.upper = null;
this.size = 0;
}
public void push(T data) {
LinkedList<T> newNode = new LinkedList<T>(data, this.upper);
this.upper = newNode;
this.size++;
}
public T peek() {
try {
return this.upper.getData();
} catch (NullPointerException e) {
System.out.println("No upper element, empty stack!");
return null;
}
}
public T pop() {
try {
T data = this.upper.getData();
this.upper = this.upper.getPrevious();
this.size--;
return data;
} catch (NullPointerException e) {
System.out.println("No upper element, empty stack!");
return null;
}
}
public int size() {
return this.size;
}
public boolean isEmpty() {
return this.size == 0;
}
public String toString() {
String s = "[ ";
LinkedList<T> currentNode = upper;
while (currentNode != null) {
s += currentNode.getData();
currentNode = currentNode.getPrevious();
if (currentNode != null) {
s += ", ";
}
}
s += " ]";
return s;
}
public void bubbleSort() {
if (this.size <= 1) {
return;
}
Stack<T> sorted = new Stack<T>();
while (!this.isEmpty()) {
T temp = this.pop();
while (!sorted.isEmpty() && ((Comparable<T>) sorted.peek()).compareTo(temp) > 0) {
this.push(sorted.pop());
}
sorted.push(temp);
}
while (!sorted.isEmpty()) {
this.push(sorted.pop());
}
}
}
public class Tester {
public static void main(String[] args) {
Stack<Integer> s1 = new Stack<Integer>();
s1.push(3);
s1.push(4);
s1.push(1);
s1.push(2);
s1.push(5);
System.out.println(s1.toString());
s1.bubbleSort();
System.out.println(s1.toString());
}
}
Tester.main(null);
public abstract class Collectable implements Comparable <Collectable> {
public final String masterType = "Collectable";
private String type;
public interface KeyTypes {
String name();
}
protected abstract KeyTypes getKey();
public String getMasterType() {
return masterType;
}
public String getType() {
return type;
}
public void setType(String type) {
this.type = type;
}
public abstract String toString();
public int compareTo(Collectable obj) {
return this.toString().compareTo(obj.toString());
}
public static void print(Collectable[] objs) {
if (objs.length > 0) {
Collectable obj = objs[0];
System.out.println(
obj.getMasterType() + ": " +
obj.getType() +
" listed by " +
obj.getKey());
}
System.out.println("-------------------------");
for(Object o : objs)
System.out.println(o);
System.out.println();
}
}
public class SportsTeam extends Collectable {
public static KeyTypes key = KeyType.name;
public static void setOrder(KeyTypes key) {SportsTeam.key = key;}
public enum KeyType implements KeyTypes {name, numMembers}
private final String name;
private final int numMembers;
SportsTeam(String name, int numMembers)
{
this.setType("SportsTeam");
this.name = name;
this.numMembers = numMembers;
}
@Override
protected KeyTypes getKey() { return SportsTeam.key; }
@Override
public String toString() {
String output = super.getType() + ": " + this.name + " has " + this.numMembers + " members.";
return output;
}
// Test data initializer
public static SportsTeam[] SportsTeamArray() {
return new SportsTeam[]{
new SportsTeam("Boston Red Sox", 26),
new SportsTeam("New York Yankees", 23),
new SportsTeam("San Diego Padres", 28),
new SportsTeam("Los Angeles Dodgers", 22),
new SportsTeam("Atlanta Braves", 24),
new SportsTeam("Chicago Cubs", 29),
new SportsTeam("Houston Astros", 25)
};
}
public static void main(String[] args)
{
SportsTeam[] objs = SportsTeamArray();
List<SportsTeam> SportsTeamArray = new ArrayList<SportsTeam>(Arrays.asList(objs));
SportsTeam.setOrder(KeyType.numMembers);
SportsTeam.print(objs);
SportsTeam.setOrder(KeyType.name);
Collections.sort(SportsTeamArray);
SportsTeam.setOrder(KeyType.numMembers);
for (SportsTeam team : SportsTeamArray)
System.out.println(team);
}
}
SportsTeam.main(null);