Selection Sort – This
form of sorting algorithms finds the minimum value, swaps it with the value in
the first position, and repeats these steps for the remainder of the list. It
does no more than n swaps.
Algorithm used in
Selection Sort to find the smallest element in the array and swap it with the
element in the first position, then find the second smallest element and
exchange it with the element in the second position, and continue in this way
until the entire array is sorted.
Let n = array length =
size of the array and outer loop variable is ‘i’.
- The outer loop is executed n-1 times
- Each time the outer loop is executed, the inner loop is executed
- Inner loop executes n-1 times at first. On average, inner loop executes about n/2 times for each execution of the outer loop.
- Every time inner loop executer it find the least value from the list then swap it with the value in ‘i’ position.
Result is n *
n/2 * k, that is, O(n2/2 + k) = O(n2)
The Complexity of
Selection Sort will be same as Bubble Sort.
Complexity :
Best-Case Analysis
•
If
the elements start in sorted order, the for loop will compare the adjacent
pairs but not make any changes
•
So
the swapped Elements variable will still be false and the while loop is only
done once
•
There
are N – 1 comparisons in the best case
Worst-Case Analysis
•
If
in the best case the while loop is done once, in the worst case the while loop
must be done as many times as possible
•
Each
pass of the for loop must make at least one swap of the elements
•
The
number of comparisons will be:
Average-Case Analysis
•
We
can potentially stop after any of the (at most) N – 1 passes of the for loop
•
This
means that we have N – 1 possibilities and the average case is given by where
C(i) is the work done in the first i passes
•
On
the first pass, we do N – 1 comparisons
•
On
the second pass, we do N – 2 comparisons
Working Example.
Array
a[5] having 5 element starting from index 0 to 4.
Values
stored in a[]={5 ,3, 9, 8, 2}
The
passes will take place for the bubble sort –
Element
Position
|
0
|
1
|
2
|
3
|
4
|
Smallest
element
|
Pass-1
|
a[0]
|
a[1]
|
a[2]>
|
a[3]
|
a[4]
|
2
a[4] – Swap with a[0]
|
5
|
8
|
9
|
3
|
2
|
||
2
|
8
|
9
|
3
|
5
|
||
Pass-2
|
2
|
8
|
9
|
3
|
5
|
3
a[3] – Swap with
a[1]
|
2
|
3
|
9
|
8
|
5
|
||
Pass-3
|
2
|
3
|
9
|
8
|
5
|
5
a[4] – Swap with
a[2]
|
2
|
3
|
5
|
8
|
9
|
||
Pass-4
|
2
|
3
|
5
|
8
|
9
|
8
a[3] – Swap with
a[3]
|
Final
Positions of the Element
|
2
|
3
|
5
|
8
|
9
|
Algorithm
Algorithm
for i ?1 to n-1
min ?
i;
x ? A[i]
for j = i + 1 to n
do
If A[j] < min then
m? j
x? A[j]
end if
end for j
A[i] ? A [m]
end for i
Source Code
import
java.io.*;
public class Selection_Sort
{
public static void main(String
args[])throws IOException
{
BufferedReader br=new
BufferedReader(new InputStreamReader(System.in));
int Size;
System.out.print("\n\tEnter Size : ");
Size=Integer.parseInt(br.readLine());
int AR[]=new int[Size];
Selection_Sort SS=new
Selection_Sort();
SS.Accept(AR,Size);
System.out.print("\n\tOriginal Data : \t");
SS.Display(AR,Size);
SS.Sort(AR,Size);
System.out.print("\n\tAfter Sort : \t");
SS.Display(AR,Size);
}
void Sort(int AR[], int Size)
{
for(int i=0;i<Size-1;i++)
{
int small=AR[i];
int pos=i;
for(int
j=i+1;j<Size;j++)
{
if(AR[j]<small)
{
small=AR[j]; //Finding smallest
no
pos=j;
}
}
AR[pos]=AR[i];
AR[i]=small;
}
}
void Display(int AR[],int Size)
{
for(int i=0;i<Size;i++)
{
System.out.print(AR[i]+" ");
}
System.out.println();
}
void Accept(int AR[], int
Size)throws IOException
{
BufferedReader br=new
BufferedReader(new InputStreamReader(System.in));
for(int i=0;i<Size;i++)
{
System.out.print("\tEnter AR["+(i+1)+"] : ");
AR[i]=Integer.parseInt(br.readLine());
}
}
}
Output
Enter
Size : 5
Enter
AR[1] : 5
Enter
AR[2] : 3
Enter
AR[3] : 9
Enter
AR[4] : 8
Enter
AR[5] : 2
Original
Data : 5 3
9 8 2
After
Sort : 2
3 5 8
9
