How does the swap work in Selection sort?

Question

can someone please explain why the swap portion of this method works, I have been using this method for some time but I can't wrap my head around how the swap portion works. I would appreciate it if someone could explain it. thank you

 public static int [] selectionSort(int [] num){ int min=0,minIndex=0; for(int i=0; i< num.length-1;i++){ min=num[i]; for(int x=i+1;x<num.length;x++){ if(min > num[x]){ min=num[x]; minIndex=x; } } //this is the part Im so confused about if(num[i]> min){ int temp=num[i]; num[i]=num[minIndex]; num[minIndex]=temp; } } return num; }

What's confusing? It's swapping the element at index i with the element at index minIndex. — Bohemian
– Bohemian ♦, Commented Jun 11, 2017 at 22:21
Try to write the code to swap the values of two variables and you will understand. — Alexander Torstling
– Alexander Torstling, Commented Jun 11, 2017 at 22:26

cs95 · Accepted Answer · 2017-06-11 22:23:04Z

The whole notion of selection sort is to select the index of the next smallest element and move it to its rightful position.

In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

The following example explains the above steps:

int 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 (64 is automatically sorted)

At each step, you find minIndex. You then swap the value in arr[minIndex] with the value in arr[i].

So at iteration 0, minIndex will be 4 since 11 is at index 4, and i is, of course, 0 since it is the first iteration.... and so on.

At iteration 0, num[i] => 64, and num[maxIndex] => 11.

int temp = num[i]; // temp => 64 num[i] = num[minIndex]; // num[i] = num[minIndex] => 11 num[minIndex] = temp; // num[minIndex] => 64

After iteration 0, num[i] => 11, and num[maxIndex] => 64.

your step by step explanation was the missing link for me, thank your for your help

MagikarpSama · Accepted Answer · 2017-06-11 22:25:58Z

Since variables in Java aren´t adressed with pointers but with their value (call-of value instead call-of reference), you need to assign a temp variable to store your smallest value in. Because you are setting the num[i] to another number, you need to be able to access the number later.

int temp=num[i]; //create temp variable to store the number in array num on index i num[i]=num[minIndex]; // assign a new number to num on index i num[minIndex]=temp; // now assign the temp number to num on index minIndex

Collectives™ on Stack Overflow

How does the swap work in Selection sort?

2 Answers 2

2 Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Related