Group sort

Group sort
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

http://blueocean-penn.blogspot.com/2015/06/group-sort.html
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;

}

    public static void groupSort(char[] str, char[] sequence){
        if(str==null||str.length<2||sequence==null||sequence.length<1||sequence.length > str.length){
            return;
        }
        int[] lenArr = new int[sequence.length];   //stores number of each element in sequence array
        // initilization
        HashMap chrOrder = new HashMap();   //char order
        for(int i = 0; ilength; i++){
            chrOrder.put(sequence[i], i);
            if(str[0]==sequence[i]){
                lenArr[i]++;    //initialize the chr[0]
            }
        }
        for(int i=1;ilength;i++){
            int pos = i;
            boolean found = false;
            for(int j=lenArr.length-1 ;j>0 && pos>0;j--){
                if(chrOrder.get(str[pos])>=chrOrder.get(str[pos-1])){   //compare sequence order
                    lenArr[chrOrder.get(str[pos])]++;
                    found = true;
                    break;
                }
                else{
                    // exchange element with previous one
                    char tmp = str[pos];
                    str[pos] = str[pos - lenArr[j]];
                    str[pos - lenArr[j]] = tmp;
                    pos -= lenArr[j];
                } //if
            } //for j
            if(!found){
                //case could be: BBBCCCCDDDA, when next one is A, in this way, A won't be matched in above if clause
                lenArr[chrOrder.get(str[0])]++;
            }
        } //for i
    }

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;
}
}
Read full article from Group sort