Selection Sorting Algorithm for strings

Question

I was having trouble following the selected sorting algorithm for sorting strings in an array alphabetically. My code as it is, is a complete mess.

public class sorting {
public void getArray(String [] a) {
    int min = 0;
    int minIndex = 0;
    for (int j = 0; j < a.length; j++ ) {
        for (int i = j; i < a.length; i++) {
            if (i == j) {
                 a[min] = a[j]; 
            }
            if (a[min].compareTo(a[i]) < 0) { // if current element is < lowest, assign new lowest.
                a[min] = a[i];
                minIndex = i;
            } // end of if
        } // end of INSIDE for

        a[minIndex] = a[j]; // place first element at the location of the smallest element.
        a[j] = a[min]; // place the smallest element value in the first spot. 
    } // end of OUTSIDE for    
}

Can anyone throughly explain to me their thought process in going on about this? For instance, what does the inner for loop do vs the outside? Many thanks in advance!

Vincent van der Weele · Accepted Answer · 2015-02-12 07:03:28Z

1

Very simply put, selection sort does the following:

Find the smallest element
Swap it with the first element
Find the second smallest element
Swap it with the second element
... (and so on)

After steps 1 and 2, you know that the smallest element is in the first spot of the array. In step 3 you look for the second smallest element, which is the smallest if you start searching from the second position.

This is what the outer loop does: find the j-th smallest element and swap it with the element in spot j.

Now, how do you find the smallest element in an array? For that you need the inner loop. You keep track of the smallest element so far (and the index where you found it) and whenever you find a smaller element, you update the current smallest element (and the index where you found it).

There are two bugs in your code though:

When you're tracking the minimum element of an array, you are overwriting elements of your input. Instead of using a[min], you should always use min directly (for that you need to change the type to String of course).
You should check if the a[i] is smaller than min, not the other way around.

if (i == j) {
    min = a[j];
}
if (a[i].compareTo(min) < 0) {
    min = a[i];
    minIndex = i;
}

and in the end:

a[minIndex] = a[j]; 
a[j] = min;

edited Feb 12, 2015 at 7:03

answered Feb 12, 2015 at 6:17

Vincent van der Weele

13.2k1 gold badge37 silver badges66 bronze badges

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

10 Comments

Destinox Over a year ago

To make this a little more brain compatible: would the outer for loop be considered the "Macro?" as in where all the elements are in their final positions and the inner for loop be considered the "Micro?" in that the smallest element is being found?

Vincent van der Weele Over a year ago

@Destinox yes, that logic is correct. And if you want to name those loops "macro" and "micro", be my guest ;)

Destinox Over a year ago

Update: Strings are passed through this method. How would min (an integer) work in this scenario?

Destinox Over a year ago

Min would not be able to work since the parameters are not strings.

Vincent van der Weele Over a year ago

@Destinox just change the type to String (also updated my answer).

|

sprinter · Accepted Answer · 2015-02-12 06:18:06Z

Sure I can have a go at explaining it to you. Firstly I'll do a bit of refactoring to make it a bit easier for me to explain. It is logically equivalent to the code you posted just with variables renamed and some logic split out into a second method rather than having an inner and outer loop.

This method iterates through the strings and, for each entry, calls swapMinFromIndex

public void sortStrings(String[] strings) {
    for (int i = 0; i < strings.length; i++)
        swapMinFromIndex(strings, i);
}

This method starts by assuming the first element is the smallest. It then goes through the remaining elements and if any are smaller than the current smallest it stores their index. Finally it swaps the smallest with the first (unless they are the same).

private void swapMinFromIndex(String[] strings, int start) {
    int indexOfMin = start;
    for (int i = start + 1; i < strings.length; i++) {
        if (strings[i].compareTo(strings[indexOfMin]) {
            indexOfMin = i;
        }
    }
    if (indexOfMin != start) {
        String tmp = strings[start];
        strings[start] = strings[indexOfMin];
        strings[indexOfMin] = tmp;
    }
}

So together these two methods continually look for the smallest element and swap it into position.

Collectives™ on Stack Overflow

Selection Sorting Algorithm for strings

2 Answers 2

10 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

10 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related