Selection sort é outro algoritmo de ordenação popular ensinado na maioria dos cursos de ciência da computação. Este algoritmo funciona encontrando repetidamente o menor elemento da porção não ordenada da lista e trocando-o com o primeiro elemento não ordenado. Ele começa selecionando o valor mínimo em toda a lista e trocando-o com o primeiro elemento. Então ele se move para a segunda posição, encontra o menor valor nos elementos restantes não ordenados e o troca com o segundo elemento. Este processo continua, avançando pela lista um elemento de cada vez, até que toda a lista esteja ordenada. A ordenação por seleção resulta em uma complexidade de tempo quadrática nos cenários de melhor, médio e pior caso. A complexidade de espaço será constante O(1) porque a ordenação é feita in loco e uma quantidade constante de memória está sendo usada independentemente do tamanho da lista. Objetivo: Cumprir as user stories abaixo e fazer todos os testes passarem para completar o laboratório. Histórias de Usuário: 1. Você deve definir uma função chamada selection_sort. 1. Sua função selection_sort deve ter um parâmetro que representa a lista de itens. 1. Sua função selection_sort deve receber uma lista e ordenar os itens no local do menor para o maior. 1. Sua função selection_sort deve modificar a lista de entrada in-place e retorná-la assim que estiver ordenada. 1. Sua função selection_sort deve seguir o algoritmo de ordenação por seleção, trocando o menor elemento da parte não ordenada da lista com o primeiro elemento não ordenado. 1. Sua função selection_sort não deve realizar trocas desnecessárias quando o menor elemento já estiver na posição correta. 1. Sua função selection_sort não deve usar nem o método embutido sort() nem a função sorted().

Testes:

• Você deve ter uma função chamada `selection_sort`.
• Sua função `selection_sort` deve ter um parâmetro.
• Você não deve importar nenhum módulo ou usar métodos de ordenação embutidos no seu código.
• Seu `selection_sort` deve retornar a mesma lista que a lista de entrada.
• Seu `selection_sort` deve modificar a lista de entrada in-place. Você não deve usar nenhum método que adicione ou remova itens da lista.
• Sua função `selection_sort` deve seguir o algoritmo de ordenação por seleção, trocando o valor mínimo na parte não ordenada da lista com o primeiro elemento não ordenado. Evite trocas desnecessárias quando o valor mínimo já estiver na posição correta.
• `selection_sort([33, 1, 89, 2, 67, 245])` deve retornar `[1, 2, 33, 67, 89, 245]`.
• `selection_sort([5, 16, 99, 12, 567, 23, 15, 72, 3])` deve retornar `[3, 5, 12, 15, 16, 23, 72, 99, 567]`.
• `selection_sort([1, 4, 2, 8, 345, 123, 43, 32, 5643, 63, 123, 43, 2, 55, 1, 234, 92])` deve retornar `[1, 1, 2, 2, 4, 8, 32, 43, 43, 55, 63, 92, 123, 123, 234, 345, 5643]`.
• Sua função `selection_sort` deve ordenar corretamente qualquer lista de números.