MHB How Does the Selection Sort Algorithm Work?

[Joystar77]

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]

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

 

[Joystar77]

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]

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

 

[Joystar77]

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]

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.

 

[Joystar77]

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]

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.