Selection Sort help

[Adam Scott]

I have a question about selection sort. If I had an array of numbers, 1 2 3 4 100 0, and used the selection sort method (below) on the array,
would the 0 slowly work it's way down to the end?


Nest loop = full rotation of nest loop

Nest loop 1: 1 2 3 4 100 0
Nest loop 2: 1 2 3 4 100 0
Nest loop 3: 1 2 3 4 100 0
Nest loop 4: 1 2 3 4 100 0
Nest loop 5: 1 2 3 4 0 100
Nest loop 6: 1 2 3 0 4 100
etc.

METHOD:

static void selectionSort(int[] arr){
		int n = arr.length;        

		for(int i = 0;i<n;i++){
			int min = i;
			for(int j = i+1;j<n;j++){
				if(arr[j]<arr[min]){
						min = j;
				}
			}
			int temp = arr[i];
			arr[i] = arr[min];
			arr[min] = temp;
		}
	}

[Matthew Brown]

Well, you can always step through it to find out, or add some print statements. But in selection sort, the 0 should jump straight to the start once you've identified it as the smallest element.

[Jelle Klap]

No, a selection sort is just a slightly more optimal bubble sort that requires O(N) swaps instead of O(N²), but still requires O(N²) comparisons. It does this by iterating the entire remainder of the array relative to the starting index and "selecting" the index of the smallest value it encounters. Only after the entire remainder of the array has been iterated are values at the starting index and the "smallest value" index finally swapped. So, in your example, the inner loop would perform 5 iterations, discover (coincidentally during the fifth iteration) that 0 is the smallest value in the array and set min to point at the index of that smallest value; that index is 5. The inner loop then completes. Only now, in the first iteration of the outer loop, are the values at index 0 and index 5 actually swapped, after which the outer loop starts its second iteration. Long story short, no, 0 does not slowly work its way to the start of the array, it is selected into that position immediately.

[Adam Scott]

I see so it looks at the entire array, swap number, and then repeats until it's sorted, thanks for the help!

[Campbell Ritchie]

Jelle Klap wrote:No, a selection sort is just a slightly more optimal bubble sort . . . .

I once timed a selection sort on a 1000000‑element int[] and it took about 1hr 39min, as against bubble sort with took about 1hr 40min. Arrays#sort which I think is a quicksort took something in the region of 0.4″ for the same exercise.

[Matthew Brown]

Campbell Ritchie wrote: Arrays#sort which I think is a quicksort took something in the region of 0.4″ for the same exercise.

Arrays.sort uses (a variant of) quick sort for primitive values, and (a variant of) merge sort for reference types. I think that's because it's more likely that a stable sort method will be useful for reference types (because you might want to sort by different fields at different times).

[Jelle Klap]

I think it even falls back to selection sort for tiny arays.

Edit: insertion sort according to the JDK source.

    /**
     * Tuning parameter: list size at or below which insertion sort will be
     * used in preference to mergesort.
     * To be removed in a future release.
     */
    private static final int INSERTIONSORT_THRESHOLD = 7;

    private static void mergeSort(Object[] src,
                                  Object[] dest,
                                  int low,
                                  int high,
                                  int off) {
        int length = high - low;

        // Insertion sort on smallest arrays
        if (length < INSERTIONSORT_THRESHOLD) {
            for (int i=low; i<high; i++)
                for (int j=i; j>low &&
                         ((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
                    swap(dest, j, j-1);
            return;
        }
        
        // ...
}