Sort an array of strings based on length

Question

The question is to sort an array of Strings, based on the length of the strings.

For example

input = {"cat", "star", "act", "gid", "arts", "dog", "rats"}  
output = {"cat", "act", "gid", "dog", "star", "arts", "rats"}

I did it using Insertion sort(using the length of the strings instead of the strings themselves). My question:is there a better way to do it?

An alternative I thought of is - use a TreeMap to store each string and its length as value (assume the strings are unique in the given array). Then sort it based on its values. The running time would be O(nlogn) and space complexity would be O(n). Do you think this is a better approach?

EDIT: Sorry for not mentioning this earlier - I want to do this without using Arrays.sort() or a custom comparator.

Code sample for insertion sort:

public static String[] insertionSort(String[] arr) {
    for(int i=1;i<arr.length;i++) {
        int j = 0;
        for(;j<i;j++) {
            if(arr[j].length() > arr[j+1].length()) {
                String temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
    return arr;
}

Solution 1

There are a number of better ways to do it. For insertion sort, we're talking O (n^2). A much better sorting algorithm would be something like mergesort (better worst-case) or quicksort (better on average). Since this is a length-based sort, there are a number of approaches that can be taken. You are going to have to calculate the length of each string at some point. What you could do is create an array of ints that correspond to the lengths of the words at the same respective index. Then you can run mergesort or quicksort on the ints and be sure to flip the strings around at the same time. The end result would be a non-decreasing array of ints and a non-decreasing array of strings.

Solution 2

Try this one.

Your input

String[] input = {"cat", "star", "act", "gid", "arts", "dog", "rats"};

Your Comparator

class SampleComparator implements Comparator<String> {
    @Override
    public int compare(String o1, String o2) {
        return new Integer(o1.length()).compareTo(o2.length());
   }
}

Your Sorting

Collections.sort(in, new SampleComparator());

Your output

output = {"cat", "act", "gid", "dog", "star", "arts", "rats"}

Solution 3

    String[] str={"umbrella","apple", "baby", "cat","rat","obnoxious"};
    Arrays.sort(str, new Comparator<String>() {

        @Override
        public int compare(String o1, String o2) {
            return o1.length()-o2.length();
        }
    });

Comments

[Jayamohan]

Your snippet compiles?