Given an unsorted sequence, please sort it using insertion sort and selection sort respectively, and compare which algorithm is better.

Submit: 1041 Solved: 274

[Submit][Status][Web Board]

Given an unsorted sequence, please sort it using insertion sort and selection sort respectively, and compare which algorithm is better.

The first line contains an integer \(T\), representing the number of test cases.

For each test case, the first line will be an integer \(n\) showing the length of array. Then there are n integers.

For all cases, \(1 ≤ T ≤ 10, 2 ≤ n ≤ 10^3\)

The secondline, you need to output the better algorithm in this case.

if the insertion sort is better, print "Insertion Sort wins!" (without quotation marks)

```
2
3
1 3 2
3
3 2 1
```

```
1 2 3
Insertion Sort wins!
1 2 3
Selection Sort wins!
```