Need help understanding Selection Sort Algorithm

Question

I was given this assignment yesterday in class and thought I understood the process of selection sort but I feel a little unsure about it now. I thought that after each pass the numbers on the left become sorted and are not checked again until all the numbers on the right have been sorted first.

Below are the instructions and my answer:

Show the resulting array after each pass of the selection sort algorithm. If the algorithm stops before a given pass is taken, leave that pass blank.

Original Array: 30 8 2 25 27 20 
PASS 1: 8 30 2 25 27 20 
PASS 2: 8 2 30 25 27 20 
PASS 3: 8 2 25 30 27 20 
PASS 4: 8 2 25 27 30 20 
PASS 5: 8 2 25 27 20 30

Can someone tell me if I did this correctly?

Answer 1

In Pseudocode:

Repeat until no unsorted elements remain:
    Search the unsorted part of the data to find the smallest value
    Swap the smallest found value with the first element of the unsorted part

According to this, your data list will be...

Original Array: 30 8 2 25 27 20

P1: [2] 8 30 25 27 20 // smallest(2), swap this with the first value(30)

P2: [2 8] 30 25 27 20 // smallest(8), don't need to swap 

P3: [2 8 20] 25 27 30 // smallest(20), swap this with the first ele of unsorted list(30)

P4: [2 8 20 25] 27 30 // smallest(25), don't need to swap

P5: [2 8 20 25 27] 30 // smallest(27), don't need to swap

P6: [2 8 20 25 27 30] // smallest(30), don't need to swap... sorted!

PASS 6 is not needed since the last element is already sorted anyway.

Check this video from CS50(well explained by Havard University.): https://www.youtube.com/watch?v=3hH8kTHFw2A

Answer 2

I am glad you tried it out

Algorithm is :

repeat (numOfElements - 1) times

  set the first unsorted element as the minimum

  for each of the unsorted elements

    if element < currentMinimum

      set element as new minimum

  swap minimum with first unsorted position

Output will be :

Pass 1 : 2 8 30 25 27 20
Pass 2 : 2 8 30 25 27 20
Pass 3 : 2 8 20 25 27 30
Pass 4 : 2 8 20 25 27 30
Pass 5 : 2 8 20 25 27 30

You can give custom input and it will show you step wise step output : https://visualgo.net/bn/sorting

Hope this helps :D

Cheers to your learning !