Sorting Algorithms

🎯 Try several sorting algorithms.

Sorting algorithms are among the most fundamental algorithms of all. In this exercise, you will gain a basic understanding of some of these algorithms.

This is an offline exercise.

Material

  • a deck of 16 playing cards per group (2-3 participants)

  • the pseudocode of the 4 algorithms

  • a stopwatch

  • paper to write down the time

Instructions

  • read the algorithm description carefully

  • shuffle the deck of cards

  • start the stopwatch

  • execute one of the algorithms

  • stop the clock as soon as all the cards are sorted

Selection Sort

  1. lay the cards in a row in front of you

  2. go through all the cards

  3. take the card with the smallest number and put it on the target pile

  4. repeat step 2 until all cards are sorted

Insertion Sort

  1. take a new card from the pile

  2. go through the already placed cards

  3. place the new card in the the correct position

  4. repeat steps 1 and 2 until all cards are sorted

Bubblesort

  1. lay out all cards in a row in front of you

  2. go through the cards from left to right

  3. if there is a smaller card to the right of a larger one, swap them

  4. repeat steps 2 and 3 until nothing changes in one pass

Mergesort

  1. divide the deck of cards into two equal piles

  2. sort each pile according to the mergesort method

  3. turn both piles upside down so that the smallest card is visible

  4. place the smaller card from one of the piles on the target pile

  5. Repeat step 4 until all cards are sorted.

Optional Goals

  • repeat the exercise with a small (8) and a large (16) deck of cards

  • count comparison and swap operations

  • implement one of the algorithms

  • measure the runtime with %timeit

Translated with www.DeepL.com