group sort

This post is responding to my friend Li Peng's page. http://allenlipeng47.com/PersonalPage/index/view/173/nkey

Given an array of string, and sequence. Sort the array according to the given sequence.
For example:
String str = "DCBAEECCAAABBAEEE"; String sequence = "ABCDE";
output should be: AAAAABBBCCCDEEEEE

The counting sort like sort algorithms are the ones can be done in O(n).

public static char[] sort(char[] strs, char[] comp){

char[] sorted = new char[strs.length];

int[] count = new int[256]; 

for(char s : strs){

count[s]++;

}

int index = 0;

for(char c : comp){

int num = count[c];

while(num-->0)

sorted[index++] = c;

}

return sorted;

}

if it is required to sort in place:

public static char[] sort(char[] strs, char[] comp){

int[] count = new int[256]; 

for(char s : strs){

count[s]++;

}

int index = 0;

for(char c : comp){

int num = count[c];

while(num-->0)

strs[index++] = c;

}

return strs;

}

Sort the Double linked list in place:

/*

* in place sort DLL of Rs, Gs and Bs, so that Rs in front, followed by Gs and Bs

* assume DLL has the sentinel node to separate the head and tail

*/

public static void sortDLL(DLL head, DLL sentinel){
final char[] setOfChars= new char[]{'R', 'G', 'B'};

DLL curr, p;
curr = p = head;

//push all R to the front

while(p != sentinel){
if(p.data == 'R'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}

 

curr = p = head.pre.pre;

//push all B to the back

while(p != sentinel){
if(p.data == 'B'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.pre;
}
p = p.pre;
}
}

How about Singled LinkedList?

//here I use DLL node to represent the SLL

//in this case DLL.pre = null

void sortSLL(DLL head){
DLL curr = head, p = head;

//push all Rs to the front

while(p != null){
if(p.data == 'R'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}

//now all Rs at front and curr points at candidate 

//position for next char which is G

//push all Gs to the front

p = curr;
while(p != null){
if(p.data == 'G'){
char t = curr.data;
curr.data = p.data;
p.data = t;
curr = curr.next;
}
p = p.next;
}
}

Convert Binary Search Tree to Sorted Doubly-linked list

This is very interesting problem. And most of solutions are recursive approach which will cause stack overflow.

The below is my solution, which does in-place and iteratively.

The idea is to in-order traverse the tree and use head pointer referencing the head of the linked list and pre pointers referencing the previous node during traverse.

public static Node isBSTAndTreeToDLL(Node root){

if(root==null)

return null;

Stack<Node> s = new Stack<Node>();

Node head = null;

Node n = root;

Node pre = null;

while(!s.isEmpty() || n!=null){

if(n!=null){

s.push(n);

n = n.left;

}

else{

Node p = s.pop();

//this is the left most node

if(head == null)

head = p;

if(pre!=null){

pre.right = p;

p.left = pre;

}

pre=p;

n = p.right;

}

}

//handle the last node

pre.right = head;

head.left = pre;

return head;

}