Trace two sorting algorithms

A youth sports club needs its members’ ages in ascending order. Sort 1 and Sort 2 both change the given list in place. Follow the algorithms in Listing 1 or their Python versions in Listing 2 for each list in the tables below.

A pass is one complete run of the outer loop on line 5 of Listing 1 (a) or line 5 of Listing 1 (b). List positions start at 0, and length(Ages) is the number of ages in the list. In both listings, from ... to ... includes both endpoints. The procedure swap(Ages, i, j) exchanges the ages at positions i and j in the same list. Sort 1 stops after a pass with no swaps. Sort 2 always makes three passes for a list of four ages.

Sort 1 in Listing 1 (a) compares neighboring ages. Sort 2 in Listing 1 (b) selects the smallest age in the part of the list that has not yet been placed in order. Both pseudocode listings use Pass to count passes, starting at 1. The variables i and j are list positions, and min is the position of the smallest age found so far. In Sort 2, pass 1 places the smallest age at position 0, pass 2 places the next smallest at position 1, and so on.

Listing 1: Two algorithms for sorting a list of ages in ascending order.

(a) Sort 1 compares adjacent ages and moves larger ages toward the end of the list. Each pass starts at the outer loop on line 5.

Input: Ages
Output: Ages in ascending order
Start
  Set n to length(Ages)
  For Pass from 1 to n - 1
    Set Swapped to False
    For i from 0 to n - Pass - 1
      If Ages[i] > Ages[i + 1]
        Call swap(Ages, i, i + 1)
        Set Swapped to True
      End If
    End For
    # Record Ages after this pass.
    If Swapped = False
      Exit For
    End If
  End For
  Output Ages
End

(b) Sort 2 selects the smallest remaining age and moves it to the next position. Each pass starts at the outer loop on line 5.

Input: Ages
Output: Ages in ascending order
Start
  Set n to length(Ages)
  For Pass from 1 to n - 1
    Set i to Pass - 1
    Set min to i
    For j from i + 1 to n - 1
      If Ages[j] < Ages[min]
        Set min to j
      End If
    End For
    Call swap(Ages, i, min)
    # Record Ages after this pass.
  End For
  Output Ages
End

The Python versions use range, which stops before its second argument. Both functions call swap(ages, i, j), the procedure you will write below. In Sort 2, min_i is the position of the smallest age found so far. Each function changes the original list and returns that list.

Listing 2: Python versions of Sort 1 and Sort 2 for a list of ages.

(a) Sort 1 in Python compares neighboring ages and stops after a pass with no swaps. Each pass starts at the outer loop on line 3.

def sort_1(ages):
    n = len(ages)
    for pass_no in range(1, n):
        swapped = False
        for i in range(n - pass_no):
            if ages[i] > ages[i + 1]:
                swap(ages, i, i + 1)
                swapped = True
        # Record ages for this pass.
        if not swapped:
            break
    return ages

(b) Sort 2 in Python places the smallest remaining age at the next position. Each pass starts at the outer loop on line 3.

def sort_2(ages):
    n = len(ages)
    for pass_no in range(1, n):
        i = pass_no - 1
        min_i = i
        for j in range(i + 1, n):
            if ages[j] < ages[min_i]:
                min_i = j
        swap(ages, i, min_i)
        # Record ages for this pass.
    return ages

Copy each list before running the second algorithm, so both start with the same ages. Record the whole list after each pass, even if no values changed. Write Stopped if an algorithm does not make that pass. Table 1 shows the first pass for [16, 14, 15, 17]. Complete that table and Table 2 and Table 3.

Table 1: Trace to complete for the ages 16, 14, 15, and 17. The first pass is worked out for both algorithms.

Pass	Sort 1 list after the pass	Sort 2 list after the pass
Start	`[16, 14, 15, 17]`	`[16, 14, 15, 17]`
1	`[14, 15, 16, 17]`	`[14, 16, 15, 17]`
2
3

Table 2: Trace to complete for the ages 14, 15, 16, and 17. Record when each algorithm stops.

Pass	Sort 1 list after the pass	Sort 2 list after the pass
Start	`[14, 15, 16, 17]`	`[14, 15, 16, 17]`
1
2
3

Table 3: Trace to complete for the ages 17, 16, 15, and 14. Record the list after every pass.

Pass	Sort 1 list after the pass	Sort 2 list after the pass
Start	`[17, 16, 15, 14]`	`[17, 16, 15, 14]`
1
2
3

For each input, count the passes each algorithm makes. Did they produce the same sorted list? Which algorithm stops earlier for some inputs, and why? Name the algorithm that compares neighbors and the one that repeatedly selects the smallest remaining age. Use the first pass of the mixed list to explain why their intermediate lists differ.

Then write the Python procedure swap(ages, i, j) used by both algorithms. Assume that i and j are valid list positions. Exchange those two ages in the original list, leave every other age unchanged, and return nothing. Use simple assignments and a temporary variable rather than Python’s multiple assignment. The procedure must also work when i and j are the same position.

Hint

For Sort 1, keep track of whether any swap occurred during the pass. For Sort 2, update min while scanning; swap only after the scan ends.

To see the lists change, open the Sort 1 animation or the Sort 2 animation. In VisuAlgo, choose Exploration Mode, enter the ages under Create(A), then choose Sort. Use the playback controls to follow the comparisons and swaps one step at a time.