Software Design and Development
Home > Software Design and Development > Core > Software Development Cycle > Standard Algorithms: Sorting
Sorting algorithms used in software solutions
This material describes and implements the standard sorting algorithms required by the syllabus for use in software solutions using pseudocode.
Syllabus outcomes
H4.2 A student applies appropriate development methods to solve software problems.
H4.3 A student applies a modular approach to implement well-structured software solutions and evaluates their effectiveness.
H5.2 A student creates and justifies the need for various types of documentation required for a software solution.
H5.3 A student selects and applies appropriate software to facilitate the design and development of software solutions.
Students must learn to recognise the logic of specified standard approaches, apply those standard approaches as part of the solution to a complex problem and document the logic required to solve a problem using both pseudocode and flowcharts.
The following headings may help you navigate:
Sorting
Sorting is ordering the elements of an array into ascending (or descending) order. Three sorting algorithms are specified in the syllabus, the bubble sort, the selection sort and the insertion sort. These standard sorting algorithms required by the syllabus are "insitu" sorts. This means that the elements are manipulated into the required order within the original array. There are other types of sorting which use additional or auxillary arrays but insitu sorts are quicker because they are processed in memory. All sorting routines require swapping of one element with another. A module, traditionally called SWAP, is used in the sorts.
Swapping elements in an array
The assignment of variables is often confused with equivalence in mathematics because the equals sign is often used for assignment. Assigning means "put the value on the right hand side of the = into the variable on the left hand side". Any data in the left hand variable is overwritten by the value in the right hand variable (or the value to which the right hand expression evaluates). Once overwritten it can not be retrieved. If we swap values mathematically we would say: Let x = y and Let y = x. We hold the values in our memory while we perform the swap on paper. If we do this in computing the first assignment overwrites the value in the variable x with that in y. The second assignment then places the new value of x (now y) in the variable y. As a result both variable x and variable y contain the same value (y). To avoid this problem we set up a temporary variable, traditionally called temp, and we store the value of x in temp while we affect the swap.
Bubble sort
Objective
In a bubble sort we make many passes through the unsorted array swapping the elements in successive pairs of index positions to the required order. The values "bubble" to their sorted position.
Concept
We read the elements in the first and second index positions in the array and compare these elements. If they are in the correct order relative to each other, leave them, but if they are not, swap the values. Then read the second and third index positions. If the elements are in the correct order relative to each other, leave them, but if they are not swap them. This continues for one full pass, or traverse, through the array. We need to make many passes through the array to sort it and it is only when we have made a pass which did not require any pairs to be swapped that we know the array is sorted. Alternatively we can be sure the array is sorted if we make as many passes through the array as there are elements in the array but this could be inefficient because sorting could be complete in less than this number of passes. The number of passes required will depend on the extent to which the array was unsorted. In the worst case, the array was sorted in reverse order to that required, and to sort it, it will take as many passes through the array as there are elements in the array minus one to sort.
Algorithm to sort in ascending order.
Activity 1: Bubble sort
- Using the test data below tabulate the values
in the array at each pass of a bubble sort.
Test data BUBBLESORT
Index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Element
11
3
12
5
13
4
6
14
7
8
15
1
9
2
10
- Rewrite the algorithm to include a test which ends the routine when no pairs have been swapped during a pass.
- How many passes through the array will be made if the test for “no pairs swapped” was implemented with the test data.
Selection sort
Objective
To sort the array by selecting the target element (maximum or minimum) in the array and swapping it into the appropriate index position (last or first) in the array.
Concept
In the selection sort we select the maximum (or minimum) element in the array and swap it to the maximum (or minimum) index position in the array. The array now falls into two parts, a sorted part and an unsorted part. Initially the sorted part is just one element and the unsorted part is the rest of the array. We then read the unsorted part of the array, select the maximum (or minimum) element in the unsorted part and swap it to the next index position in the sorted part. The sorted part of the array increases by one and the unsorted part decreases by one each time we swap.
Algorithm to sort in ascending order
Activity 2: Selection sort
- Using the test data below draw a table showing the
values in each index position of the array during each pass of a selection
sort.
Test data SELECTIONSORT
Index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
element
11
3
12
5
13
4
6
14
7
8
15
1
9
2
10
Insertion sort
Objective
The aim of the insertion sort is to take the last element in the unsorted part of the array and insert it into the correct position in the sorted part of the array.
Concept
Firstly, the array is divided into two parts, a sorted and an unsorted part. The sorted part contains only one element, the last element, whatever value it may contain. We then take the element in the adjacent index position of the unsorted part and insert it into the correct position in the sorted part by shuffling the values in the sorted part to make space for it as necessary. The sorted part increases by one and the unsorted part decreases by one each time an element is inserted.
Algorithm
This algorithm assumes we are sorting in ascending order starting with the minimum value.
Activity 3: Insertion sort
- Using the test data below draw a table showing the
values in each index position of the array during each pass of an insertion
sort.
Test data INSERTIONSORT
Index
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
element
11
3
12
5
13
4
6
14
7
8
15
1
9
2
10
Bibliography
Brookshear, J. Glenn. (1994) Computing Science an overview Fourth Edition, The Benjamin/Cummings Publishing Company.
Stephens, R (1998) Ready-to-Run Visual Basic Algorithms Second Edition,
Wiley Computer Publishing,
Further Resources
Fowler, A (2000) Software Design and Development, First Edition, Heinemann
This work was prepared by
Jennifer Thomson
|