Wednesday, June 24, 2015

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

3 comments:

  1. You are right, it is just a counting sort. Easiest one should be the 2nd of your code. I think I thought too much, made the sorting complex. Mine should be O(mn) time complexity.

    ReplyDelete
    Replies
    1. yep, you can pretty much find the solution based on the time complexity the interviewer asks for.

      Delete
    2. I also updated the blog with sorting SLL and DLL.

      Delete