sorting-visualizer

About sorting-visualizer

sorting-visualizer is a visualizer for the most popular sorting algorithms built using pygame in Python. It is a graphical-user interface based project.

The project sorts an array of pygame.rect() of increasing lengths (in ascending order). Before each trial, the array must be shuffled. The sorting algorithm can also be changed.

Where the 'sorting-visualization' happens

The visualizer is built using an interface between Python and C (using the ctypes package). After the rectangles are shuffled, an array of their heights is passed to the chosen C-sorting function. The custom sorting function sorts it, and returns the combinations of traversals/swaps one needs to do to sort the list. These are then passed to the pygame visualization functions to draw on the screen.

The Python-C interface can be found on Line 148 of main.py:

def sort_samples(algorithm: int, heights: list[int]) -> list[list[int]]:
    c_array = (ctypes.c_int * NUM)(*heights)

    SORTING_LIBS[algorithm].sort.argtypes = (ctypes.POINTER(ctypes.c_int * NUM), ctypes.c_int)
    SORTING_LIBS[algorithm].sort.restype = ctypes.POINTER(ctypes.c_int * 2*NUM**2)

    swaps_ptr = SORTING_LIBS[algorithm].sort(c_array, ctypes.c_int(NUM))
    swaps_list: list[list[int]] = []

    for i, long in enumerate(swaps_ptr.contents):
        swap = [long[0], long[1]]
        if i != 0 and swaps_list[-1] == swap == [0, 0]:
            break
        swaps_list.append(swap)

    return swaps_list

Features

The following features are provided in the visualizer:

• Ability to shuffle the samples any number of times before sorting
• Ability to change the sorting algorithm before each trial

Sorting Agorithms implemented

Currently, fourteen different popular sorting algorithms are supported. These are:

• Bubble Sort
• Cocktail Shaker Sort
• Cycle Sort
• Odd Even Sort
• Selection Sort
• Reverse Selection Sort: Selection Sort in reverse
• Double Selection Sort: Bidirectional Selection Sort
• Insertion Sort
• Quick Sort using the Lomuto Partition Scheme
• Merge Sort using the Top-Down Implementation
• Heap Sort using the Floyd's Heap Construction Algorithm
• Tim Sort using above mentioned Insertion and Merge
• Bitonic Sort
• Stooge Sort

Controls

• Space: Shuffle the samples
• Enter: Start the sorting algorithm
• S: Change the sorting algorithm
• R: Arrange the samples in reverse order of sorting

Footnotes

• Do not close the application while the algorithmis being visualized as ongoing system processes may cause the app to crash.
• The algorithm cannot be changed while the samples are being sorted.
• The samples cannot be sorted when they are already in sorted order.

Run

To run the visualizer, clone the repository on your device, navigate to the folder, and execute:

make
python3 ./src/py/main.py

Future Plans

• Ability to select ascending/descending order for sorting
• Add more interesting algorithms (non-exhasutively):
  • Comb Sort
  • Smooth Sort
• Ability to dynamically change the number of samples
• Speed up the visualization process if possible
• Add a timer/counter that counts the time elapsed in sorting, the number of array traversals, and the number of swaps (difficult to implement due to Python-C interfacing)