Suppose we have a new sorting algorithm that works as follows. Given array x, start at index i=0 and perform the followi

[answerhappygod]

Suppose We Have A New Sorting Algorithm That Works As Follows Given Array X Start At Index I 0 And Perform The Followi 1 (41.85 KiB) Viewed 20 times

Suppose we have a new sorting algorithm that works as follows. Given array x, start at index i=0 and perform the following steps: 1. if i=0, increment i, return to step 1 2. if i==len (x), stop (the list is sorted) 3. if x < x[i-1], swap them, and decrement i, return to step 1 4. if x 2 x[i-1], simply increment i, return to step 1 For example, if we were sorting [4, 3, 21, the steps would be: array i action [4, 3, 2] 1-0 i-0, so increment i [4, 3, 21 i-1 x[1] x [0], so swap and decrement i [3, 4, 21 1-0 10, increment i [3, 4, 21 1-1 x[1] x [0], so simply increment i [3, 4, 21 1-2 x [2] < x[1], so swap and decrement i 1-1 x[1] < x[0], so swap and decrement i i-0, increment i 1-0 [3, 2, 4] [2, 3, 4] [2, 3, 4] [2, 3, 4] [2, 3, 4] 1-1 x[1]> x[0], so simply increment i x [1], so simply increment i i=2 x [2] 1=3 list is sorted! For an array of length n, what is the approximate average complexity of this sort algorithm? In other words, what is the order (big-O notation) that best describes the typical number of swaps, as a function of n, expected in this algorithm. Show your work and/or thoroughly explain your answer. Lucky guesses will be marked zero.