SelectionSort.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
import java.util.Random; import java.util.stream.Collectors; import java.util.Collections; import java.util.Arrays; public class SelectionSort<T extends Comparable<T>> { public void sort(T[] arr){ // i delimits the sorted and unsorted subarrays for (int i = 0; i < arr.length - 1; i++){ // Find the smallest element in the unsorted // subarray i -> end int minIndex = i; for (int j = i; j < arr.length; j++){ if (arr[j].compareTo(arr[minIndex]) < 0) minIndex = j; } // Do the swap. T smallest = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = smallest; } } public static Integer[] getRandoms(int count){ return new Random().ints().limit(count).boxed().toArray(Integer[]::new); } public static void main(String[] args){ // Small test SelectionSort<Integer> ss = new SelectionSort<>(); Integer[] ints = {35, 65, 30, 60, 20}; ss.sort(ints); for (Integer i : ints) System.out.print(i + " "); System.out.println(); Integer[] randoms = getRandoms(80000); long startTime = System.currentTimeMillis(); ss.sort(randoms); long endTime = System.currentTimeMillis(); System.out.println("Total sort of random data execution time: " + (endTime - startTime) ); System.gc(); // Re-sort already sorted, sort reversed. //Collections.reverse(Arrays.asList(randoms)); startTime = System.currentTimeMillis(); ss.sort(randoms); endTime = System.currentTimeMillis(); System.out.println("Total resort execution time: " + (endTime - startTime) ); } } |
LinkedList.java (Insertion sort version)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 |
import java.util.List; import java.util.Random; import java.util.stream.Collectors; import java.util.Collections; import java.util.Arrays; public class LinkedList<T extends Comparable<T>> { private class Node<T extends Comparable<T>> { T data; Node<T> next; public Node(T data){ this.data = data; } public Node(T data, Node<T> next){ this(data); this.next = next; } public String toString(){ return "" + data; } } private Node<T> head, tail; private int count; public LinkedList(){ count = 0; } public void clear(){ head = null; count = 0; } public void prepend (T i){ if (count == 0){ head = tail = new Node<T>(i); } else { head = new Node<T>(i, head); } count++; } public void append(T i){ if (count == 0){ head = tail = new Node<T>(i); } else { tail = tail.next = new Node<T>(i); } count++; } public int size(){ return count; } public boolean isEmpty(){ return head == null; } // Precondition: list is sorted. private void sortedInsert(T i){ if (count == 0 || i.compareTo(head.data) < 0) prepend(i); else{ Node<T> temp = head; while(temp.next != null && temp.next.data.compareTo(i) < 0) temp = temp.next; temp.next = new Node<T>(i, temp.next); if (temp == tail) tail = temp.next; count++; } } // Sorts an existing list. public void insertionSort(){ Node<T> temp = head; head = tail = null; count = 0; while (temp != null){ sortedInsert(temp.data); temp = temp.next; } } public String toString() { String retVal = "Linked list with " + count + " elements\nNodes:"; for (Node<T> temp = head; temp != null; temp = temp.next) retVal += temp + " "; retVal += "\nhead: " + head.data + " tail: " + tail.data; return retVal; } public static List<Integer> getRandoms(int count){ return new Random().ints().limit(count).boxed().collect(Collectors.toList()); } public static void main(String[] args){ // Small test LinkedList<Integer> ll = new LinkedList<>(); ll.append(3); ll.append(1); ll.append(5); ll.append(4); //System.out.println(ll.toString()); ll.insertionSort(); //System.out.println(ll.toString()); ll.clear(); List<Integer> randoms = getRandoms(80000); // Measure prepend insert time long startTime = System.currentTimeMillis(); for(Integer r : randoms) ll.prepend(r); long endTime = System.currentTimeMillis(); System.out.println("Total prepend execution time: " + (endTime - startTime) ); // Normal sort test on random data. /* startTime = System.currentTimeMillis(); ll.insertionSort(); endTime = System.currentTimeMillis(); System.out.println("Total insertionSort execution time: " + (endTime - startTime) );*/ // Test already sorted / reversed with sortedInsert. Collections.sort(randoms); Collections.reverse(randoms); ll.clear(); startTime = System.currentTimeMillis(); for (Integer r : randoms) ll.sortedInsert(r); endTime = System.currentTimeMillis(); System.out.println("Total sortedInsert of resorted data execution time: " + (endTime - startTime) ); } } |