4.3: Unit Summary

Last updated
Save as PDF

Page ID: 49951

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

This unit discussed the searching and sorting algorithms together with their examples. Searching which is about finding a particular item in a given list of items, and Sorting on the other hand which is the ordering in a particular way of some given data, were explained. For the searching, the sequential and binary searches were discussed. While for the sorting algorithm, insertion sort, shell sort and quicksort were discussed. Where possible algorithms that can be used to illustrate the two concepts were also introduced.

Unit Assessment

Check your understanding!

Question and answer

Instructions

Answer all the questions below:

Describe the quicksort algorithm.
Describe an insertion sorting algorithm.

Feedback

In quicksort, the steps performed are the following:
1. pick an element, called a pivot, from the list
2. reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way)
3. recursively sort the sub-list of lesser elements and the sub-list of greater elements
An algorithm that sorts by insertion takes the initial, unsorted sequence and computes a series of sorted sequences using the following rules:
1. the first sequence in the series is the empty sequence
2. given a sequence S(i) in the series, for 0<=i<n, the next sequence in the series, S(i + 1), is obtained by inserting the (i + 1)th element of the unsorted sequence S(i + 1) into the correct position in S(i)

Grading Scheme

The marks will be awarded as shown below

Question	Scores (marks)
1	Each 2 mark total mark is 6
2	Each line of explanation 2 marks; maximum 12
Total	18

Unit Readings and Other Resources

The readings in this unit are to be found at course level readings and other resources.