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;
}
}