public class Sort {
void selectionSort(int arr[]) {
int n = arr.length;
int currentMaximum;
int temp;
for (int i=0; i < n; i++) {
currentMaximum = 0;
// Considering the first element to be the maximum element of the unsorted array.
// And, (n-i) is to ignore the comparisons that is already done.
for(int j = 1; j < n-i; j++) {
if (arr[j] > arr[currentMaximum]) {
currentMaximum = j;
}
}
// Swap the Current Maximum element with the last element.
temp = arr[n-i-1];
arr[n-i-1] = arr[currentMaximum];
arr[currentMaximum] = temp;
}
}
public static void main(String args[]) {
int arr[] = {7, 4, 8, 1, 6};
Sort sort = new Sort();
sort.selectionSort(arr);
for(int i=0; i < arr.length; i++) {
System.out.print(arr[i]+", ");
}
}
}
We are just concerned about the 'void selectionSort(int arr[])' method, where the sorting logic is defined.
We have the array
int arr[] = {7, 4, 8, 1, 6}; Which we have passed to the 'selectionSort(..)' method.
In the 'bubbleSort(..)' method, we have taken the count of the elements of the array.
int n = arr.length;
Also note that,
int currentMaximum;
'currentMaximum' is going to hold the position of the Current Maximum value. I will clear it below.
Now, let us corelate this code with the explanation of Selection Sort.
Let us take the same values defined above.
And take the chunk of code and explain it.
for (int i=0; i < n; i++) {
currentMaximum = 0;
// Considering the first element to be the maximum element of the unsorted array.
// And, (n-i) is to ignore the comparisons that is already done.
for(int j = 1; j < n-i; j++) {
if (arr[j] > arr[currentMaximum]) {
currentMaximum = j;
}
}
// Swap the Current Maximum element with the last element.
temp = arr[n-i-1];
arr[n-i-1] = arr[currentMaximum];
arr[currentMaximum] = temp;
}
So, the outer loop, i.e.
for (int i=0; i < n; i++)
Determines the Passes. If you see the above explanation you can find the first pass,
In the next step we have initialized the 'currentMaximum' to 0.
currentMaximum = 0;
Because no matter what we have to initialize the 'currentMaximum' to 0 at the end of every pass.
Then comes the the inner loop, i.e.
for(int j = 1; j < n-i; j++)
Which determines the iterations.
Next, comes the comparison part where we compare 2nd element with the currentMaximum. Now, since currentMaximum is at the 0th position of the Array. We compare if 4 is greater than 7 or not.
if (arr[j] > arr[currentMaximum]) {
currentMaximum = j;
}Let, us also look at the 2nd iteration.
In the above diagram we can see that j is 2. And if we refer to the code,
if (arr[j] > arr[currentMaximum]) {
currentMaximum = j;
}
a[j] is 8 and arr[currentMaximum] is 7. And 8 is greater than 7. So, we initialize currentMaximum with 2.
And in the next iteration j is increased by 1 and refers to the 3 in array,
In the next iteration j is increased by 1. And when we reach at the end of the pass( i.e. When j becomes 4),
We swap the currentMaximum with the last element.
temp = arr[n-i-1]; // (n-i-1) is (5-0-1) i.e. 4 arr[n-i-1] = arr[currentMaximum]; // currentMaximum is 2 arr[currentMaximum] = temp;
So, as mentioned we swap arr[n-i-1] i.e. arr[2] with arr[currentMaximum] i.e. arr[4]
And continue in the same pattern.
If we consider the Selection Sort Algorithm, there are two loops. Firstly, there is the 'for' loop.
And inside the 'for' loop there is also a 'for' loop.
The 'for' loop executes n times(Assuming the array contains n elements).
Now, for each iteration of 'for' loop, the nested 'for' loop also executes approximately 'n' times.
Which means for 1st iteration of 'for' loop,
Similarly, for 2nd iteration of 'for' loop,
Similarly, for nth iteration of 'for' loop,
So, the running time is close to n*n or n2.
So, in worst case the running time is O(n2).