Implemente um *comb sort*. O Comb Sort é uma variante do Bubble Sort. Assim como ordenação Shell Sort, a Comb Sort aumenta a diferença usada nas comparações e trocas. Dividir a diferença por $(1-e^{-\\varphi})^{-1} \\approx 1,247330950103979$ funciona melhor, mas 1,3 pode ser mais prático. Algumas implementações usam a ordenação de inserção, já que a diferença é menor do que uma certa quantidade. Variantes: <ul> <li>Combsort11 makes sure the gap ends in (11, 8, 6, 4, 3, 2, 1), which is significantly faster than the other two possible endings.</li> <li>Combsort with different endings changes to a more efficient sort when the data is almost sorted (when the gap is small). Comb sort with a low gap isn't much better than the Bubble Sort.</li> </ul> Pseudocódigo: <pre><b>function</b> combsort(<b>array</b> input) gap := input<b>.size</b> <i>//initialize gap size</i> <b>loop until</b> gap = 1 <b>and</b> swaps = 0 <i>//update the gap value for a next comb. Below is an example</i> gap := int(gap / 1.25) <b>if</b> gap &#x3C; 1 <i>//minimum gap is 1</i> gap := 1 <b>end if</b> i := 0 swaps := 0 <i>//see <a href='https://rosettacode.org/wiki/Sorting_algorithms/Bubble_sort' target='_blank'>Bubble Sort</a> for an explanation</i> <i>//a single "comb" over the input list</i> <b>loop until</b> i + gap >= input<b>.size</b> <i>//see <a href='https://rosettacode.org/wiki/Sorting_algorithms/Shell_sort' target='_blank'>Shell sort</a> for similar idea</i> <b>if</b> input[i] > input[i+gap] <b>swap</b>(input[i], input[i+gap]) swaps := 1 <i>// Flag a swap has occurred, so the</i> <i>// list is not guaranteed sorted</i> <b>end if</b> i := i + 1 <b>end loop</b> <b>end loop</b> <b>end function</b> </pre>

Escreva uma função que ordene um determinado array usando uma ordenação de pente.

Critérios de Aceitação:

Testes:

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