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

Need a **hand?** Try out these hints, one at a time.

Use two nested loops and put the **smallest** element at the beginning of the array in each iteration of the outer loop.

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**