Selection sort offers improved performance over bubble sort, especially for arrays with a large number of elements. Where bubble sort accumulated the largest elements towards the end of the array, selection sort accumulates the smallest elements at the beginning of the array.
Write a method that uses the selection sort algorithm to sort an input array of integers. See the hints and click the red colored links for additonal details on the algorithm.
Examples:
selectionSortArray({1,5,2}) -> {1,2,5}
selectionSortArray({11}) -> {11}
selectionSortArray({}) -> {} {} -> [Empty] Array
1. Use head
- an index to keep track of the left subarray which is already sorted. head
should be incremented in every loop iteration.
2. At the same time, a nested inner for
loop finds the smallest element in the subarray starting from head
to the end of the array.
3. Use a temp
variable to do the swap.
4. You need to make a pass through all the elements of the array, selecting the smallest one and then swapping it with the element at head
. Now the leftmost integer
is sorted hence it doesn't need to be moved again.
5. This process continues until all the numbers are sorted and head
has reached the end of the array. Return arr
Selection sort enables us to do fewer swaps than bubble sort, and in practice it would offer better performance. However, the complexity of this sort
is the same as that of Bubble Sort - O(N^2)
public static int[] selectionSortArray(int[] arr){ return arr; }
C
Java
Python