#
Sort

/*************************************************************************** * Author: Isai Damier * Title: Singly Linked List * Project: geekviewpoint * Package: datastructure * * Description: A LinkedList is a data structure that allows access * to a collection of data using pointers/references. While an * array can also be defined as above, LinkedLists and arrays differ * in how they are stored in memory and in the operations they * allow. Unlike an array that must be stored in a block of memory, * the nodes of a LinkedList can be stored anywhere because each * node has a reference to the node that succeeds it. Because the * nodes are stored so loosely, inserting nodes into a LinkedList * is easy; whereas in an array, all the succeeding elements must * be shifted. Of course, insertion also means changing the size of * the array, which means creating the entire array anew. * * Perhaps the greatest beauty of LinkedList is that it allows * accessing an entire sequence of nodes using only one variable: * a reference to the first node in the sequence. * * Countless operations can be performed on LinkedLists. Following * are a few, ranging from the common to the very interesting. **************************************************************************/ public class SinglyLinkedList { Node head = null; Node tail = null; /***************************************************************** * Time Complexity of Solution: * O(n*log n). * * Description: Sort the elements in this linked list in ascending * order. * * Technical Details: Sorting a LinkedList in place is very costly: * in the order of O(n^2 * log(n)) with a good algorithm. * Therefore it makes sense to create an array from the list, * sort the array, and then empty the array into the list by * index. It's kind of like: unbutton a shirt; move the buttons * around; then button the shirt anew. (I think it's a good analogy.) *****************************************************************/ public void sort() { if (2 > this.size()) { return; } int[] A = new int[this.size()]; //unfasten the buttons (i.e. unbutton the shirt) int x = 0; for (Node t = head; null != t; t = t.next) { A[x++] = t.data;//list fills array } //sort the buttons mergesort(A, 0, A.length - 1); //refasten the buttons (i.e. button the shirt anew) x = 0; for (Node t = head; null != t; t = t.next) { t.data = A[x++];//array fills list } } private void mergesort(int[] input, int first, int last) { //break array into smaller structurally identical pieces int mid = (first + last) / 2; if (first < last) { mergesort(input, first, mid); mergesort(input, mid + 1, last); } //merge sorted pieces to get solution to original array int a = 0, f = first, l = mid + 1; int[] tmp = new int[last - first + 1]; while (f <= mid && l <= last) { tmp[a++] = input[f] < input[l] ? input[f++] : input[l++]; } while (f <= mid) { tmp[a++] = input[f++]; } while (l <= last) { tmp[a++] = input[l++]; } a = 0; while (first <= last) { input[first++] = tmp[a++]; } } }

public class SinglyLinkedListTest { /** * Test of sort method, of class SinglyLinkedList. */ @Test public void testSort() { System.out.println("sort"); int[] input = {9, 4, 5, 2, 1, 12, 6, 7, 4, 8, 3, 0, 16, 19, 11}; SinglyLinkedList linkedList = new SinglyLinkedList(); for (int i = 0; i < input.length; i++) { linkedList.addToTail(input[i]); } assertTrue(Arrays.equals(input, linkedList.toArray())); Arrays.sort(input); assertFalse(Arrays.equals(input, linkedList.toArray())); linkedList.sort(); assertTrue(Arrays.equals(input, linkedList.toArray())); } }