Selection Sort Algorithms

Joystar1977

Active member
Sort with Selection Sort algorithms the following list:

329, 363, 373, 334, 320

Give the intermediate lists at each step.

I found the following information about Selection Sort. It states as follows: "The idea of selection sort is rather simple: the next largest (or smallest) element in the array is repeatedly found and moved to its final position in the sorted array. In order to sort the array in increasing order, the smallest element at the beginning of the array and the largest element at the end, the largest element is selected and moved to the highest index position. This is done by swapping the element at the highest index and the largest element. The effective size of the array is then reduced by one element and the process is repeated on the smaller (sub array). The process ends when the effective size of the array becomes 1 (an array of 1 element is already sorted)."

Can someone please explain this in simpler terms? What does it mean when it says to give the intermediate lists at each step?

MarkFL

Staff member
I will explain this with an example array:

[2, 4, 1, 5, 3]

1.) We find that 5 is the greatest element, so we swap 5 and the element at the last position, and take this out of the array:

[2, 4, 1, 3], 5

2.) Now, for the remaining four elements in the array, we find 4 is the greatest element, so we swap 4 with the element in the last position and take it out of the array:

[2, 3, 1], 4, 5

3.) For the remaining three elements, we find that 3 is the greatest element, so we swap it with the element in the last position and take it out of the array:

[2, 1], 3, 4, 5

4.) For the remaining two elements, we find 2 is the greatest element, so we swap it with the element in the last position and take it out of the array:

[1], 2, 3, 4, 5

Now we are down to an array of one element, and the original array is sorted:

1, 2, 3, 4, 5

Joystar1977

Active member
Is this correct with Selection Sort?

329, 364, 373, 334, 320

[329, 364, 334, 320], 373

[329, 334, 320], 364, 373

[329, 320], 334, 364, 373

[320], 329, 334, 364, 373

320, 329, 334, 364, 373

Are the intermediate lists at each step around the parentheses or brackets?

MarkFL

Staff member
The brackets denote those elements still in the array. It looks like you are removing the greatest element without making the required swap.

Joystar1977

Active member
MarkFL, can you please then correct what I did because I was trying to follow the example you gave about how to do Selection Sort Algorithms. Does it matter whether or not I use parentheses or brackets?

Evgeny.Makarov

Well-known member
MHB Math Scholar
The algorpthm description says,
the largest element is selected and moved to the highest index position. This is done by swapping the element at the highest index and the largest element.
Is this correct with Selection Sort?

329, 364, 373, 334, 320

[329, 364, 334, 320], 373
What is the element at the highest index in the initial array? It's the element at the end of the array, i.e., 320. What is the largest element? It's 373. Now the description says that you have to swap 320 and 373 in [329, 364, 373, 334, 320]. You get

329, 364, 320, 334, 373,

and not

329, 364, 334, 320, 373,

Now you exclude the last element (373), restrict you array to the first four elements and do the same.

Joystar1977

Active member
Evgeny.Makarov! I don't quite understand what your doing in this process of Selection Sort. Is this correct then as follows:

329, 364, 373, 334, 320

[329, 364, 320, 334], 373

[329, 334, 320], 364, 373

[329, 320], 334, 364, 373

[320], 329, 334, 364, 373

320, 329, 334, 364, 373

Evgeny.Makarov

Well-known member
MHB Math Scholar
329, 364, 373, 334, 320

[329, 364, 320, 334], 373

[329, 334, 320], 364, 373

[329, 320], 334, 364, 373

[320], 329, 334, 364, 373

320, 329, 334, 364, 373
Yes, this is correct.