It is a sorting technique. It improves bubble sort by making only one exchange for every pass through the list of elements. First selection sort looks for the largest value when it through the pass and after completing the pass, after that it place in a proper location.
Time complexity of Selection sort: O(n2)
Average Performance: O(n2)
Worst case Performance: O(n2)
Best case performance: O(n2)
Worst Case Space complexity: O(n) total, O(1) auxiliary.
Example on Selection Sort:
52, 45, 789, 46, 89 [Initial Array of elements]
45, 52, 789, 46, 89 [After the first pass, First sub list {45}]
45, 46, 52, 789, 89 [After the second pass, Second sub list {45, 46}]
45, 46, 52, 89, 789 [After the third pass, Third sub list {45, 46, 52}]
45, 46, 52, 89, 789 [After the fourth pass, Fourth sub list {45, 46, 52, 89}]
45, 46, 52, 89, 789 [After the fifth pass or Last pass, sub list {45, 46, 52, 89, 789}]
Algorithm for Selection Sort:
Start
Construct a single dimensional array
Fill the array with elements.
Using the selection sort technique bring the smallest number to the first unsorted position of the array.
Repeat the last step till the entire array is sorted.
Print the sorted array
Stop.
Program for selection Sort in java:
public class SelectionSort {
public static void selectionSort(int[] arr){
for (int i = 0; i < arr.length – 1; i++)
{
int index = i;
for (int j = i + 1; j < arr.length; j++){
if (arr[j] < arr[index]){
index = j;//searching for lowest index
}
}
int smallerNumber = arr[index];
arr[index] = arr[i];
arr[i] = smallerNumber;
}
}
public static void main(String a[]){
int[] arr1 = {9,14,3,2,43,11,58,22};
System.out.println(“Before Selection Sort”);
for(int i:arr1){
System.out.print(i+” “);
}
System.out.println();
selectionSort(arr1);//sorting array using selection sort
System.out.println(“After Selection Sort”);
for(int i:arr1){
System.out.print(i+” “);
}
}
}
Output of the above program:
Before Selection Sort
9 14 3 2 43 11 58 22
After Selection Sort
2 3 9 11 14 22 43 58
Click here to View otherSorting Techniques
