Lily's Homework

  • + 1 comment

    Hey, counter example here:

    5
    3 4 2 1 5
    

    the expected output is 3, but with your logic:

    3 4 2 1 5
    1 2 3 4 5
    ---------
    1 1 1 1 0
    
    &&
    
    3 4 2 1 5
    5 4 3 2 1
    ---------
    1 0 1 1 1
    

    the output is ceil(4/2) = 2

    The flaw in your logic is that you assume that two different positions between the input array and the sorted input array are fixed with only 1 swap, when in reality it's a bit more complex than that.