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?

Search first and watch videos in youtube, en.wikipedia.org/wiki/File:Selection-Sort-Animation.gif — Saeed
– Saeed, Commented Apr 24, 2018 at 16:43

Hiteshdua1 · Accepted Answer · 2018-04-24 16:49:39Z

3

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 !

answered Apr 24, 2018 at 16:49

Hiteshdua1

2,28620 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

c-an · Accepted Answer · 2018-04-24 16:54:34Z

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

ISHAN KUMAR GHOSH · Accepted Answer · 2018-04-24 16:45:20Z

I noticed that 2 is the smallest element in your array. So in the 1st pass it should be in the start of the array. Kindly refer the below examples.

EXAMPLE 1 : arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4] // and place it at beginning 11 25 12 22 64

// Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 11 12 25 22 64

// Find the minimum element in arr[2...4] // and place it at beginning of arr[2...4] 11 12 22 25 64

// Find the minimum element in arr[3...4] // and place it at beginning of arr[3...4] 11 12 22 25 64

REFERENCE 1 : https://www.hackerearth.com/practice/algorithms/sorting/selection-sort/tutorial/

REFERENCE 2 : https://www.tutorialspoint.com/data_structures_algorithms/selection_sort_algorithm.htm

Michael · Accepted Answer · 2018-04-24 16:46:41Z

2

If you look at your results it should be obvious you haven't done it correctly. Eight is not less than two! :)

Take the first item: 30. Find the min: 2. Swap it.

PASS 1: 2 | 8 30 25 27 20

The first part of the list is now sorted (denoted by the pipe).

Take the next item: 8. Find the min - 8 is actually the min. No swap occurs.

PASS 2: 2 8 | 30 25 27 20

Take the next item: 30. Find the min: 20. Swap it.

PASS 3: 2 8 20 | 25 27 30

Take the next item: 25. It is the min. No swap occurs.

PASS 4: 2 8 20 25 | 27 30

Take the next item: 27. It is the min. No swap occurs.

PASS 5: 2 8 20 25 27 | 30

Take the next item: 30. It is the min. No swap occurs.

The list is now sorted.

answered Apr 24, 2018 at 16:46

Michael

44.5k12 gold badges97 silver badges143 bronze badges

Comments

Abhishek katiyar · Accepted Answer · 2020-11-23 17:50:43Z

### Step 1 − Set MIN to location 0 or any high Value
### Step 2 − Search the minimum element in the list
### Step 3 − Swap with value at index of minimum
### Step 4 − Repeat until iteration gets over
<code>

    final int[] intArr = new int[]{14, 33, 27, 10, 35, 19, 42, 44};
    int index = -1;
    boolean isMin;
    for (int i = 0; i < intArr.length; i++) {
      int min = 999999999;
      isMin = false;
      for (int j = i + 1; j < intArr.length; j++) {
        if (intArr[j] < min && intArr[i] >= intArr[j]) {
          min = intArr[j];
          index = j;
          isMin = true;
        }
      }
      if (isMin) {
        intArr[index] = intArr[i];
        intArr[i] = min;
      }
    }
    Arrays.stream(intArr).forEach(System.out::println);
</code>

Collectives™ on Stack Overflow

Need help understanding Selection Sort Algorithm

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related