9.4: Unit Summary

Last updated
Save as PDF

Page ID: 47934

\( \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 presented six sorting algorithms based on insertion, selection, merge and partition methods. The insertion sort based algorithms, the insertion sort and binary tree sort have quadratic performance in the worst case, thus may be suited to sorting small data collections. The selection based sorting algorithms, the selection sort and the heap sort, give slight improvement in run time efficiency, though, generally also suffer from the quadratic worst case performance.

The merge sort and quick sort algorithm are based on merge and partition approach respectively, and both algorithms use the divide-and-conquer strategy. They have comparable run time complexity on average of Θ(n lg n). Quick sort is a well established sorting algorithm whose worst-case running time is Θ(n2) and expected running time is Θ(n lg n) where the constants hidden in Θ(n lg n) are small.

Unit Assessment

Check your understanding!

Programming Exercises

Instructions

A merge of two sorted lists, e.g. merge( [1;4;9;12], [2;3;4;5;10;13]) leads to a new sorted list [1;2;3;4;4;5;9;10;12;13], made up from the elements of the arguments in the merge function. This operation can be declared so that it has a worst-case running time proportional to the sum of the length of the argument lists. Declare such a function. Test this function so that you are sure that all branches of the declaration work correctly.

Answers

mailto:njulumi@gmail.com

Grading Scheme

As per the offering Institution grading policy.

Unit Readings and Other Resources

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