1.1125 Given the unsorted list: Juan, Bill, Alice, Teresa, Victor, Fred, Donna

Show the complete process of sorting the list using a BUBBLE-DOWN sort WITH a flag

PASS 1:

1. Juan, Bill, Alice, Teresa, Victor, Fred, Donna (Swap)

2. Juan, Bill, Alice, Teresa, Victor, Donna, Fred (Swap)

3. Juan, Bill, Alice, Teresa, Donna, Victor, Fred (Swap)

4. Juan, Bill, Alice, Donna, Teresa, Victor, Fred (Don’t Swap)

5. Juan, Bill, Alice, Donna, Teresa, Victor, Fred (Swap)

6. Juan, Alice, Bill, Donna, Teresa, Victor, Fred (Swap)

Alice, Juan, Bill, Donna, Teresa, Victor, Fred (The list at the end of the pass)

PASS 2:

7. Alice, Juan, Bill, Donna, Teresa, Victor, Fred (Swap)

8. Alice, Juan, Bill, Donna, Teresa, Fred, Victor (Swap)

9. Alice, Juan, Bill, Donna, Fred, Teresa, Victor (Don’t Swap)

10. Alice, Juan, Bill, Donna, Fred, Teresa, Victor (Don’t Swap)

11. Alice, Juan, Bill, Donna, Fred, Teresa, Victor (Swap)

Alice, Bill, Juan, Donna, Fred, Teresa, Victor (The list at the end of the pass)

PASS 3:

12. Alice, Bill, Juan, Donna, Fred, Teresa, Victor (Don’t Swap)

13. Alice, Bill, Juan, Donna, Fred, Teresa, Victor (Don’t Swap)

14. Alice, Bill, Juan, Donna, Fred, Teresa, Victor (Don’t Swap)

15. Alice, Bill, Juan, Donna, Fred, Teresa, Victor (Swap)

Alice, Bill, Donna, Juan, Fred, Teresa, Victor (The list at the end of the pass)

PASS 4:

16. Alice, Bill, Donna, Juan, Fred, Teresa, Victor (Don’t Swap)

17. Alice, Bill, Donna, Juan, Fred, Teresa, Victor (Don’t Swap)

18. Alice, Bill, Donna, Juan, Fred, Teresa, Victor (Swap)

Alice, Bill, Donna, Fred, Juan, Teresa, Victor (The list at the end of the pass)

* NOTE: Even though the list is sorted, without a flag, we must perform One pass to make sure we don’t make any swaps.

PASS 5:

19. Alice, Bill, Donna, Fred, Juan, Teresa, Victor (Don’t Swap)

20. Alice, Bill, Donna, Fred, Juan, Teresa, Victor (Don’t Swap)

And we are done. In this case we (only) saved one pass.