selection sort method for array

Question

i have this method that i got from a website about selection sort that i need to check how it works :

import java.util.Arrays;

public class SelectionSort {
public static void selectionSort(int[] data, int low, int high) {
    if (low < high) {
        swap(data, low, findMinIndex(data, low));
        selectionSort(data, low + 1, high);
    }
}

public static void swap(int[] array, int index1, int index2) {
    int tmp = array[index1];
    array[index1] = array[index2];
    array[index2] = tmp;
}

public static int findMinIndex(int[] data, int index) {
        int minIndex;
        if (index == data.length - 1)
        return index;
        minIndex = findMinIndex(data, index + 1);
        if (data[minIndex] < data[index])
        return minIndex;
        else
        return index;
}



public static void main (String[] args) {
    int[] numbers = {3, 15, 1, 9, 6, 12, 21, 17, 8}; 
    SelectionSort.selectionSort(numbers, 0, numbers.length);
    System.out.println(Arrays.toString(numbers));
}
}

can you help me undrestand why is that int high get the last index of the array ?how?

Can you please show the code for your main() method where you call selectionSort, and then try to rephrase your question? It is not at all clear what you are asking, so it's hard to help. — JVMATL
– JVMATL, Commented Jan 17, 2014 at 22:24
I corrected the code in the question, it missed some lines. It makes the question too obvious now. — Raul Guiu
– Raul Guiu, Commented Jan 17, 2014 at 22:43

user3100783 · Accepted Answer · 2014-01-18 00:21:09Z

In this specific code...

findMinIndex compares the element in a given index to all elements in front of it (elements with higher indices) up to the very last element of the array.

So if you have an array:

int[] a = { 7, 4, 2, 6 };

and you call findMinIndex(a, 0); it will first check to see that there is an element after index 0. That's what this part does index == data.length - 1. If there is no element after, it will simply return the index it was passed. But there obviously is an element after index 0 since the array has length 4.

Now that we've confirmed that there are elements after our index, it is time to get the index of the smallest element after index. This way we can compare the element at our index to all the elements in front of it to see which element is smallest in the range index to array.length - 1 (inclusive). This is accomplished through recursion:

minIndex = findMinIndex(data, index + 1);

So the next few calls will go like this:

findMinIndex(data, 1);
// is there an element after 1? There is. So we end up calling findMinIndex again...

findMinIndex(data, 2); // is there an element after 2? Yes. Recurse...

findMinIndex(data, 3); // is there an element after 3? No. That's the end of the array

// remember this part? it's used now to finally terminate the recursion
if (index == data.length - 1)
    return index; // this equals 3

Now the recursive calls begin to unwind.

// index == 2 because the 2nd to last index is 2. remember our array has length 4 and indices 0-3.
minIndex = 3; // this is the index of the last element
if (data[3] < data[2]) { // look at our array 'a', is 6 less than 2?
    return 3; // No it is not. so this is not returned
} else {
    return 2; // we end up return the index (2) of the smaller element (2)
}

It unwinds again.

// index == 1
minIndex = 2; // we compared 2 and 3 and found that the element at index 2 was smaller
if (data[2] < data[1]) { // is 2 less than 4?
    return 2; // yes, this is returned because the element at index 2 is less than the element at index 1
} else {
    return 1; // false!
}

And one more time.

// index == 0 this is our original call! when we said findMinIndex(a, 0);
minIndex = 2;
if (data[2] < data[0]) { // is 2 less than 7?
    return 2; // yes it is
} else {
    return 0; // false!
}

Finally, the method will return 2. This is because of all the elements after (inclusive) index 0, the element with index 2 is the smallest.

Now let's look at selectionSort. When you first call it, you need to use this format:

selectionSort(a, 0, 4); // where 4 is the length of the array

This function also uses recursion. The swap method is self explanatory (it swaps the elements at 2 different indices). Now let's go through the recursive calls:

if (0 < 4) { // True of course
    swap(a, 0, findMinIndex(a, 0));
    selectionSort(data, 0 + 1, 4);
}

Remember that we found the smallest element after 0 (inclusive) had an index of 2. So the above code can be replaced with:

if (0 < 4) { // True of course
    swap(a, 0, 2);
    selectionSort(data, 0 + 1, 4);
}

This will change our array to {2, 4, 7, 6} because we swapped the elements at index 0 and index 2. Notice how index 0 is now the smallest element in the array with a value of 2.

Now selectionSort is called again to make sure the array is in order from least to greatest. The next call will look like this:

// low == 1 and high == 4
if (1 < 4) { // true
    swap(a, 1, findMinIndex(data, 1));
    selectionSort(a, 1 + 1, 4);
}

Remember our array is now {2, 4, 7, 6}. That means that the smallest element after index 1 (value of 4) is actually just 4. So the above code would be equal to:

// low == 1 and high == 4
if (1 < 4) { // true
    swap(a, 1, 1);
    selectionSort(a, 1 + 1, 4);
}

The swap does nothing in this case. Now the method is called recursively again.

// low == 2 and high == 4
if (2 < 4) { // true
    swap(a, 2, findMinIndex(data, 2));
    selectionSort(a, 2 + 1, 4);
}

Our array wasn't changed with the last swap. The smallest element after index 2 (inclusive) will be 6, which has an index of 3. That means our code above is equal to:

// low == 2 and high == 4
if (2 < 4) { // true
    swap(a, 2, 3);
    selectionSort(a, 2 + 1, 4);
}

Now our array becomes { 2, 4, 6, 7 }. Hooray it's in order from least to greatest! But that's not where it ends. There is another recursion call just to make sure that it's really in order.

// low == 3 and high == 4
if (3 < 4) { // true
    swap(a, 3, findMinIndex(data, 3));
    selectionSort(a, 3 + 1, 4);
}

Remember in findMinIndex it checks to see if there are any elements after the given index? There are no elements after index 3, so it will just return 3. That means the above code is equal to:

// low == 3 and high == 4
if (3 < 4) { // true
    swap(a, 3, 3);
    selectionSort(a, 3 + 1, 4);
}

This swap does nothing. And as you can see, there is still another recursion call! This will be the final one.

// low == 4 and high == 4
if (4 < 4) { // false, 4 is not less than 4
    swap(a, 4, findMinIndex(a, 4)); // none of this happens
    selectionSort(a, 4 + 1, 4); // no recursion
}
// finally returns void

The end.

It's a lot easier to understand selection sorts with loops as opposed to recursion.

Raul Guiu · Accepted Answer · 2014-01-17 22:42:11Z

1

It is the size of the array, it is used to know when is over.

Every cycle: First: checks if any element with and index higher than low (low starts at 0) is lower and if that is the case swaps them. Second: increase low

It stops when low is not lower than high (size of the array).

See the definition of selection sort:

http://en.wikipedia.org/wiki/Selection_sort

edited Jan 17, 2014 at 22:42

answered Jan 17, 2014 at 22:36

Raul Guiu

2,41423 silver badges39 bronze badges

Comments

Kermit the Hermit · Accepted Answer · 2015-11-08 18:20:38Z

For anyone looking for another way to do selection sort using recursion, here is one way to do it.

//the method that will be called to sort the array recursively
public static void selectionSort(double[] arr) {
    selectionSort(arr, 0);
}

//this is a recursive helper method.
//arr is the array to be sorted and index is the current index in
//the array which will be swapped with the smallest value in the
//remaining part of the array
private static void selectionSort(double[] arr, int index) {
    //if index has reached the second to last value, there are
    //no more values to be swapped
    if (index < arr.length - 1) {
        //let index, at first, be the index at which the smallest element is located
        int smallestIndex = index;
        //find the smallest entry in the array from i=index to i=index.length - 1
        for (int i = index + 1; i < arr.length; i++) {
            //if the element at i is smaller than the element at smallestIndex, then update the value of smallestIndex
            if (arr[i] < arr[smallestIndex]) {
                smallestIndex = i;
            }
        }
        //swap the elements of arr[smallestIndex] and arr[index]
        double t = arr[index];
        arr[index] = arr[smallestIndex];
        arr[smallestIndex] = t;
        selectionSort(arr, index + 1);
    }
}

Collectives™ on Stack Overflow

selection sort method for array

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related