Module gopy.sorting.selection

"""
Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place 
comparison-based algorithm in which the list is divided into two parts, the sorted 
part at the left end and the unsorted part at the right end. Initially, the sorted 
part is empty and the unsorted part is the entire list.

The smallest element is selected from the unsorted array and swapped with the 
leftmost element, and that element becomes a part of the sorted array. This process 
continues moving unsorted array boundary by one element to the right.

This algorithm is not suitable for large data sets as its average and worst case 
complexities are of Ο(n2), where n is the number of items.

### Algorithm

```
Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted
```

### Pseudocode

```python
procedure selection sort 
   list  : array of items
   n     : size of list

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i    
  
      /* check the element to be minimum */

      for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
        
end procedure
```
"""
def sort(array):
    for i in range(0, len(array) - 1):
        smallest = i
        for j in range(i + 1, len(array)):
            if array[j] < array[smallest]:
                smallest = j
        array[i], array[smallest] = array[smallest], array[i]
    return array