1
\$\begingroup\$

I have the following first-letter only alphabetical sorting algorithm:

Note: FileManager is just a file I/O class that reads in the unsorted words from a textfile then writes the sorted ones back out).

public class Sorter { 
    static String list[];

    public static void main(String args[]) {
        FileManager fm = new FileManager(); 
        list = new String[fm.amountOfWords];
        boolean sorted = false;
        System.out.println("UNSORTED LIST: ");
        for (int x = 0; x < list.length; x++) {
            list[x] = fm.list[x];
            System.out.println(list[x]);
        }

        for (int y = 0; y < 100; y++) {
            for (int x = 0; x < list.length; x++) {
                int current = list[x].charAt(0);
                if (x != list.length - 1) {
                    if (current > list[x + 1].charAt(0)) {
                        String temp;
                        temp = list[x + 1];
                        list[x + 1] = list[x];
                        list[x] = temp;

                    }
                } else {

                    list[x] = list[x];

                }

            }

        }

        fm.writeSortedContents();
        System.out.println("");
        System.out.println("SORTED (v3):");
        for (int x = 0; x < list.length; x++) {
            System.out.println(list[x]);
        }
    }

This code works fine as far as I can tell. In general, I'm just looking for tips to make it better.

However, I have found one simple issue that could be fixed: it doesn't know when to actually stop. I'm just running sorting code 100 times in a for loop because at that point its almost guaranteed that a short list that needs to be sorted has actually been sorted. In this case specifically, this isn't an issue but for future programs where memory/speed is a factor I need to fix this (also for learning purposes).

Is there any way to increase the efficiency of this algorithm by perhaps determining exactly how many times it needs to run the sort code?

\$\endgroup\$
2
\$\begingroup\$

This search algorithm is deeply flawed. Assuming no prior knowledge about the original ordering of the list, instead of 100 iterations, you need list.length iterations to guarantee correct ordering. This is easy to see if you consider the unfortunate case when the smallest item starts in the last position. If the size of the list is bigger than 100, the item will not reach its correct position. If the list is smaller than 100, then the program is doing pointless iterations.

There are some very strange parts in this code. Instead of this:

for (int x = 0; x < list.length; x++) {
    list[x] = fm.list[x];
    System.out.println(list[x]);
}

This is much better:

String[] list = fm.list.clone();

And this is completely pointless:

    } else {

        list[x] = list[x];

    }

The main method is doing too much. Try to decompose to smaller functions that do one thing and do it well. For example, printing and sorting should be separated.

Lastly, the algorithm should be improved. If you change the number of iterations from 100 to the size of the list as I suggested, the algorithm becomes quadratic. That's very poor. Wikipedia explains many better algorithms, for example merge sort.

In this particular example, given that you want to sort only by the first letter, a radix sort would be very efficient, run in linear time, if you don't mind using a little extra space.

| 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.