Msinger Msinger -4 years ago 54
Java Question

selection sort , how does the swap work

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;
}

Answer Source

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download