• Post Reply Bookmark Topic Watch Topic
  • New Topic

Selection Sort help  RSS feed

 
Adam Scott
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Java
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think it even falls back to selection sort for tiny arays.

Edit: insertion sort according to the JDK source.
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!