Insertion Sort for a string

Question

I'm fairly new to coding and I'm trying to alphabetize a single string from an array of strings using an insertion sort. Any help would be deeply appreciated. The input is "alpha" or s[5]; I expect "aahlp". My code currently prints out "alpha".

public static void main(String[] args) 
{
    String[]s = new String[] {"bob", "charlie", "mike", 
                             "lola", "arnold","alpha"};

    sort(s[5]);
}

public static void sort(String s)
{
    String temp = null;
    for(int i = 1; i<s.length(); i++)
    {
        char next= s.charAt(i);

        int j=i;
        while (j > 0 && s.charAt(j-1)>next) 
        { 
            temp = s.substring(0, i) + s.charAt(j-1) + s.substring(i+1);
            System.out.println(temp);
            j--;
        }

        //this is where the problem seems to be happening:
        temp= s.substring(0,i)+next+s.substring(i+1);
        s=temp;
    }
    System.out.println(s);
}

How about some inputs, expected results, and the actual (incorrect?) results your code is currently producing? — William Price
– William Price, Commented Feb 13, 2015 at 5:53
what does alphabetize a single string from an array of strings mean ? — mangusta
– mangusta, Commented Feb 13, 2015 at 6:15
I.E. "dcba" alphabetized is "abcd". Later in development I will use a for loop to sort the whole String[] s; for the time being, I want to be able to sort one element in s- that element being s[5] or "alpha". — Jawsh Bivens
– Jawsh Bivens, Commented Feb 13, 2015 at 6:19
I'd change your approach, given String is immutable, first get its characters with toCharArray(), do you algorithm stuff on the array, then make the resultant string at the end using new String(sortedCharArray) — Adam
– Adam, Commented Feb 13, 2015 at 6:26
Since strings are immutable, do not do your sort on a String itself. Do a sort on char[] chars you can get as String#toCharArray(), and then return new String(chars). — ioreskovic
– ioreskovic, Commented Feb 13, 2015 at 7:14

ioreskovic · Accepted Answer · 2015-02-13 07:30:33Z

1

Since String is immutable, you cannot really sort it. However, you can obtain the underlying char array and sort that and then create a new String from it.

If your exercise is to implement such a sort algorithm yourself, then you can do something like this:

public class StringSort {
    public static String insertionSort(String s) {
        return new String(insertionSort(s.toCharArray()));
    }

    private static String insertionSort(char[] array) {
        int len = array.length;

        for (int i = len - 1; i > 0; i--) {
            if (array[i] < array[i - 1]) {
                swap(array, i, i - 1);
            }
        }

        for (int i = 2; i < len; i++) {
            char temp = array[i];
            int j = i;
            while (temp < array[j - 1]) {
                array[j] = array[j - 1];
                j--;
            }
            array[j] = temp;
        }

        return new String(array);
    }

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

    public static void main(String[] args) {
        String s = "alpha";
        String sSorted = insertionSort(s);
        System.out.println(sSorted);
    }
}

However, if you are not required to implement the sorting yourself, then simply using built in sorts will reduce the possibility of error:

private static void sort(String s) {
    char[] array = s.toCharArray();
    Arrays.sort(array);
    System.out.println(new String(array));
}

answered Feb 13, 2015 at 7:30

ioreskovic

5,7377 gold badges41 silver badges71 bronze badges

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

1 Comment

Jawsh Bivens Over a year ago

I'm required to use insertion sort for my homework, or that second method would be the best. Thanks, I didn't know I couldn't change strings. Glad I consulted stackoverflow!

Paresh · Accepted Answer · 2015-02-13 07:27:25Z

0

Use below sort method instead:

private static void sort(String s) {
    char[] charArray = s.toCharArray();
    Arrays.sort(charArray);
    System.out.println(new String(charArray));
}

answered Feb 13, 2015 at 7:27

Paresh

1561 silver badge3 bronze badges

Comments

Jawsh Bivens · Accepted Answer · 2015-02-13 07:51:24Z

Thanks for your help guys. I got it working correctly and I was even able to make it sort the whole String array. Here's the code if you were wondering. (This has been edited several times)

public static void main(String[] args) 
    {
        String[]sa = new String[] {"bob", "charlie", "mike", 
                                 "lola", "arnold","alpha", "beta"};
        sort(sa);

        for (int i= 0; i< sa.length; i++)
        System.out.println(sa[i]);

    }

    public static String[] sort(String[] sa)
    {
        //indexing through sa[k] (the string array
        for(int k=0;k<sa.length;k++)
        {

            String s= sa[k];

        char[] adam=s.toCharArray();

        //The actual insertion sort, indexing through s, represented as char[] adam for simplicity
        for(int i = 1; i<adam.length; i++)
        {
            char next= adam[i];

            int j=i;
            //
            while (j > 0 && adam[j-1]>next) 
            { 
                adam[j]=adam[j-1];

                j--;
            }


           adam[j]=next;
           s=sa[k]=String.valueOf(adam);



        }


       //System.out.println(s);

        }

        return sa;
    }

Collectives™ on Stack Overflow

Insertion Sort for a string

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related