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

I think expected code will be O(n) for both time and space as there is no need to order elements, just initial pass of bucket sort. — Alexei Levenkov
– Alexei Levenkov, Commented Oct 26, 2013 at 5:32
@AlexeiLevenkov: Do I do this using a 2 dimensional string array for the bucket? — codewarrior
– codewarrior, Commented Oct 26, 2013 at 22:41
I'm not sure what your goal/language is: I'd have map of length to list of strings with that length and fill it out on first iteration, than simply copy all lists together in order. If you know that length of the strings is limited you can use just array or arrays and use first index as key for length, otherwise you'll need to build/use hashtable to get O(1) to add each string to correct sub-array. — Alexei Levenkov
– Alexei Levenkov, Commented Oct 26, 2013 at 23:02
@AlexeiLevenkov: Let's assume that I don't know anything about the max/min length of the strings. Assuming my language is Java, your approach seems to be the alternate approach I've given in my question, right? — codewarrior
– codewarrior, Commented Oct 27, 2013 at 3:32
Yes, it somewhat different, but my runtime estimate was wrong - if maximum length is not known you'd still have to sort resulting array of length... So your red-black tree approach is as good as my HashMap suggestion. — Alexei Levenkov
– Alexei Levenkov, Commented Oct 27, 2013 at 19:23

Prabhakaran Ramaswamy · Accepted Answer · 2013-10-26 05:42:20Z

5

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

answered Oct 26, 2013 at 5:42

Prabhakaran Ramaswamy

26.1k10 gold badges61 silver badges65 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Trying · Accepted Answer · 2013-10-26 05:46:00Z

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

answered Oct 26, 2013 at 5:46

Trying

14.3k11 gold badges72 silver badges113 bronze badges

Comments

Don · Accepted Answer · 2013-10-26 05:35:44Z

2

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.

answered Oct 26, 2013 at 5:35

Don

876 bronze badges

Comments

Aman Gautam · Accepted Answer · 2013-10-26 05:42:30Z

0

If you can use a Collection instead (e.g an ArrayList will be great in your case), you can use Collections.sort to do the work for you. It's fast and clean. See: java.util.List

You will need a custom comparator.

public class StringComparator implements Comparator<String>
{
    @Override
    public int compare(String s1, String s2) 
    {
        return s1.length()-s2.length();
    }
}

edited Oct 26, 2013 at 5:42

answered Oct 26, 2013 at 5:34

Aman Gautam

3,5912 gold badges23 silver badges25 bronze badges

1 Comment

Jayamohan Over a year ago

Your snippet compiles?

Wagner DosAnjos · Accepted Answer · 2013-10-26 05:44:56Z

0

You can use a Comparator as following:

public static class OrderStringByLength implements Comparator<String> {
    @Override
    public int compare(String s1, String s2) {
        int c = s1.length() - s2.length();
        return (c != 0) ? c : s1.compareTo(s2);
    }
}

Then you can sort the array as follows:

Arrays.sort(input, new OrderStringByLength());

answered Oct 26, 2013 at 5:44

Wagner DosAnjos

6,3841 gold badge18 silver badges30 bronze badges

Comments

SanA · Accepted Answer · 2016-03-19 05:41:38Z

public class SortArrayOfStringOnLength {

public static void main(String[] args) {
    String[] strArray = new String[] { "cat", "star", "act", "gid", "arts",
            "dog", "rats" };

    printArray(strArray);

    String[] outputArray = getSortedArray(strArray);
    printArray(outputArray);

}

private static String[] getSortedArray(String[] strArray) {

    Map map = new TreeMap();
    for (int i = 0; i < strArray.length; i++) {
        String str = strArray[i];
        if (map.containsKey(str.length())) {
            List list = (List) map.get(str.length());
            list.add(str);
            map.put(str.length(), list);
        } else {
            List list = new ArrayList();
            list.add(str);
            map.put(str.length(), list);
        }
    }

    Set set = map.keySet();

    Iterator itr = set.iterator();
    int outArrayIndex = 0;
    String[] outputArray = new String[strArray.length];
    while (itr.hasNext()) {

        Integer intValue = (Integer) itr.next();
        List list = (List) map.get(intValue);
        for (int i = 0; i < list.size(); i++) {
            outputArray[outArrayIndex] = (String) list.get(i);
            outArrayIndex++;
        }
    }

    return outputArray;
}

private static void printArray(String[] strArray) {

    System.out.println("*****************");
    for (int i = 0; i < strArray.length; i++) {
        System.out.println(strArray[i]);
    }

}

}

SanA · Accepted Answer · 2016-03-19 06:13:03Z

0

    String[] strArray = new String[] { "cat", "star", "act", "gid", "arts",
            "dog", "rats" };
    List<String> strings = Arrays.asList(strArray);
    strings.sort((s1, s2) -> Math.abs(s1.length()) - Math.abs(s2.length()));
    System.out.println(strings);

answered Mar 19, 2016 at 6:13

SanA

1291 silver badge7 bronze badges

Comments

Soudipta Dutta · Accepted Answer · 2019-03-21 07:42:57Z

Question: Sort an array of strings according to string lengths. We can do it Using Streams in Java 8

public class SortStringsAccordingToLength {

    public static void main(String[] args) {
        List<String> sampleStrings = Arrays.asList("Protijayi", "Gina", "Gini", "Soudipta");

        System.out.println(lengthSortUsingSorted1(sampleStrings));

        System.out.println(lengthSortUsingSorted2(sampleStrings));
        System.out.println(lengthSortUsingSorted3(sampleStrings));
        System.out.println(lengthSortUsingSorted4(sampleStrings));
    }

    private static List<String> lengthSortUsingSorted4(List<String> list) {

        list.sort((a, b) -> Long.compare(a.length(), b.length()));
        System.out.println(list);

        return list;
    }

    private static List<String> lengthSortUsingSorted3(List<String> sampleStrings) {
        List<String> list1 = sampleStrings.stream()
                .sorted(Comparator.comparingLong(String::length).thenComparing(Comparator.naturalOrder()))
                .collect(Collectors.toList());
        return list1;
    }

    private static List<String> lengthSortUsingSorted2(List<String> sampleStrings) {
        List<String> list1 = sampleStrings.stream().sorted(Comparator.comparingInt(String::length))
                .collect(Collectors.toList());
        return list1;
    }

    public static List<String> lengthSortUsingSorted1(List<String> sampleStrings) {
        List<String> list1 = sampleStrings.stream().sorted((s1, s2) -> s1.length() - s2.length())
                .collect(Collectors.toList());
        return list1;
    }

}

Collectives™ on Stack Overflow

Sort an array of strings based on length

8 Answers 8

Comments

Comments

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

8 Answers 8

Comments

Comments

Comments

1 Comment

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related