/************************* * Written By: bornToCode() ************************* This program implements a linked radix sort. It displays how the radix sort works at each pass. The time complexity of the radix sort is O(n * k), where n is the number of keys, and k is the length of the longest key. Since the radix sort doesn't rely on comparisons, it is much faster than any sorting method that relys on comparisons (even merge and quick sort). However, this is only true if: 1: The keys to be sorted can be broken apart (i.e. numbers into digits, words into characters). 2: The number of keys is large, while the length of the keys is small. Anyways, I hope this program hopes to show how the radix sort works... Enjoy! **NOTE: I didn't use java's library data structures (lists or queues) because: * 1: This is implementation dependent * 2: I tried to optimize the linked lists for the radix sort * 3: I need practice with data structures (I'm learning too ;) ) * 4: I'm a noob Feel free to use any of my code, but please give me credit! Also, if you notice any bugs (I'm sure there are many, lol), please let me know! Thank you! */ public class Node { public String data; public Node next; public Node(String data) { this.data = data; next = null; } public Node(String data, Node next) { this.data = data; this.next = next; } } public class LinkedList { protected Node head; protected Node tail; protected int count; public LinkedList() { head = null; tail = null; count = 0; } public final boolean isEmpty() { return count == 0; } public final boolean isFull() { return false; } public final int size() { return count; } public void clear() { while(!isEmpty()) { remove(0); } head = tail = null; } public void insert(int position, String data) { if(isEmpty() && position == 0) head = new Node(data); else if(position < 0 || position >= count) { return; } else if(position == 0) { Node newNode; if(count == 1) { tail = new Node(head.data); newNode = new Node(data, tail); } else { newNode = new Node(data, head); } head = newNode; } else if(position == count - 1) { Node newNode = new Node(data); tail.next = newNode; tail = newNode; } else if(position == count - 2) { Node preceding = getNode(position); Node newNode = new Node(data, tail); preceding.next = newNode; } else { Node preceding = getNode(position); Node following = preceding.next; Node newNode = new Node(data, following); preceding.next = newNode; } count++; } public void append(String data) { Node newNode = new Node(data); if(isEmpty()) { head = newNode; tail = head; } else if(count == 1) { head.next = newNode; tail = newNode; } else { tail.next = newNode; tail = newNode; } count++; } public String remove(int position) { String removed = null; if(isEmpty() || position < 0 || position >= count) { return removed; } else if(position == 0) { removed = head.data; head = head.next; } else if(position == count - 1) { Node previous = getNode(position - 1); Node target = tail; removed = target.data; previous.next = null; target = null; tail = previous; } else { Node previous = getNode(position - 1); Node target = getNode(position); removed = target.data; previous.next = target.next; target = null; } count--; return removed; } public String retrieve(int position) { if(isEmpty() || position < 0 || position >= count) { return null; } else if(position == 0) return head.data; else { Node target = getNode(position); return target.data; } } public void replace(int position, String data) { if(isEmpty() || position < 0 || position >= count) return; else if(position == 0) head.data = data; else { Node target = getNode(position); target.data = data; } } public String toString() { Node current; String list = ""; for(current = head; current != null; current = current.next) { list += current.data; if(current.next != null) list += ", "; } return list; } public void concat(LinkedList otherList) { if(otherList.head == null) { return; } if(count == 0) { head = otherList.head; tail = otherList.tail; } else { tail.next = otherList.head; tail = otherList.tail; } count += otherList.count; } protected final Node getNode(int position) { Node temp = head; for(int i = 0; i < position; i++) { temp = temp.next; } return temp; } } public class SortableList extends LinkedList { protected int maxKeyLength; protected final int MAX_CHARACTERS = 28; public SortableList() { super(); maxKeyLength = 0; } private void findMaxKey() { if(isEmpty()) { maxKeyLength = 0; } else if(count == 1) { maxKeyLength = head.data.length(); } else { Node current; for(current = head; current != null; current = current.next) { if(current.data.length() > maxKeyLength) { maxKeyLength = current.data.length(); } } } } private void addPadding() { for(Node current = head; current != null; current = current.next) { String word = current.data; while(word.length() < maxKeyLength) { word += " "; } } } private void updateKeys() { findMaxKey(); addPadding(); } @Override public void insert(int position, String data) { super.insert(position, data); updateKeys(); } @Override public void append(String data) { super.append(data); updateKeys(); } @Override public String remove(int position) { String removed = super.remove(position); updateKeys(); return removed; } @Override public void replace(int position, String data) { super.replace(position, data); updateKeys(); } @Override public void concat(LinkedList otherList) { super.concat(otherList); updateKeys(); } /* Place Sorting Methods Here */ public void radixSort() { LinkedList[] buckets = new LinkedList[MAX_CHARACTERS]; //initialize buckets for(int i = 0; i < buckets.length; i++) { buckets[i] = new LinkedList(); } int pass = 1; for(int k = maxKeyLength - 1; k >= 0; k--) { System.out.println("Pass: " + (pass++)); System.out.println("Significant character position: " + (k + 1)); while(!isEmpty()) { String word = remove(0); int bucketIndex = alphabetPosition(word.charAt(k)); buckets[bucketIndex].append(word); } //merge buckets back into list radixRethread(buckets); } } private int alphabetPosition(char character) { if(character == ' ') return 0; if('a' <= character && character <= 'z') return character - 'a' + 1; if('A' <= character && character <= 'Z') return character - 'A' + 1; return 27; } private void radixRethread(LinkedList[] buckets) { char alpha = 'a'; //for displaying buckets for(int i = 0; i < buckets.length; i++) { concat(buckets[i]); if(i == 0) System.out.println("Bucket [\' \']: " + buckets[i].toString()); else if(i < buckets.length - 1) System.out.println("Bucket [" + (alpha++) + "]: " + buckets[i].toString()); else System.out.println("Bucket [other]: " + buckets[i].toString()); buckets[i] = new LinkedList(); } System.out.println("\nSort in progress...: " + toString() + "\n"); } } //import java.util.Random; public class Main { public static void main(String[] args) { SortableList list = new SortableList(); String[] words = {"rat", "mop", "cat", "map", "car", "top", "cot", "tar", "rap"}; for(String word : words) { list.insert(0, word); } System.out.println("Unsorted: " + list.toString() + "\n"); list.radixSort(); System.out.println("\nSorted: " + list.toString()); /*//Testing Random random = new Random(); for(int i = 0; i < 30; i++) { int position; if(list.isEmpty()) position = 0; else position = random.nextInt(list.size()); list.insert(position, "" + i); } System.out.println("List created: \n" + list.toString() + "\n"); for(int i = 0; i < 10; i++) { int index = random.nextInt(list.size()); System.out.println("Removed entry at index [" + index +"]"); list.remove(index); } System.out.println("\n" + list.toString() + "\n"); for(int i = 0; i < 5; i++) { int index = random.nextInt(list.size()); System.out.println("Retrieved entry at index [" + index + "]: " + list.retrieve(index)); } System.out.println(); for(int i = 0; i < 10; i++) { int index = random.nextInt(list.size()); String value = "" + (random.nextInt(100) + 1); System.out.println("Replaced entry value at index [" + index + "] with " + value); list.replace(index, value); } System.out.println("\n" + list.toString()); */ list.clear(); } }

RadixSort