Quick Sort Visualizer

COSC 2306: Data Programming - Partitioning Strategy

Pivot Value --
Pivot
Left Mark
Right Mark
Final Position
Press "Step Forward" to begin the partitioning process.

Algorithm Trace

# Quick Sort ready.
# Strategy: Use first element as pivot. Partition using left/right marks.

Controls

Python Implementation (Slide 17)
def partition(a_list, first, last):
    pivot_value = a_list[first]
    left_mark = first + 1
    right_mark = last
    done = False
    while not done:
        while left_mark <= right_mark and \
              a_list[left_mark] <= pivot_value:
            left_mark += 1
        while a_list[right_mark] >= pivot_value and \
              right_mark >= left_mark:
            right_mark -= 1
        if right_mark < left_mark:
            done = True
        else:
            # swap left/right marks
            a_list[left_mark], a_list[right_mark] = \
                a_list[right_mark], a_list[left_mark]
    # swap pivot and right_mark
    a_list[first], a_list[right_mark] = \
        a_list[right_mark], a_list[first]
    return right_mark