Sort Hacks
Sort Hacks
Bubble sort
Bubble sort compares two adjacent elements in an array. It swaps the two elements so that the smaller is on the left and the larger one is on the right. The sort then moves on to the next two elements and repeats the process. This way, the largest element will move to the end of the array. Bubble sort then repeats this process until all the elements are sorted. Since the largest element moves to the end at the end of each iteration, on the next iteration, bubble sort will ignore the last elements. This is indicated with the nested for loop:
for (int j = 0; j < size - i - 1; j++)As can be seen, j, or the index of the array, depends on the value of i.
import java.util.Arrays;
public class Bubble {
public static void main(String[] args) {
int[] data = {1, 9, 3, 2, 5};
int size = data.length;
for (int i = 0; i < size; i++) {
for (int j = 0; j < size - i - 1; j++) {
int left = data[j];
int right = data[j+1];
if (right < left) {
int temp = left;
data[j] = right;
data[j+1] = temp;
}
}
}
for (int i = 0; i < size; i++) {
System.out.println(data[i]);
}
}
}
Bubble.main(null)
import java.util.Arrays;
public class Selection {
public static void main(String[] args) {
int[] data = {1, 9, 3, 2, 5};
int size = data.length;
for (int i = 0; i < size; i++) {
int min = data[i];
int index = i;
for (int j = i + 1; j < size; j++) {
if (min > data[j]) {
min = data[j];
index = j;
}
}
int temp = data[i];
data[i] = min;
data[index] = temp;
}
for (int i = 0; i < size; i++) {
System.out.println(data[i]);
}
}
}
Selection.main(null)
Insertion
In insertion sort, the algorithm first assumes that the first element is sorted. The algorithm then moves to the next element, and compares it with the elements before. The algorithm takes the element out and stores it in a variable. The algorithm then figures out where to move the element in by comparing the element with the values of the one before.
import java.util.Arrays;
public class Insertion {
public static void main(String[] args) {
int[] data = {1, 9, 3, 2, 5};
int size = data.length;
for (int i = 1; i < size; i++) {
int index = 0;
int num = 0;
boolean swap = false;
for (int j = i; j > 0; j--) {
num = data[i];
if (num < data[j-1]) {
index = j-1;
swap = true;
}
}
if (swap) {
for (int k = i; k > index; k--) {
data[k] = data[k-1];
}
data[index] = num;
}
}
for (int i = 0; i < size; i++) {
System.out.println(data[i]);
}
}
}
Insertion.main(null)
Merge sort
In merge sort, the array is split into half. This process is repeated until only one element is left per array. Next, the algorithm merges the elements together based on order. To do this, the algorithm compares the first element of each array with each other, puts the smallest element in a new array. It then moves to the next element in the array where the element was removed and comapres it with the other element in the array. This process is repeated until the new array is created that was sorted.
import java.util.Arrays;
public class Merge {
public Merge() {
}
private static void mergeSort(int[] data) {
int size = data.length;
if (size < 2) {
return;
}
int midIndex = size / 2;
int[] leftHalf = new int[midIndex];
int[] rightHalf = new int[size - midIndex];
for (int i = 0; i < midIndex; i++) {
leftHalf[i] = data[i];
}
for (int i = midIndex; i < size; i++) {
rightHalf[i - midIndex] = data[i];
}
mergeSort(leftHalf);
mergeSort(rightHalf);
merge(data, leftHalf, rightHalf);
}
private static void merge(int[] data, int[] leftHalf, int[] rightHalf) {
int leftSize = leftHalf.length;
int rightSize = rightHalf.length;
int i = 0;
int j = 0;
int k = 0;
while (i < leftSize && j < rightSize) {
if (leftHalf[i] <= rightHalf[j]) {
data[k] = leftHalf[i];
i++;
} else {
data[k] = rightHalf[j];
j++;
}
k++;
}
while (i < leftSize) {
data[k] = leftHalf[i];
i++;
k++;
}
while (j < leftSize) {
data[k] = rightHalf[j];
j++;
k++;
}
}
public static void printArray(int[] data) {
for (int i = 0; i < data.length; i++) {
System.out.println(data[i]);
}
}
public static void main(String[] args) {
int[] data = {1, 9, 3, 2, 5};
mergeSort(data);
printArray(data);
}
}
Merge.main(null)
public abstract class Collectable implements Comparable <Collectable> {
public final String masterType = "Collectable";
private String type; // extender should define their data type
// enumerated interface
public interface KeyTypes {
String name();
}
protected abstract KeyTypes getKey(); // this method helps force usage of KeyTypes
// getter
public String getMasterType() {
return masterType;
}
// getter
public String getType() {
return type;
}
// setter
public void setType(String type) {
this.type = type;
}
// this method is used to establish key order
public abstract String toString();
// this method is used to compare toString of objects
public int compareTo(Collectable obj) {
return this.toString().compareTo(obj.toString());
}
// static print method used by extended classes
public static void print(Collectable[] objs) {
// print 'Object' properties
System.out.println(objs.getClass() + " " + objs.length);
// print 'Collectable' properties
if (objs.length > 0) {
Collectable obj = objs[0]; // Look at properties of 1st element
System.out.println(
obj.getMasterType() + ": " +
obj.getType() +
" listed by " +
obj.getKey());
}
// print "Collectable: Objects'
for(Object o : objs) // observe that type is Opaque
System.out.println(o);
System.out.println();
}
}
/**
* Implementation of a Double Linked List; forward and backward links point to adjacent Nodes.
*
*/
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() {
}
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;
}
}
import java.util.Iterator;
/**
* Queue Iterator
*
* 1. "has a" current reference in Queue
* 2. supports iterable required methods for next that returns a generic T Object
*/
class QueueIterator<T> implements Iterator<T> {
LinkedList<T> current; // current element in iteration
// QueueIterator is pointed to the head of the list for iteration
public QueueIterator(LinkedList<T> head) {
current = head;
}
// hasNext informs if next element exists
public boolean hasNext() {
return current != null;
}
// next returns data object and advances to next position in queue
public T next() {
T data = current.getData();
current = current.getNext();
return data;
}
}
/**
* Queue: custom implementation
* @author John Mortensen
*
* 1. Uses custom LinkedList of Generic type T
* 2. Implements Iterable
* 3. "has a" LinkedList for head and tail
*/
public class Queue<T> implements Iterable<T> {
private String name = null; // name of queue
private int count = 0; // number of objects in queue
LinkedList<T> head = null, tail = null;
/** Constructor
* Queue constructor
* Parameters to name queue and Data Objects
*/
/*
public Queue(String name, T[]... seriesOfObjects) {
this.name = name;
this.addList(seriesOfObjects);
}
*/
/** Queue Accessors / Getters
* These gettrs return Queue Meta Data
*/
public String getName() {return this.name;}
public int getCount() {return this.count;}
/** Add an object
* Parameter is a Data Object that is added to end of the Queue,
*
* @param data, is the data to be inserted in the Queue.
*/
public void add(T data) {
// add new object to end of Queue
LinkedList<T> tail = new LinkedList<>(data, null);
if (this.head == null) {// initial condition
this.head = this.tail = tail;
}
else { // nodes in queue
this.tail.setNextNode(tail); // current tail points to new tail
this.tail = tail; // update tail
}
this.count++;
}
/** Add a list of Objects
* Paramter is a serise of Data Objects to be added to Queue
*
*/
public void addList(T[]... seriesOfObjects) { //accepts multiple generic T lists
for (T[] objects: seriesOfObjects)
for (T data : objects) {
this.add(data);
}
//printQueue();
}
/** Delete Head Element
* Returns the data of head.
*
* @return data, the dequeued data
*/
public T delete() {
T data = this.peek();
if (this.tail != null) { // initial or empty condition
this.head = this.head.getNext(); // current tail points to new tail
if (this.head != null) {
this.head.setPrevNode(tail);
}
this.count--;
}
return data;
}
/** Peak at Head Data
* Returns the data of head element
*
* @return this.head.getData(), the head data in Queue.
*/
public T peek() {
return this.head.getData();
}
/** Get Head
* Returns the head object
*
* @return this.head, the head object in Queue.
*/
public LinkedList<T> getHead() {
return this.head;
}
/** Get Tail
* Returns the tail object
*
* @return this.tail, the last object in Queue
*/
public LinkedList<T> getTail() {
return this.tail;
}
/** Implements Iterator
* Returns the iterator object.
*
* @return this, instance of object
*/
public Iterator<T> iterator() {
return new QueueIterator<>(this.head);
}
/** Print Queue
* Prints which by usage validates iterable and getters
*
*/
public void print() {
System.out.print(this.getName() + " " + this.getCount() +": ");
for (Object obj: this)
System.out.print("" + obj + " ");
System.out.println();
}
public void printQueue() {
for (Object obj: this){
System.out.print("" + obj + " ");
}
System.out.println();
}
// RETURN SIZE OF QUEUE
public int queueSize(Queue<T> queue) {
int size = 0;
for (T data : queue) {
size++;
}
return size;
}
}
public class Test<T> extends Queue<T> {
public int swap = 0;
public int comparison = 0;
public int getSwap() {
return swap;
}
public int getComparison() {
return comparison;
}
public Queue<T> bubble(Queue<T> queue) {
LinkedList<T> head = queue.getHead();
int size = queueSize(queue);
LinkedList<T> leftList = queue.getHead();
LinkedList<T> rightList = queue.getHead().getNext();
for (int i = 0; i < size; i++) {
leftList = queue.getHead();
rightList = queue.getHead().getNext();
for (int j = 0; j < size - i - 1; j++) {
comparison++;
T left = leftList.getData();
T right = rightList.getData();
Integer a = Integer.parseInt(left.toString());
Integer b = Integer.parseInt(right.toString());
if (a.compareTo(b) > 0) {
T temp = left;
leftList.setData(right);
leftList.getNext().setData(temp);
swap++;
}
leftList = leftList.getNext();
rightList = leftList.getNext();
}
}
Queue<T> queueReturn = new Queue<>();
for (int i = 0; i < size; i++) {
queueReturn.add(leftList.getData());
leftList = leftList.getNext();
}
return queueReturn;
}
}
class QueueTester {
public static void main(String[] args)
{
Integer[] words = new Integer[] {1, 9, 3, 2, 5};
// Integer[] words = new Integer[] {1, 9, 3, 2, 599};
Queue<Integer> queue = new Queue<>();
queue.addList(words);
Test test2 = new Test();
System.out.println(test2.bubble(queue));
test2.bubble(queue).printQueue();
}
}
QueueTester.main(null);
class QueueTester {
public static void main(String[] args)
{
long start = System.nanoTime();
int rand = 0;
Integer[] words = new Integer[5000];
for (int i = 0; i < 5000; i++) {
rand = (int)(Math.random() * 5001);
words[i] = rand;
}
Queue<Integer> queue = new Queue<>();
queue.addList(words);
Test test2 = new Test();
System.out.println(test2.bubble(queue));
test2.bubble(queue);
long end = System.nanoTime();
long diff = end - start;
System.out.println("time: " + diff + " nanoseconds");
System.out.println("swaps: " + test2.getSwap());
System.out.println("comparison: " + test2.getComparison());
}
}
QueueTester.main(null);
The twelve times were: 1382351197 1518772694 1419194044 1482452370 1429396442 1492955314 1484289813 1547380618 1563023076 1452845386 1441392214 1432165772
Leaving out the largest and smallest times, the average time was 1470084466.7 nanoseconds, or 1.470 seconds.
public class Selection<T> extends Queue<T> {
public int swap = 0;
public int comparison = 0;
public int getSwap() {
return swap;
}
public int getComparison() {
return comparison;
}
public Queue<T> selection(Queue<T> queue) {
LinkedList<T> head = queue.getHead();
int size = queueSize(queue);
LinkedList<T> leftList = queue.getHead();
LinkedList<T> rightList = queue.getHead().getNext();
T min = leftList.getData();
int index = 0;
for (int i = 0; i < size; i++) {
min = leftList.getData();
index = i;
for (int j = i + 1; j < size; j++) {
T next = rightList.getData();
Integer a = Integer.parseInt(min.toString());
Integer b = Integer.parseInt(next.toString());
if (a.compareTo(b) > 0) {
min = next;
index = j;
}
comparison++;
rightList = rightList.getNext();
}
T temp = leftList.getData();
leftList.setData(min);
LinkedList<T> replace = queue.getHead();
for (int j = 0; j < index; j++) {
replace = replace.getNext();
}
replace.setData(temp);
swap++;
leftList = leftList.getNext();
if (i != size - 1) {
rightList = leftList.getNext();
}
}
Queue<T> queueReturn = new Queue<>();
LinkedList<T> returnList = queue.getHead();
for (int i = 0; i < size; i++) {
queueReturn.add(returnList.getData());
returnList =returnList.getNext();
}
return queueReturn;
}
}
class SelectionTester {
public static void main(String[] args)
{
Integer[] words = new Integer[] {1, 9, 3, 2, 5};
Queue<Integer> queue = new Queue<>();
queue.addList(words);
Selection selector = new Selection();
System.out.println(selector.selection(queue));
selector.selection(queue).printQueue();
}
}
SelectionTester.main(null);
class SelectionTimeTester {
public static void main(String[] args)
{
int rand = 0;
Integer[] words = new Integer[5000];
for (int i = 0; i < 5000; i++) {
rand = (int)(Math.random() * 5001);
words[i] = rand;
}
Queue<Integer> queue = new Queue<>();
queue.addList(words);
long start = System.nanoTime();
Selection selector = new Selection();
selector.selection(queue);
long end = System.nanoTime();
long diff = end - start;
System.out.println("time: " + diff + " nanoseconds");
System.out.println("swaps: " + selector.getSwap());
System.out.println("comparison: " + selector.getComparison());
}
}
SelectionTimeTester.main(null);
The twelve times were: 687636054 636843905 686517174 642819604 686863058 684597760 688876699 653644990 667359947 657286135 624851036 733308142
Removing the highest and lowest time, the average time is 669,244,532.6 nanoseconds, or 0.669 seconds.
public class Insertion<T> extends Queue<T> {
public int swapNum = 0;
public int comparison = 0;
public int getSwapNum() {
return swapNum;
}
public int getComparison() {
return comparison;
}
public Queue<T> insertion(Queue<T> queue) {
LinkedList<T> head = queue.getHead();
int size = queueSize(queue);
LinkedList<T> leftList = queue.getHead();
LinkedList<T> rightList = queue.getHead().getNext();
T min = leftList.getData();
// int index = 0;
for (int i = 1; i < size; i++) {
int index = 0;
int num = 0;
boolean swap = false;
T one = null;
for (int j = i; j > 0; j--) {
one = rightList.getData();
Integer a = Integer.parseInt(one.toString());
leftList = queue.getHead();
T two = leftList.getData();
for (int k = j; k > 1; k--) {
leftList = leftList.getNext();
}
two = leftList.getData();
Integer b = Integer.parseInt(two.toString());
if (a.compareTo(b) < 0) {
index = j - 1;
swap = true;
}
comparison++;
}
leftList = queue.getHead();
if (swap) {
T switched = null;
for (int j = i; j > index; j--) {
for (int k = 0; k < j; k++) {
switched = leftList.getData();
leftList = leftList.getNext();
}
leftList.setData(switched);
leftList = queue.getHead();
}
leftList = queue.getHead();
for (int j = 0; j < index; j++) {
leftList = leftList.getNext();
}
leftList.setData(one);
swapNum++;
}
rightList = rightList.getNext();
}
Queue<T> queueReturn = new Queue<>();
LinkedList<T> returnList = queue.getHead();
for (int i = 0; i < size; i++) {
queueReturn.add(returnList.getData());
returnList =returnList.getNext();
}
return queueReturn;
}
}
class InsertionTester {
public static void main(String[] args)
{
Integer[] words = new Integer[] {9, 1, 3, 2, 5};
Queue<Integer> queue = new Queue<>();
queue.addList(words);
Insertion inserter = new Insertion();
System.out.println(inserter.insertion(queue));
inserter.insertion(queue).printQueue();
}
}
InsertionTester.main(null)
class InsertionTimeTester {
public static void main(String[] args)
{
int rand = 0;
Integer[] words = new Integer[2000];
for (int i = 0; i < 2000; i++) {
rand = (int)(Math.random() * 5001);
words[i] = rand;
}
Queue<Integer> queue = new Queue<>();
queue.addList(words);
long start = System.nanoTime();
Insertion inserter = new Insertion();
inserter.insertion(queue);
long end = System.nanoTime();
long diff = end - start;
System.out.println("time: " + diff + " nanoseconds");
System.out.println("swaps: " + inserter.getSwapNum());
System.out.println("comparison: " + inserter.getComparison());
}
}
InsertionTimeTester.main(null);
From the output above, it can be seen that insertion sort takes significantly more time than the other sort types (might also be due to the fact that my insertion algorithm isn't the most efficient). Furthermore, generating 5000 random numbers will crash my computer, which is why the code above only generates 2000 random numbers.