String trim(String s) {
if (s.length() ==0) return s;
if (s.charAt(0) == ' ') return trim(s.substring(1,s.length()));
if (s.charAt(s.length()-1) ==' ') return trim(s.substring(0,s.length()-1));
return s; }
package project;
public class QuickSort {
Comparable theArray[];
public void sort(Comparable theArray[]) {
this.theArray = theArray;
sort_recursive(0, theArray.length - 1);
}
private void sort_recursive(int partition_start, int partition_end) {
if (partition_start == partition_end) {
return; //base case , it the sub array length is zero, then sorted
}
int pivotLocation = partition(partition_start, partition_end); //use the partition algorythm to find pivot location
if (pivotLocation != partition_start) { //if the pivot is not the smallest value
sort_recursive(partition_start, pivotLocation - 1); //then quick sort the values before the partition
}
if (pivotLocation != partition_end) { //if the pivot is not the largest value
sort_recursive(pivotLocation + 1, partition_end); //then quick sort the values after the partition
}
}
//partition algorythm
private int partition(int bottom, int top) {
int down = bottom;
int up = top;
Comparable pivot = theArray[bottom];
while (true) {
while (!(theArray[down].compareTo(pivot) > 0)) {
down++; // increase down pointer untill a value greater than pivot value is found
if (down == top) {
break; //the boundry conditions of the partition
}
}
while (!(theArray[up].compareTo(pivot) <= 0)) {
up--; // decrease up pointer untill a value less than or equal to pivot value is found
if (up == bottom) {
break;//the boundry conditions of the partition
}
}
if (up > down) {
Swapper.swap(theArray, up, down); //if up is greater than down then swap the up position value and down position value
} else {
Swapper.swap(theArray, up, bottom); //else then swap the up position value and pivot position value, here the pivot is selected as the first element in the sub array
return up; //pivot location is found, which is the up position
}
}
}
}
package project;
//Swaps the values of two locations in a specific Array
public class Swapper {
public static void swap(Comparable[] theArray, int position1, int position2) {
Comparable temp = theArray[position1];
theArray[position1] = theArray[position2];
theArray[position2] = temp;
}
}
package project;
public class ShellSort {
Comparable theArray[];
int length;
public void sort(Comparable theArray[]) {
this.theArray = theArray;
length = theArray.length;
shell_sort();
}
private void shell_sort() {
int gap = length / 2;
while (true) {
for (int i = length - 1; i > i - gap && i > -1; i--) { //visit each element within one gap length from the last position , and check if one gap length is more than the array size
for (int j = i; j - gap > -1; j = j - gap) { //visit each element one gap length apart from each other.
if (theArray[j - gap].compareTo(theArray[j]) > 0) { //comapare the two elements which are one gap length apart from each other
Swapper.swap(theArray, j, j - gap); // if the left element is greater than the right element then swap the left and right elemnts
}
}
}
if (gap == 1) {
return; //if gap length is one then the array is sorted
}
gap = gap / 2; //reduce the gap size by half and repeat the above insertion sort
}
}
}
package project;
//Swaps the values of two locations in a specific Array
public class Swapper {
public static void swap(Comparable[] theArray, int position1, int position2) {
Comparable temp = theArray[position1];
theArray[position1] = theArray[position2];
theArray[position2] = temp;
}
}
package project;
public class RadixSort {
String theArray[];
int maxLength = 0;
public char[] sort(char c[]) {
toBinary(c);
padZeros();
radixSort();
for (int j = 0; j < theArray.length; j++) {
int b = Integer.parseInt(theArray[j], 2);
c[j] = (char) b;
}
return c;
}
public int[] sort(int c[]) {
toBinary(c);
padZeros();
radixSort();
for (int j = 0; j < theArray.length; j++) {
c[j] = Integer.parseInt(theArray[j], 2);
}
return c;
}
private void toBinary(char x[]) { //convertion to binary
theArray = new String[x.length];
for (int i = 0; i < x.length; i++) {
theArray[i] = Integer.toBinaryString(x[i]);
}
}
private void toBinary(int x[]) { //convertion to binary
theArray = new String[x.length];
for (int i = 0; i < x.length; i++) {
theArray[i] = Integer.toBinaryString(x[i]);
}
}
//radix sort done using stright radix sort
private void radixSort() {
bit_evaluvation:
for (int bit = theArray[0].length() - 1; bit > -1; bit--) {
int zero, one = 0;
//find the first occurence of one, upto that point it has zeros
while (theArray[one].charAt(bit) != '1') {
one++;
if (one == theArray.length) {
continue bit_evaluvation; //All zeros no need to process this bit
}
}
while (true) {
//find the next occurence of zero
zero = one;
while (theArray[zero].charAt(bit) != '0') {
zero++;
if (zero == theArray.length) {
continue bit_evaluvation;// if it cannnot find a zero then evaluvation for this bit is finished
}
}
//shift array elemets from i to zero position by one element and copy the zero position value to the i position
String tmp = theArray[zero];
int j = zero;
while (j - 1 >= one) {
theArray[j] = theArray[--j];
}
theArray[one] = tmp;
one++; //go to next position, which is a one and repeat the above operation
if (one == theArray.length) {
continue bit_evaluvation;// if it cannnot find a next one then evaluvation for this bit is finished
}
}
}
}
private void padZeros() { //fill zeros to the front so that all binary strings are of equal length
for (String s : theArray) {
if (s.length() > maxLength) {
maxLength = s.length();
}
}
for (int j = 0; j < theArray.length; j++) {
theArray[j] = String.format("%0" + maxLength + "d", Long.parseLong(theArray[j]));
}
}
}
package project;
public class HeapSort {
Comparable theArray[];
int length;
public void sort(Comparable theArray[]) {
this.theArray = theArray;
length = theArray.length;
bulidHeap(); //build the heap using the supplied array
sortHeap(); //sort the created heap
}
private void bulidHeap() {
for (int i = (length / 2) - 1; i > -1; i--) { //The second half of the array are leaf nodes, thus we will consider only the first half
downHeap(i); //ensure heap condition is valid for each node which is a parent
}
}
private void downHeap(int parent) {
int greater = parent; //Assume the parent is greater than both the children
while (true) {
//find the index of the left child
int left_child = parent * 2 + 1;
//if there is no left child,then the heap condition is valid
if (left_child >= length) {
return;
}
//find if the left child has a greater value
if (theArray[left_child].compareTo(theArray[parent]) > 0) {
greater = left_child;
}
//find if a right child also exisits which is greater than the left child
if (left_child + 1 < length && theArray[left_child + 1].compareTo(theArray[left_child]) > 0) {
greater = left_child + 1; //left_child+1 = right child's position
}
//if the parent is greater than both the children,then the heap condition is valid
if (parent == greater) {
return;
}
//swap the greater child with the parent
Swapper.swap(theArray, parent, greater);
//Consider the parents new location and evaluvate its heap condition with respect to its new children
parent = greater;
}
}
private void sortHeap() {
while (length != 1) { //do untill only one node remains unsorted, which will be the smallest node
Swapper.swap(theArray, 0, --length); //reduce the unsorted length by 1 and the swap the node at the last unsorted position with the root
downHeap(0);//ensure the heap condition for the new root value
}
}
}
package project;
//Swaps the values of two locations in a specific Array
public class Swapper {
public static void swap(Comparable[] theArray, int position1, int position2) {
Comparable temp = theArray[position1];
theArray[position1] = theArray[position2];
theArray[position2] = temp;
}
}
public class ListNode {
Object element;
ListNode next;
public ListNode(Object x, ListNode n) {
element = x;
next = n;
}
public ListNode(Object x) {
this(x, null);
}
}
/* Linked list based Stack implementation */
public class StackUsingLinkedList {
private ListNode tosNode; // The node which represents the top of the Stack
public StackUsingLinkedList() { // Creates a stack with no nodes
tosNode = null;
}
public boolean isEmpty() { // Checks if the Stack is empty
return (tosNode == null);
}
public void makeEmpty() { // Empty the Stack by removing linked nodes
tosNode = null;
}
public void push(Object x) { // Create new node and add the data, point to tos node, and make new tos
tosNode = new ListNode(x, tosNode);
}
public void pop() throws Exception {
if (isEmpty()) { //Check if empty before pop
throw new Exception("The Stack is empty: Stack pop");
}
tosNode = tosNode.next; //make the new tos point tos next of current tos
}
public Object top() throws Exception {
if (isEmpty()) { //Check if empty before top
throw new Exception("The Stack is empty: Stack top");
}
return tosNode.element; //return the element
}
public Object topAndPop() throws Exception {
Object returnValue = top(); //keep the top node's value
pop(); // pop and remove the top node
return returnValue; // return the top node's value
}
}
public class PostfixConverter {
/* References
* http://scriptasylum.com/tutorials/infix_postfix/algorithms/infix-postfix/index.htm
* http://www.cis.temple.edu/~koffman/cis223/InfixToPostfix.doc
*/
public String convertPostfix(String x) throws Exception {
String postfixString = ""; //Set postfix string to empty string
StackUsingLinkedList operatorStack = new StackUsingLinkedList(); //Create an empty operator stack
for (int i = 0; i < x.length(); i++) { //Repeat unitll end of the string
char c = x.charAt(i); //Get the next token in the infix string
if ((!(Character.isDigit(c)) && !(Character.isLetter(c))) && !(c == ('+') || c == ('*') || c == ('-') || c == ('/') || c == ('(') || c == (')')) || (c == ' ')) {
continue; //Used to avoid spaces and invalid characters, + - * / are not digits or characters
}
if (!(c == ('+') || c == ('*') || c == ('-') || c == ('/') || c == ('(') || c == (')'))) //If next token is an operand (begins with digit)
{
postfixString += c; //append it to postfix string
} else {
while (true) { // Repeat until the next op is pushed onto the stack.
//If operator stack is empty or next op is ‘(‘, push next operator onto stack
if (operatorStack.isEmpty() || c == '(') {
operatorStack.push(c);
break; //the operator is pushed on to the stack, no need for further processing c
}
//Else if precedence of this operator is greater than one on top of the stack then push to stack
else if (precedence(c) > precedence(operatorStack.top())) {
operatorStack.push(c);
break; //the operator is pushed on to the stack, no need for further processing c
}
else {
//For the case of brackets ---------------------------------
if (c == ')') {
while (!(operatorStack.top().toString().equals("("))) { //Pop and append until the opening bracket is reached
postfixString += operatorStack.topAndPop();
}
operatorStack.pop(); //remove the opening bracket, no need for it
break;
}
//End of case for brackets--------------------------------
//Then this operator has lower precedence, then top and pop the stack untill all higher operators are appened to the string
postfixString += operatorStack.topAndPop();
}
}
}
}
//At end of string, keep popping stack until stack is empty
while (!operatorStack.isEmpty()) {
postfixString += operatorStack.topAndPop();
}
//Finally return the postfix String
return postfixString;
}
// The method checks the precedence of each operator
private int precedence(Object x) {
if (x.toString().equals("*") || x.toString().equals("/")) {
return 2;
} else if (x.toString().equals("+") || x.toString().equals("-")) {
return 1;
} else {
return 0;
}
}
}
public class ExpressionEvaluator {
StackUsingLinkedList operandStack;
PostfixConverter pc;
public ExpressionEvaluator() {
operandStack = new StackUsingLinkedList(); //A stack to keep operands
pc = new PostfixConverter(); //Used for converting to postfix
}
public int evaluate(String x) throws Exception {
String postfixInput = pc.convertPostfix(x); //First convert to postfix
int result = 0; // Initially the output is zero
for (int i = 0; i < postfixInput.length(); i++) {
char c = postfixInput.charAt(i);
if (!(c == ('+') || c == ('*') || c == ('-') || c == ('/'))) {
operandStack.push(c); //If a operand then add to stack
} else { // If operator, then pop twice and calculate
int b = Integer.parseInt(operandStack.topAndPop().toString());
int a = Integer.parseInt(operandStack.topAndPop().toString());
result = compute(a, b, c);
operandStack.push(result); //Push the result in to the stack for further calculations
}
}
return result; //Return the calculated value
}
private int compute(int a, int b, Character op) { // Used for mapping String characters to numerical operators
if (op == '*') {
return a * b;
}
if (op == '/') {
return a / b;
}
if (op == '+') {
return a + b;
}
if (op == '-') {
return a - b;
} else {
return 0;
}
}
}
public class LinkedList {
public ListNode header;
public LinkedList() {
header = new ListNode(null); //Creates a header node with null data
}
//(i)
public LinkedList concatenate(LinkedList secondList) {
LinkedList combinedList = new LinkedList(); // Creates a new empty list which will store the combained two list's values
LinkedList setOfLists[] = {this, secondList}; //Need to combaine this list and the secondList
for (int i = 0; i < setOfLists.length; i++) { //Do for both lists (this and secondList)
if (!(setOfLists[i].isEmpty())) { //To check if there is a header.next position
ListNode current = setOfLists[i].header.next; //Goto the very first node in the list
while (true) { //Used to do until the end of the list is reached
combinedList.insertAtEnd(current.element);// Copy the element value to the combained List
current = current.next;// Move to the next node
if (current == null) {
break;//Reached end of list, break the while loop and move on to next list
}
}
}
}
return combinedList; //Finally return the combinedList which contains both the lists contents
}
//(ii)
public void insertAtEnd(Object newData) {
ListNode current = header; //Start from header
while (null != current.next) { //Used To visit the last node in the List
current = current.next;// Move to the next node
}
current.next = new ListNode(newData, null); //Insert the new node to the end of the list
}
//(iii)
public void removeAtPosition(int position) {
ListNode current = header;
for (int i = 0; i < position; i++) { //Used to navigated to the position just before the deletion position
if (current.next == null) {
return;//The searched position is not found, terminate processing
}
current = current.next;// Move to the next node
}
current.next = current.next.next; //The deletion process
}
//(iv)
public LinkedList sort() throws Exception {
//Uses te Quicksort alogrythm to quicksort the List
//Referenced from: http://en.wikipedia.org/wiki/quicksort#Algorithm
if (isEmpty()) {
throw new Exception("Exception in Sort, The list empty");
}
return quicksort(this); //Sort this list and return
}
//The quicksort function which is used recursively
public LinkedList quicksort(LinkedList x) {
if (x.header.next.next == null) //The base case of the recursion are lists of size of one, which are always sorted.
{
return x; //Since it is sorted return it
}
LinkedList less = new LinkedList(); //To store values less than pivot value
LinkedList greater = new LinkedList(); //To store values greater than pivot value
Object pivot = x.header.next.element; //select a pivot value which is the value compared against
double pivotDouble = Double.parseDouble(pivot.toString()); //Conversion to Double of the pivot value
ListNode current = x.header.next; //Start from the first node
while (current != null) { // Do until the end of the list
double currentDouble = Double.parseDouble(current.element.toString()); //Conversion to Double to the current value
if (currentDouble < pivotDouble) {
less.insertAtEnd(current.element); //If less than pivot then insert to the "less list"
} else if (currentDouble > pivotDouble) {
greater.insertAtEnd(current.element); //If greater than pivot then insert to the "greater list"
}
current = current.next; //Go to the next node
}
if (!less.isEmpty()) { //If empty nothing to sort
less = quicksort(less); //Sorts the list which having elements having value less than the pivot value, recursively
}
if (!greater.isEmpty()) { //If empty nothing to sort
greater = quicksort(greater); //Sorts the list which having elements having value less than the pivot value, recursively
}
less.insertAtEnd(pivot); //Append the pivot value to end of the sorted less list
return less.concatenate(greater); //Concatenate the "sorted less list" and "sorted greater list" and return the sorted list
}
/*
*
*
* ----------------------General List Operations----------------------------------------------------------
*
*
*/
//Will return true if List is empty
public boolean isEmpty() {
return header.next == null;
}
//Will Return a String Containing all the values stored in the List
public String printList() {
String contents = "";
if (isEmpty()) {
return "List Empty";
}
ListNode current = header.next;
while (true) {
contents += current.element.toString() + "\n";
current = current.next;
if (current == null) {
break;//End of list reached,terminate processing
}
}
return contents;
}
// Will insert a node on to the header position
public void insertBeginning(Object newData) {
header.next = new ListNode(newData, header.next);
}
// Will insert a node after the node having specific position data
public void insertAfter(Object newData, Object positionData) {
ListNode current = header;
while (positionData != current.element) {
current = current.next;
}
if (current == null) {
return; //The searched position is not found, terminate processing
}
current.next = new ListNode(newData, current.next);
}
// Will remove the node after the node having specific position data
public void removeAfter(Object positionData) {
ListNode current = header;
while (positionData != current.element) {
current = current.next;
}
if (current == null) {
return;//The searched position is not found, terminate processing
}
current.next = current.next.next;
}
}