CareerCup

use a hash table, the key is sorted string, and all the string combined by these character is in one block. for example hashtable[abc]={abc,cab}, hashtable[dgo]={dog,god}.
And then sort it by the order of the first character of each key.

write the sort compare criteria of two strings (str1, str2) as bellow
1> build two arrays p1[256], p2[256], set to zero in the begging.
2> for each character c in str1, let p1[a]++
3> for each character d in str2, let p2[d]++;
4> check count from 1 to 255,
4.1> if p1[count]>p2[count],
4.1.1> If there exist one count2 >count that p2[count2]>0 , then str1 < str2,
for case str1="aaaacdefdg", str2="aaab"
4.1.2> if for all count2 >count, p2[count2]=0 then str1>str2
for case str1="aaaacdefdg", str2="aaa"
4.2> if p1[count]<p2[count]:
4.2.1> if there is count2 >count, p1[count2]>0, then str1>str2
symmetric as 4.1.1.
4.2.2> if for all count2> count, p1[count2]=0, then str1<str2
symmetric as 4.1.2.
5> if all p[count]=0, then using strcmp to find which str is bigger.

then people could use the quick sort to perform the sorting, by copying the str address but not the whole string while doing the swapping.

Concatenate sorted string and original string. Then sort
god->dgogod
dog->dgodog

Just override the comparator.. that should do it..
This works in Java. For other's I don't know.

Just need to keep track the min element for each anagrams set in order to compare correctly.

for (String str : array) {
            String sort = sort(str);
            String list = anagrams.get(sort);
            if (list == null || list.compareTo(str) > 0) {
                anagrams.put(sort, str);
            }
        }
        
        Arrays.sort(array, new Comparator<String>() {

            @Override
            public int compare(String o1, String o2) {                
                String sort1 = sort(o1);
                String sort2 = sort(o2);
                return anagrams.get(sort1).compareTo(anagrams.get(sort2));
            }
        });

def radixsort(array):
    maxlen = len(max(array,key = lambda x: len(x)))
    i = maxlen - 1
    while i >= 0:
        array = sorted(array,key=lambda x:x[i] if i < len(x) else 0)
        i -= 1
    return array

// first pass
insert all strings into a hash table, key = string, value = sorted key

now call bubble sort or any other sort with following a Compare function which compares first the value of the string and then then key if needed.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class wordSequence {
	/**
	 * @author: Amarkant kumar ,DUCS
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		String[] data = {"cat","dog","act","god","tac"}; 
		processData(data);
	}

	private static void processData(String[] data) {
		
		Map<Integer,List<String>> obj = new HashMap<>();
		for(int i=0;i<data.length;i++)
		{
			int a=0;
			String s = data[i];
			for(int j=0;j<s.length();j++)
			{
				a+=(int)s.charAt(j);
			}
			
			if(obj.size()==0)
			{
				obj.put(a, new ArrayList<String>());
				obj.get(a).add(data[i]);
			}
			else
			{
				if(obj.get(a) == null)
				{
					obj.put(a, new ArrayList<String>());
					obj.get(a).add(data[i]);
				}
				else
				{
					obj.get(a).add(data[i]);
				}
			}	
		}
		System.out.println(obj.values());
		
	}
}

/*
 * Output: [[cat, act, tac], [dog, god]]
 * 
 * */

Python Solution Using Key Function:

def anagram_sort(lst):
    return sorted(lst, key=lambda elem: (sorted(elem), elem))

lst = ['god', 'dog', 'abc', 'cab', 'man']
assert anagram_sort(lst) == ['abc', 'cab', 'man', 'dog', 'god']

def sort_words(a)
  swapped = true
  while swapped
  	swapped = false
  	0.upto(a.size - 2) do |i|
  	  if a[i][0] > a[i+1][0]
  	  	a[i], a[i+1] = a[i+1], a[i]
  	  	swapped = true
  	  end
  	end
  end
  a
end

import java.util.*;

public class SortAnagramsNext {

   public static List<String> sortWithAnagramsTogether(List<String> elements) {
      List<String> sortedElements = sort(elements);
      Map<String, List<String>> anagramMap = new LinkedHashMap<String, List<String>>();
      for (String element : sortedElements) {
         String sortedElement = sortChars(element);
         if (anagramMap.get(sortedElement) == null) {
            anagramMap.put(sortedElement, new ArrayList<String>());
         }
         anagramMap.get(sortedElement).add(element);
      }
      Map<String, List<String>> tmpMap = new LinkedHashMap<String, List<String>>();
      for (String key : anagramMap.keySet()) {
         tmpMap.put(anagramMap.get(key).get(0), anagramMap.get(key));
      }
      anagramMap = tmpMap;
      List<String> sortedWithAnagrams = new ArrayList<String>();
      List<String> mapKeys = new ArrayList<String>(anagramMap.keySet());
      Collections.sort(mapKeys);
      for (String mapKey : mapKeys) {
         for (String element : anagramMap.get(mapKey)) {
            sortedWithAnagrams.add(element);
         }
      }
      return sortedWithAnagrams;
   }

   public static String sortChars(String str) {
      char[] strChars = str.toCharArray();
      Arrays.sort(strChars);
      return String.valueOf(strChars);
   }

   public static List<String> sort(List<String> elements) {
      List<String> sortedElements = new ArrayList<String>(elements);
      Collections.sort(sortedElements);
      return sortedElements;
   }

   public static void main(String[] args) {
      List<String> elements = Arrays.asList("god", "dog", "abc", "cab", "man");
      List<String> sortedElements = sortWithAnagramsTogether(elements);
      System.out.println(sortedElements);
   }

}

private static String sortString(String x)
	{
		char[] ar = x.toCharArray();
		Arrays.sort(ar);
		String sorted = String.valueOf(ar);
		
		return sorted;
	}
	
	static String[] q5(String[] x)
	{
		HashMap<String,ArrayList<String>> y=new HashMap<String,ArrayList<String>>();
		
		for(int i=0;i<x.length;i++)
		{
			if (!y.containsKey(sortString(x[i])))
				y.put(sortString(x[i]), new ArrayList<String>());
			y.get(sortString(x[i])).add(x[i]);
		}
		
		int count=0;
		String[] result=new String[x.length];
		
		for (ArrayList<String> z:y.values())
		{
			for (String a:z)
			{
				result[count++]=a;
			}
		}
		return result;
	}

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;
bool compare_anagram (string first, string second)
{
  sort(first.begin(), first.end());
  sort(second.begin(), second.end());
  return (first < second);
}
int main() {
	list<string> inputList = {"agodz", "zadog", "abc", "az", "za","cab", "man"};
	inputList.sort(compare_anagram);
//	inputList.sort();
	for(list<string>::iterator it = inputList.begin(); it != inputList.end(); ++it) {
		cout << endl << *it;
	}
	return 0;
}

Hi I'm getting anagrams sorted. But the overall alphabetical sorting isn't happening

package onlineTest;

import java.util.*;

/**
 *
 * @author Sushil
 */
class Anagram implements Comparator<String>
{
    public int compare(String s,String s2)
    {
        char[] sChar1=s.toCharArray();
        char[] sChar2=s2.toCharArray();
        Arrays.sort(sChar1);
        Arrays.sort(sChar2);
        s=String.valueOf(sChar1);
        s2=String.valueOf(sChar2);
        return s.compareTo(s2);

        
        
    }
    
}
public class AnagramSort {
public static void main(String[] args)
    {
        args=new String[]{"god","dog","abc","cab","cba","dgo","malya","yalam"};
        Arrays.sort(args);
        Arrays.sort(args,new Anagram());
        for(String args1:args)
        System.out.println(args1);
}

}

#include <vector>
#include <map>
#include <string>
#include <algorithm>

typedef std::map<std::string, std::string> AnagramStringMap;
typedef AnagramStringMap::iterator AnagramStringMapIter;
typedef std::vector<std::string> StringVector;
typedef StringVector::iterator StringVectorIter;

void AnagramSort(StringVector& vInput)
{
    std::sort(vInput.begin(), vInput.end());                // sort with complexity n * log(n)
    AnagramStringMap anagramMap;
    for (StringVectorIter it = vInput.begin(); it != vInput.end(); ++it)
    {
        std::string s(it->rbegin(), it->rend());            // anagram of current string
        AnagramStringMapIter mapIt = anagramMap.find(s);    // find it in map (log(n))
        if (mapIt != anagramMap.end())
            mapIt->second = *it;                            // if already exists set current string as value
        else
            anagramMap.insert(std::make_pair(*it, ""));     // else insert it as a new key (log(n))
    }
    AnagramStringMapIter mapIt = anagramMap.begin();
    StringVectorIter it = vInput.begin();
    for (; mapIt != anagramMap.end(); ++mapIt, ++it)
    {
        *it = mapIt->first;                                 // copy value to array
        if (!mapIt->second.empty())                         // if word has anagram then copy it to the next index
        {
            ++it;
            *it = mapIt->second;
        }
    }
}

public static void main(String args[])
{
String []a = {"god", "dog", "abc", "cba", "man","nam"};
Map<String, String> b = new TreeMap<String, String>();
for (int i=0;i<a.length;i++)
{
b.put(a[i], a[i]);
}

for (Entry<String, String> e : b.entrySet())
{
System.out.println(e.getValue());
}
}

public static void main(String args[])
{
String []a = {"god", "dog", "abc", "cba", "man","nam"};
Map<String, String> b = new TreeMap<String, String>();
for (int i=0;i<a.length;i++)
{
b.put(a[i], a[i]);
}

for (Entry<String, String> e : b.entrySet())
{
System.out.println(e.getValue());
}
}

Short and Sweet:

import java.util.Arrays;
import java.util.Comparator;

public class StrAnaSort {

public static void main(String[] args)
{
String[] strArr = {"god","dog", "abc", "cab", "man"};
Arrays.sort(strArr, new AnagramComparator());
for(String str:strArr)
{
System.out.print(str+" ");
}
}
}

class AnagramComparator implements Comparator<String>
{

@Override
public int compare(String str1, String str2)
{
return sumLetters(str1)-sumLetters(str2);
}

private int sumLetters(String str)
{
int sum = 0;
for(int ch:str.toCharArray())
{
sum+=ch;
}
return sum;
}

}

#include <algorithm>
#include <string>
#include <vector>

using namespace std;

void anagram_sort(vector<string>& words) {
    sort(begin(words), end(words), [](const string& x, const string& y)
    {
        if (x.length() != y.length())
            return x.length() < y.length();
        else {
            string xx(x), yy(y);
            sort(begin(xx), end(xx));
            sort(begin(yy), end(yy));
            return xx < yy;
        }
    });
}

package string;
import java.util.*;
import java.lang.StringBuffer;
import java.util.Arrays;

public class WordSequence {
public HashMap<String,Integer> check=new HashMap<String,Integer>();
public HashMap<String,String> store=new HashMap<String,String>();
public void storeInHashMap(String[] str){
for(String st:str){
check.put(st, 1);
}
for(String st:str){
String reverse=new StringBuffer(st).reverse().toString();
if(check.containsKey(reverse)){
if(st.compareTo(reverse)<0){
store.put(st, st+","+reverse);
}else{
store.put(reverse, reverse+","+st);
}
}else{
store.put(st, st);
}

}
sortWord();
}
public void sortWord(){
String[] str= (String[]) store.keySet().toArray(new String[0]);
Arrays.sort(str);
for(String st:str){
System.out.println(store.get(st));
}
}
public static void main(String[] args){
String[] data = {"cat","dog","act","god","tac"};
new WordSequence().storeInHashMap(data);
}
}

First, group the anagrams by sorting the letters of each word, and using the word that these sorted letters form as a key for a dictionary.
For example, groups['abc'] = ['abc', 'cab']
Then, take the first word from each of these lists, sort them, then insert the other anagrams accordingly.

def anagrams_sort(words):
    groups = {}
    for word in words:
        anagram_key = ''.join(sorted(list(word)))
        if anagram_key in groups:
            groups[anagram_key].append(word)
        else:
            groups[anagram_key] = [word]
    
    keys = {}
    first_anagrams = []
    for key in groups.iterkeys():
        groups[key] = sorted(groups[key])
        keys[groups[key][0]] = key
        first_anagrams.append(groups[key][0])
    
    return [word for x in first_anagrams for word in groups[keys[x]]]

I keep a hash with the sorted word as key.To sort a word i use an array of 26 elements, each representing a letter.

def sort_anagrams(words = []):
    dict_words, sorted_words = {}, []
    for word in words:
        letters = [0] * 26
        for letter in word:
            letters[ord(letter) - 97] += 1
            
        new_word = ''
        for key, value in enumerate(letters):
            new_word += chr(key + 97) * value

        try:
            dict_words[new_word].append(word)
        except KeyError:
            dict_words[new_word] = [word]
        
    for words in dict_words.values():
        for word in words:
            sorted_words.append(word)

    return sorted_words

package gao.zone.study;

import java.util.Arrays;

public class AnagramsSort {

	public static void main(String[] args) {
		String[] input = { "god", "dog", "abc", "cab", "man"};
		String[] expected = {"abc", "cab", "dog", "god", "man"};
		sort(input);
		System.out.println(Arrays.toString(input));
		if(!Arrays.equals(input, expected)) {
			throw new AssertionError();
		}
	}

	private static void sort(String[] input) {
		for (int i = 0; i < input.length - 1; i++) {
			// put correct value to index i
			for (int j = i + 1; j < input.length; j++) {
				if (input[i].compareTo(input[j]) > 0) {
					swap(input, i, j);
				}
			}
			// place anagrams follow index i
			int anagramCount = 0;
			char[] anagramKey = toAnagramKey(input[i]);
			for (int j = i + 1; j < input.length; j++) {
				if (isAnagram(anagramKey, input[j])) {
					anagramCount++;
					swap(input, i + anagramCount, j);
				}
			}
			if (anagramCount > 0) {
				Arrays.sort(input, i + 1, i + anagramCount + 1);
				i += anagramCount;
			}
		}
	}

	private static boolean isAnagram(char[] anagramKey, String string) {
		if (string.length() != anagramKey.length) {
			return false;
		}
		return Arrays.equals(toAnagramKey(string), anagramKey);
	}

	private static char[] toAnagramKey(String string) {
		char[] arr = string.toCharArray();
		Arrays.sort(arr);
		return arr;
	}

	private static void swap(String[] input, int i, int j) {
		String temp = input[i];
		input[i] = input[j];
		input[j] = temp;
	}

}

public class CompareList {
	
	public static void main(String[] args) {
		String[] unsortList = {"god","dog", "abc", "cab", "man"};
 
		//before sort
		System.out.println("ArrayList is unsort");
		for(String temp: unsortList){
			System.out.println(temp);
		}
 
		for(int i=0; i<unsortList.length; i++) {
			
			for(int j=1; j<unsortList.length-i; j++) {
				
				if(unsortList[j-1].compareTo(unsortList[j]) > 0) {
					String temp = unsortList[j-1];
					unsortList[j-1] = unsortList[j];
					unsortList[j] = temp;
				}
			}
			
		}
		
		//after sorted
		System.out.println("ArrayList is sorted");
		for(String temp: unsortList){
			System.out.println(temp);
		}
		
	}
	
}

#include <iostream>
#include <vector>
#include <string>
#include <map>

using namespace std;

string MakeKey(string s)
{
    sort(s.begin(), s.end());
    return s;
}

int
main()
{
    map<string, vector<string>> anagrams;
    for(string input; cin >> input; )
    {
        auto key = MakeKey(input);
        anagrams[key].push_back(input);
    }

    for(auto &mi:anagrams)
    {
        for(auto &vi:mi.second)
        {
            cout << vi << " ";
        }
    }
    cout << endl;

    return 0;
}

So the key would essentially be the ascii value of the string

i.e

Initially:
arr = [cat, tac, pig, .... ]
hashmap = empty

Taking string out of array:
String tmp = cat

After hash map checks:
hashmap = [{ASCII VALUE} => {cat}]

Completed hash map:
hashmap = [{ASCII VALUE} => {cat, tac}, {ASCII VALUE} => {pig}, ... ]

Then iterate through hashmap and place value pairs in new array while sorting along the way.

why we are not using

Collections.sort(arrrayListOfString) ;

for java? as this is will sort on ascii code.