Selection Sort, For Java
Solution 1
Well, let's translate the pseudo-code to pseudo-English.
A - an array containing the list of numbers
numItems - the number of numbers in the list
for i = 0 to numItems - 1
for j = i+1 to numItems
if A[i] > A[j]
// Swap the entries
Temp = A[i]
A[i] = A[j]
A[j] = Temp
End If
Next j
Next i
which might read
Count through each item, from the beginning to the end, calling it X
While considering item X, count through each item after it, from just
after X to the end, calling it Y
If X is bigger than Y, swap the two, temporarily storing X in Temp
so it doesn't get lost when we copy Y into X. Copy Y into X, and then
Copy the temporarily stored old value of X (remember it is in Temp)
back into Y. Now the values of X and Y are swapped (so X is now smaller
than Y)
Now it's your job to write it in code.
Solution 2
The name of the algorithm tells you a whole lot about it. It first selects the smallest element of the list and puts it in the first spot. Then it selects the second and puts it in the second, etc.
How do you find the smallest element? Well you look through the list, and if the element you're looking at is smaller than the element at the beginning of the list, swap it in.
How do you find the second smallest? You know that the smallest element is already in the first spot. So that means the second smallest must be the smallest element between the second element and the end of the list. So you go through and do the appropriate swaps again.
Lather, rinse, and repeat.
If you're wondering how elements are swapped. Just think about how you would do it by hand. You pick element 1 up and put it in a safe place, put element 2 in element 1's old spot, then put element 1 in element 2's old spot. The temporary variable used would represent the safe place you put element 1.
Wikipedia has a nice article on it.
King
Updated on June 04, 2022Comments
-
King almost 2 years
I am having trouble understanding this pseudocode, and implementing it into my program. Can anybody explain it better or show me how the code would look? Thanks.
A - an array containing the list of numbers numItems - the number of numbers in the list for i = 0 to numItems - 1 for j = i+1 to numItems if A[i] > A[j] // Swap the entries Temp = A[i] A[i] = A[j] A[j] = Temp End If Next j Next i