Welcome to our community

Be a part of something great, join today!

Selection Sort Algorithms

Joystar1977

Active member
Jul 24, 2013
119
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

Administrator
Staff member
Feb 24, 2012
13,775
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
Jul 24, 2013
119
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

Administrator
Staff member
Feb 24, 2012
13,775
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
Jul 24, 2013
119
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
Jan 30, 2012
2,492
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,

as your second line says.

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

Joystar1977

Active member
Jul 24, 2013
119
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
Jan 30, 2012
2,492
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.