Java: Selection Sort My implementation vs. another

Question

The following is my implementation of Selection Sort:

package algorithm.selectionsort;

public class SelectionSort {

    public static void main(String[] args) {
        int[] myArray = selectionSort(new int[] { 9, 9, 9, 8, 7, 73, 32, 109, 1100, 432, 321, 0 });

        for (int element : myArray) {
            System.out.print("" + element + " ");
        }

    }

    public static int[] selectionSort(int[] a) {
        int min;
        for (int i = 0; i < a.length - 1; i++) {
            min = i;
            for (int j = i + 1; j < a.length; j++) {
                if (a[j] < a[min]) {
                    min = j;
                    int temp = a[i];
                    a[i] = a[min];
                    a[min] = temp;

                }
            }
        }
        return a;

    }

}

I noticed that my instructor codes it slightly differently:

public static int[] selectionSort(int[] a) {
    int min;
    for (int i = 0; i < a.length - 1; i++) {
        min = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[j] < a[min]) {
                min = j;


            }
        }
        int temp = a[i];
        a[i] = a[min];
        a[min] = temp;
    }
    return a;

}

Both implementations work. I'm curious as to what the difference here is. Is it efficiency?

I see it - I'm unnecessarily repeating the same code over and over. The effect is the same but this will slow me to a crawl with huge data sets. — Dewey Banks
– Dewey Banks, Commented Aug 29, 2017 at 2:33
Your instructor implemented selection sort, you invented another sort which looks very similar but is less efficient. — Nir Alfasi
– Nir Alfasi, Commented Aug 29, 2017 at 2:33

user3437460 · Accepted Answer · 2017-08-29 02:52:34Z

The difference between your instructor's and yours is that he iterate through the array and for each element, search for the minimum, then perform a swap with the element after the wall index.

For yours, you iterate through the array and for each element, while searching for the minimum, if current value is < then the current tentative min, perform a swap with the element after the wall index.

So instead of swapping n times, you could possible swap n*n times for worst case:

Your swap for just one pass (worst case):

100, 90, 88, 70, 55, 43, 32, 28, 19, 10
90, 100, 88, 70, 55, 43, 32, 28, 19, 10
88, 100, 90, 70, 55, 43, 32, 28, 19, 10
70, 100, 90, 88, 55, 43, 32, 28, 19, 10
55, 100, 90, 88, 70, 43, 32, 28, 19, 10
43, 100, 90, 88, 70, 55, 32, 28, 19, 10
32, 100, 90, 88, 70, 55, 43, 28, 19, 10
28, 100, 90, 88, 70, 55, 43, 32, 19, 10
19, 100, 90, 88, 70, 55, 43, 32, 28, 10
10, 100, 90, 88, 70, 55, 43, 32, 28, 19

Your instructor's swap for just one pass (worst case):

100, 90, 88, 70, 55, 43, 32, 28, 19, 10
10, 90, 88, 70, 55, 43, 32, 28, 19, 100

In essence, you swap the values while in the midst of searching for the min. The "min" you swapped may not be the lowest value in the array.

Javdroider · Accepted Answer · 2017-08-29 02:49:53Z

ofcouse your instructor's code is more efficiency and more elegant. What is Selection Sort?

The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

If the length of the list to be sorted is n, then just n times of exchange should be done, but in your code, it's n*(n-1)*(n-2)....

Collectives™ on Stack Overflow

Java: Selection Sort My implementation vs. another

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related