CODEWITHSUNDEEP
javaalgorithmsorting
Destinox
Destinox

Reputation: 11

Selection Sorting Algorithm for strings

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!

Upvotes: 0

Views: 617

Answers (2)

Vincent van der Weele
Vincent van der Weele

Reputation: 13177

Very simply put, selection sort does the following:

  1. Find the smallest element
  2. Swap it with the first element
  3. Find the second smallest element
  4. Swap it with the second element
  5. ... (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:

  1. 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).
  2. 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;

Upvotes: 1

sprinter
sprinter

Reputation: 27956

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.

Upvotes: 0

Related Questions