CODEWITHSUNDEEP
arraysstringalgorithmsorting
codewarrior
codewarrior

Reputation: 1034

Sort an array of strings based on length

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

Upvotes: 4

Views: 16125

Answers (8)

Soudipta Dutta
Soudipta Dutta

Reputation: 2122

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

}

Upvotes: 0

SanA
SanA

Reputation: 129

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

Upvotes: 0

SanA
SanA

Reputation: 129

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

}

}

Upvotes: 0

Trying
Trying

Reputation: 14278

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

Upvotes: 3

Wagner DosAnjos
Wagner DosAnjos

Reputation: 6374

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

Upvotes: 0

Aman Gautam
Aman Gautam

Reputation: 3579

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

Upvotes: 0

Prabhakaran Ramaswamy
Prabhakaran Ramaswamy

Reputation: 26094

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

Upvotes: 5

Don
Don

Reputation: 87

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.

Upvotes: 2

Related Questions