Selection sort is a sorting algorithm is a type of comparison sort. It is inefficient on large lists, and generally performs worse than insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms. The selection sort performs the same number of comparisons as the bubble sort: N*(N-1)/2. For 10 data items, this is 45 comparisons. However, 10 items require fewer than 10 swaps. Thus, the selection sort improves on the bubble sort by reducing the number of swaps necessary from O(N2) to O(N). Unfortunately, the number of comparisons remains O(N2).
Selection sort logic:
1. Find the maximum value in the list
2. Swap it with the value in the last position
3. Repeat the steps above for the remainder of the list
Complexity: The time complexity of Selection sort is shown below in three different cases and worst-case space complexity.
| Worst Case | Best Case | Average Case | Worst case Space Complexity |
| O(n2) | O(n2) | O(n2) | O(n) total, O(1) auxiliary |
Example: The selection sort marks the last element (12). It then goes through the list to find the biggest number (72). It swaps this with the last element and the biggest element is now in its correct position. It then marks the last but one element (1) and looks through the remaining data (excluding the last element) for the next biggest number (64). These two numbers are then swapped. This process continues until n-1 passes have been made.
| Initial Data | 27 | 11 | 64 | →72 | 1 | 12 |
| 1st pass | 27 | 11 | →64 | 12 | 1 | 72 |
| 2nd pass | →27 | 11 | 1 | 12 | 64 | 72 |
| 3rd pass | →12 | 11 | 1 | 27 | 64 | 72 |
| 4th pass | 1 | →11 | 12 | 27 | 64 | 72 |
| 5th pass | 1 | 11 | 12 | 27 | 64 | 72 |
Program: The following program uses Selection sort algorithm to sort the elements of the array.
import java.io.*;
class SelectionSort
{
public static void main(String as[]) throws Exception
{
int i,j,k,n,t,max,a[]=new int[10];
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
System.out.println("How many values:");
n=Integer.parseInt(br.readLine());
System.out.println("Enter Values:");
for(i=0;i
a[i]=Integer.parseInt(br.readLine());
for(i=0;i
{
max=a[0];
k=0;
for(j=1;j
{
if(a[j]>max)
{
max=a[j];
k=j;
}
}
t=max;
a[k]=a[n-i-1];
a[n-i-1]=t;
}
System.out.println("After Sorting");
for(i=0;i
System.out.print("\t"+a[i]);
}
}
Output:
How many values: 4
Enter Values:
45
36
87
12
After Sorting:
12 36 45 87
0 comments:
Post a Comment