5
\$\begingroup\$

This code sort the string below in ascending order.

I'd prefer it split-up in two or three smaller, simpler methods. I'm also wondering whether my algorithm has a decent time complexity.

Given string

[H, B, D, G, F, E, A, C]

Output

[A, B, C, D, E, F, G, H]

public class sortArray {
    public static void sort (String[] str)
    {
        int lastPos = str.length - 1;
        int minPos = 0;
        String s = "";
        for (int i = 0; i < lastPos; i++)
        {
            minPos = i;
            for (int j = i + 1; j <= lastPos; j++)
                if (str[j].compareTo (str[minPos]) < 0)
                    minPos = j;
            if (minPos != i)
            {
                s = str[i];
                str[i] = str[minPos];
                str[minPos] = s;
            }
        }
    }

    public static void main(String[] args){
        String[] str = {"H", "B", "D", "G","F", "E", "A", "C"};
        sort(str);
        System.out.println(Arrays.toString(str));
    }
}
\$\endgroup\$
  • 3
    \$\begingroup\$ In case if you are trying to sort an array, you could have achieve this whole thing with Arrays.sort(str); \$\endgroup\$ – Jude Niroshan Apr 9 '17 at 12:48
4
\$\begingroup\$

Your algorithm is selection sort.

Selection sort has a time complexity of \$O(n^2)\$. For sorting algorithms, that's pretty slow.

Consider looking up a sorting algorithm such as quicksort, which, whilst it does have a worst case performance of \$O(n^2)\$, on average, it tends to take \$O(n log n)\$.

Or, as suggested in the comments, make use of the built-in libraries. Use Arrays.sort. Use of library code, especially when part of the language that you're programming in, can save significantly on the work you need to do.


Splitting up your code into several methods can be done.

Take this section, for instance.

        for (int j = i + 1; j <= lastPos; j++)
            if (str[j].compareTo (str[minPos]) < 0)
                minPos = j;

What it does is it looks for the smallest string in the array. So you could turn this into a function, with arguments for the array and the starting position (array.length will get you the end).

The swap,

        if (minPos != i)
        {
            s = str[i];
            str[i] = str[minPos];
            str[minPos] = s;
        }

Could also be a separate method.

If you extract those two sections of code to separate functions, the main sorting function will look like this:

public static void sort (String[] str)
{
    int lastPos = str.length - 1;
    for (int i = 0; i < lastPos; i++)
    {
        swap(str, i, findSmallest(str, i));
    }
}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.