Gnome sort é um algoritmo de ordenação semelhante ao <a href="https://rosettacode.org/wiki/Insertion_sort" target="_blank" rel="noopener noreferrer nofollow">Insertion sort</a>, exceto que mover um elemento para sua posição correta é realizado por uma série de trocas, como no <a href="https://rosettacode.org/wiki/Bubble" target="_blank" rel="noopener noreferrer nofollow">Bubble Sort</a>. O pseudocódigo para o algoritmo é: <pre><b>function</b> <i>gnomeSort</i>(a[0..size-1]) i := 1 j := 2 <b>while</b> i &#x3C; size <b>do</b> <b>if</b> a[i-1] &#x3C;= a[i] <b>then</b> <i>/// for descending sort, use >= for comparison</i> i := j j := j + 1 <b>else</b> <b>swap</b> a[i-1] <b>and</b> a[i] i := i - 1 <b>if</b> i = 0 <b>then</b> i := j j := j + 1 <b>endif</b> <b>endif</b> <b>done</b> </pre>

Escreva uma função para implementar o pseudocódigo acima. A função deve retornar o array ordenado.

Critérios de Aceitação:

Testes:

• `gnomeSort` deve ser uma função.
• `gnomeSort([25, 32, 12, 7, 20])` deve retornar um array.
• `gnomeSort([25, 32, 12, 7, 20])` deve retornar `[7, 12, 20, 25, 32]`.
• `gnomeSort([38, 45, 35, 8, 13])` deve retornar `[8, 13, 35, 38, 45]`.
• `gnomeSort([43, 36, 20, 34, 24])` deve retornar `[20, 24, 34, 36, 43]`.
• `gnomeSort([12, 33, 26, 18, 1, 16, 38])` deve retornar `[1, 12, 16, 18, 26, 33, 38]`.
• `gnomeSort([3, 39, 48, 16, 1, 4, 29])` deve retornar `[1, 3, 4, 16, 29, 39, 48]`.