Selection Sort

Given an array of integers, sort the elements in the array in ascending order. The selection sort algorithm should be used to solve this problem.

Examples

{1} is sorted to {1}
{1, 2, 3} is sorted to {1, 2, 3}
{3, 2, 1} is sorted to {1, 2, 3}
{4, 2, -3, 6, 1} is sorted to {-3, 1, 2, 4, 6}

Corner Cases

What if the given array is null? In this case, we do not need to do anything.
What if the given array is of length zero? In this case, we do not need to do anything.

Time: O(N^2)

Space: O(N)

 1 class Solution(object):
 2   def solve(self, array):
 3     """
 4     input: int[] array
 5     return: int[]
 6     """
 7     # write your solution here
 8     if array is None or len(array) <= 1:
 9       return array
10     for i in range(len(array) - 1):
11       min_index = i
12       for j in range(i + 1, len(array)):
13         if array[j] < array[min_index]:
14           min_index = j
15       array[i], array[min_index] = array[min_index], array[i]
16     return array