programming forums Java Java JSRs Mobile Certification Databases Caching Books Engineering OS Languages Paradigms IDEs Build Tools Frameworks Products This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
Sheriffs:
Saloon Keepers:
Bartenders:

# Selection Sort help

Greenhorn
Posts: 4
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.

Matthew Brown
Bartender
Posts: 4568
9
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
Bartender
Posts: 1952
7
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.

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

Campbell Ritchie
Marshal
Posts: 56562
172
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
Bartender
Posts: 4568
9
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
Bartender
Posts: 1952
7
I think it even falls back to selection sort for tiny arays.

Edit: insertion sort according to the JDK source.