MergeAlgorithms.py

#
# A demonstration of the three sorting algorithms in the GCSE Computer Science syllabus
# using the LEGO PRIME matrix display.
#
from hub import light_matrix
import runloop
import random

#
# Shuffle a list
#
def shuffle(list):
    output = []
    while(len(list) > 0):
        index = random.randrange(0,len(list))
        value = list[index]
        list.remove(value)
        output.append(value)
    return output 

#
# Swap the element at position pos in the list with the next element
#
def swap_with_next(list,pos):
    tmp = list[pos]
    list[pos] = list[pos + 1]
    list[pos + 1] = tmp

#
# Animate the state of the list higlighting any cells in the highlights list
#
async def animate_comparison(values, highlights):
    highlighted = [100 if x in highlights else values[x] for x in range(25)]
    light_matrix.show(highlighted)
    await runloop.sleep_ms(50)


async def animate_result_step(values):
    light_matrix.show(values)
    await runloop.sleep_ms(10)

#
# Demonstrate the bubble sort
#
async def bubble_sort(values):
    for top in range(25):
        for pos in range(24-top):
            await animate_comparison(values,[pos,pos+1])
            if(values[pos] > values[pos + 1]):
                swap_with_next(values, pos)
            await animate_result_step(values)

#
# Demonstrate the merge sort, using a depth first recursive algorithm.
# GCSE teaches a breadth first algorithm, but depth first is easier to code.
#
async def merge_sort(list, start, end):
    if(end - start is 1):
        return
    if(end - start is 2):
        await animate_comparison(list,[start,start+1])
        if(list[end-1] < list[start]):
            swap_with_next(list,start)
        await animate_result_step(list)
        return
    
    # Recursively sort the two half lists
    mid = (start + end) >> 1
    await merge_sort(list, start, mid)
    await merge_sort(list, mid, end)

    # Now merge them
    tmp = list.copy()
    outptr = start
    read1 = start
    read2 = mid
    while(outptr < end):
        await animate_comparison(list,[read1,read2])
        value1 = tmp[read1] if read1 < mid else 10000
        value2 = tmp[read2] if read2 < end else 10000
        if(value1 < value2):
            list[outptr] = value1
            read1 = read1 + 1
        else:
            list[outptr] = value2
            read2 = read2 + 1
        outptr = outptr + 1
        await animate_result_step(list)

#
# Demonstrate insertion sort.
# The output list is maintained at 25 long here so that it can be used
# to populate the display.
#
async def insertion_sort(list):
    tmp = list.copy()
    list = [0 for x in range(25)]
    for ptr in range(25):
        value = tmp[ptr]
        insertion_point = 0
        while(list[insertion_point] < value and insertion_point < ptr):
            await animate_comparison(list, [insertion_point])
            insertion_point = insertion_point + 1
        list.insert(insertion_point, value)
        list.pop() # maintain 25 long
        await animate_result_step(list)

async def main():
    values = [int(x*3) for x in range(25)]
    light_matrix.show(values)
    await runloop.sleep_ms(1000)

    while True:
        # Bubble Sort
        await light_matrix.write('Bubble Sort')
        values = shuffle(values);
        light_matrix.show(values)
        await bubble_sort(values)
        await runloop.sleep_ms(1000)

        # Merge Sort
        await light_matrix.write('Merge Sort')
        values = shuffle(values)
        light_matrix.show(values)
        await merge_sort(values, 0, 25)
        await runloop.sleep_ms(1000)

        # Insertion Sort
        await light_matrix.write('Insertion Sort')
        values = shuffle(values)
        light_matrix.show(values)
        await insertion_sort(values)
        await runloop.sleep_ms(1000)

runloop.run(main())