SDD Skills - Searches and SortsIn 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.
SEARCHINGIf 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
SORTSSo 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 TipsSo 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
SummaryHopefully 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!