Selection sort is an in place sorting algorithm. The selection sort
algorithm sorts an array by repeatedly finding the minimum element (considering
ascending order) from unsorted part and putting it at the beginning.
Algorithm:
- Find the minimum value in the list (Array).
- Swap it with the value in the current position.
- Repeat this process for all the elements until the entire array is sorted.
Worst case complexity
|
O(n2)
|
Best case complexity
|
O(n)
|
Average case complexity
|
O(n2)
|
Worst case space complexity
|
O(1) auxiliary
|
public class SelectionSort
{
public static int[]
doSelectionSort(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;
int smallerNumber = arr[index];
arr[index]
= arr[i];
arr[i]
= smallerNumber;
}
return arr;
}
public static void
main(String a[]){
int[]
arr1 = {2, 5, 2, 8, 5, 6, 8, 8};
int[]
arr2 = doSelectionSort(arr1);
System.out.println("Sorted List is::");
for(int i:arr2){
System.out.print(i);
System.out.print(", ");
}
}
}
Output:
Sorted list is ::
2 2 5 5 6 8 8 8
