SDD Skills - Searches and Sorts

[Justin_L]

SDD Skills - Searches and Sorts

In the fourth part of the Software Skills Series, we'll be looking at searching and sorting!

Searching and sorting is an integral part of the Software Design and Development course, so much so that NESA has provided standard algorithms for these functions in the course specifications. While these are included below, this article aims to give a more conceptual understanding of how these algorithms work, when to use them, and how these relate to an exam context.

In your trial or HSC exams, you will be expected to know how write your own searches and sorts. Commonly you may be asked to identify and modify scaffold code in multiple choice or short answer questions.

The Prelim & HSC SDD Course only deal with searches and sorts on numerical datasets such as arrays of numbers, but we’ll be touching on other types of data as well to give you a broader understanding of these how these algorithms work.
SEARCHING
If I asked you to find certain card within a large, randomised deck of numbered cards, how would you do it?
Assuming that you can only check one card at a time, the simplest and most straightforward answer would probably be to check each card one by one until you reach the card you’re looking for.

In SDD, this is called a Linear Search – you linearly go through the deck until you reach the card you need. This is the simplest search, and has the advantage that it works on any dataset – regardless of whether it is sorted or unsorted.

Linear Search - Software Design & Development Course Specifications

BEGIN LinearSearch
    Let i = 1
    Let FoundIt = false
    Get RequiredName

    WHILE FoundIt is false AND i <= number of names
        IF Names(i) < > RequiredName THEN
            i = i + 1
        ELSE
            Let FoundIt = true
        ENDIF
    ENDWHILE

    IF FoundIt THEN
        Display “Name found at position ” i
    ELSE
        Display “Required person not found”
    ENDIF

END LinearSearch

But let’s say we change the up the question. What if I asked you to find a certain numbered card within a deck of cards in numbered order? (Going from lowest to highest) 

While you could go through each card in sequence, what you would probably do is to split the deck where you think the card would be, check if you need to go higher or lower, then repeat. This would significantly decrease the number of cards you need to check, and allow you to get back to working on your SDD Major Work (which you should definitely post about here!).

While intuitive to us, this is actually itself also a formalised way of searching called a Binary Search – the program halves the deck, finds the half containing the card, and halves again until it finds the required card. While this approach is significantly faster (which we’ll discuss in our next article on Big O Notation), it will only work on SORTED datasets, generally meaning numerical ones.

Binary Search - Software Design & Development Course Specifications

BEGIN BinarySearch
    Let Lower = 1
    Let Upper = number of elements in the array
    Let FoundIt = false
    Get RequiredName

    REPEAT
        Let Middle = (Upper + Lower) / 2
        Let Middle = integer part of Middle

        IF RequiredName = Name (Middle) THEN
            Let FoundIt = true
            Let PositionFound = Middle
        ELSE
            IF RequiredName < Name (Middle) THEN
                Let Upper = Middle – 1
            ELSE
                Let Lower = Middle + 1
            ENDIF
        ENDIF

    UNTIL FoundIt OR Lower > Upper

    IF FoundIt THEN
        Display “Required name found at ” PositionFound
    ELSE
        Display “Required name ” RequiredName “ not found.”
    ENDIF

END BinarySearch

SORTS
So to take advantage of the massive speed increases of a binary search, we would need to sort our data. Sorting our data has a large number of benefits, and you will very likely be asked to identify different types of sorts in the HSC exam.
While it’s unlikely you’ll be asked to implement a sort from scratch, I would highly recommend you have a go at implementing each of these sorts using pseudocode or a programming language of your choice as NESA has a habit of asking about these in the multiple choice.

First up, we have the humble Bubble Sort. This is the simplest sort, both conceptually and implementation wise which is why it’s often the first sort taught to students.

To simulate this sort, line up your deck of cards in a random numerical order. Decide whether you want an ascending or descending sort – for this example, I’ll use an ascending sort.

Compare the first two cards. Swap them if the first card is larger, then repeat for the next two until you reach the end. Then repeat from the beginning until the dataset is sorted. If you do this exercise, you’ll notice that the largest element will always “bubble” to the end of set, followed by the next largest and so on.

Bubble Sort - Software Design & Development Course Specifications

BEGIN BubbleSort
    Let Last = number of names in the array
    Let Swapped = true

    WHILE Swapped = true
        Let Swapped = false
        Let i = 1

        WHILE i < Last
            IF Name (i) > Name (i+1) THEN
                Swap (Name (i), Name (i+1))
                Let Swapped = true
            ENDIF
            Increment i
        ENDWHILE

        Decrement Last

    ENDWHILE

END BubbleSort

Next up, we have Selection Sort and Insertion Sort. The reasons I’m grouping these two together is because it is very easy to get confused between the two. Particularly in an exam environment where you won’t explicitly be told what it is, it’s extremely easy to mix them up which is why I’ll use this opportunity to emphasise the key difference between the two.

A Selection Sort selectively searches the unsorted part of the array to swap the next largest or smallest element into the sorted part

Selection Sort - Software Design & Development Course Specifications

Sourced from the Software Design & Development Course Specifications

An Insertion Sort sequentially takes unsorted elements and places them into the sorted part of the array using a search by shifting the elements.

Insertion Sort - Software Design & Development Course Specifications

Sourced from the Software Design & Development Course Specifications

In both cases, selection and insertion sort effectively split the dataset into a sorted and unsorted component, then moves elements to expand the sorted section until the entire dataset in sorted.
Exam Tips
So how will you be applying this in an exam context? While you can be asked to straight up write one of these sorts, here is a very non-comprehensive list of some common exam style questions:

-  Identifying the most appropriate search for a sample dataset
-  Explaining the differences or process of a search
-  Identifying a sort from pseudocode or flowchart.
-  Identifying whether a sort is ascending or descending
-  Finding a particular sort from a selection of pseudocode extracts
Summary
Hopefully this article was a useful conceptual overview to searching and sorting in the HSC Software Design & Development course! If you have time, I would highly recommend getting a pack of cards/numbers and going over these algorithms in real life to get a feel for how they work.

If you have any questions, feel free to post them below or in the software questions thread and I’ll provide some feedback!

Otherwise, check out some of the other articles in the SDD Skills Series from the main thread here!