INN701 Lecture 3
Queensland University of Technology
CRICOS No. 00213J
CAB301 Algorithms and Complexity
Lecture 4 – Basic sorting algorithms
Maolin Tang
School of Computer Science
Queensland University of Technology
CRICOS No. 00213J
a university for the worldreal R 2
Aims of this lecture
• In this lecture we study three basic sorting algorithms
– Insertion sort
– Selection sort
– Bubble sort
CRICOS No. 00213J
a university for the worldreal R 3
References
• A. Levitin. Introduction to the Design and Analysis of Algorithms.
Addison-Wesley, third edition, 2012. Sections 3.1 and 4.1.
CRICOS No. 00213J
a university for the worldreal R 4
Sorting algorithms
• Sorting algorithms are also ‘comparison-based’
– The aim of a sorting algorithm is to arrange the items in a given
collection in a certain order
– The basic operation in sorting is either comparing items or
moving/swapping items
• Again we restrict ourselves to array-based algorithms here
• As well as their efficiency, we are also interested in the following
properties of sorting algorithms
– Can they be done in place or do they need temporary storage?
– Are they stable, i.e., are the relative positions of items with the
same label preserved?
CRICOS No. 00213J
a university for the worldreal R
An application of stable sorting algorithms
• Assume that you have an array of Person objects, each of which
has a first name class member and a family name class member.
Currently the person objects are randomly stored in an array. No
CompareTo method has been defined in the Person class. Now you
want to rearrange the Person objects such that they are in
alphabetical order (in dictionary order or in lexicographical order) by
their full name.
• We can use a stable sorting algorithm to solve this computational
problem. Firstly, we sort the Person objects in the array by *first
name*. Then, we sort the Person objects in the array by *family
name.
5
CRICOS No. 00213J
a university for the worldreal R
Insertion sort
• The basic idea behind the insertion sort is
1. Divide a list into two sections: a sorted section and an unsorted
section
2. From the first element to the last element in the unsorted
section:
• Remove it from the unsorted section;
• Insert it into the sorted section at a position such that after
the insertion the sorted section remains sorted.
6
CRICOS No. 00213J
a university for the worldreal R
Insertion sort
7
CRICOS No. 00213J
a university for the worldreal R
Insertion sort
• How to insert an item into a sorted list?
8
CRICOS No. 00213J
a university for the worldreal R
Insertion sort
9
CRICOS No. 00213J
a university for the worldreal R
Insertion sort
Demo – Insertion sort with Romanian fork dance
(0:00 – 2:25)
• Notes:
– Each dancer represents an element in an array
– Those dancers who are facing you represent the data elements
that are in the sorted section
– Those dancers who have their back facing you represent the
data elements that in the unsorted section
– When a pair of dancers turn to face each other, this represents
the two corresponding elements are compared.
10
CRICOS No. 00213J
a university for the worldreal R 11
Efficiency of the insertion sort algorithm
• By analysing the algorithm’s efficiency, with respect to the length n of
the array and the number of comparisons ‘A[j] > v’ performed, we
found:
• Space efficiency
– No temporary space needed
• Stable
CRICOS No. 00213J
a university for the worldreal R
Selection sort
• The basic idea behind the algorithm is:
1. Find the minimum data item in the list of n elements;
2. Swap the minimum data item with the data item at the first
location in the list;
3. Repeat the above steps for the last n-1 elements.
12
CRICOS No. 00213J
a university for the worldreal R
Selection sort
13
CRICOS No. 00213J
a university for the worldreal R
Selection sort
14
CRICOS No. 00213J
a university for the worldreal R
Selection sort
15
CRICOS No. 00213J
a university for the worldreal R
Selection sort
Demo – Insertion sort with Gypsy fork dance
(0:00 – 6:27)
• Notes:
– Each dancer represents an element in an array
– The basic ideas behind the selection sort and the selection sort
algorithm are the same. However, some details are different.
– What are the differences?
– Can you use the pseudocode notations introduced in Lecture 1
to describe the selection sort algorithm used in the demo?
16
CRICOS No. 00213J
a university for the worldreal R 17
Efficiency of the selection sort algorithm
• By analysing the algorithm’s efficiency, with respect to the length n of
the array and the number of comparisons ‘A[j] > A[min]’ performed, we
found:
• Thus, the efficiency of the selection sort algorithm is O(n2).
• Space efficiency
– No temporary space needed
• Unstable
CRICOS No. 00213J
a university for the worldreal R
Bubble sort
• The basic idea behind the bubble sort is to systematically
exchange pairs of data items in the list that are out of order until
eventually no such pairs remain in the list.
• When all pairs in the list are in order, the list is sorted.
18
CRICOS No. 00213J
a university for the worldreal R
Bubble sort
19
CRICOS No. 00213J
a university for the worldreal R
Bubble sort
20
CRICOS No. 00213J
a university for the worldreal R
Bubble sort
Demo – Insertion sort with Hungarian fork dance
(0:54 – 4:00)
• Notes:
– Each dancer represents an element in an array
– The basic ideas behind the bubble sort algorithm used in the
demo and the bubble sort algorithm on the previous slide are the
same. However, some details are different.
– What are the differences?
– Can you use the pseudocode notations introduced in Lecture 1
to describe the bubble sort algorithm used in the demo?
21
CRICOS No. 00213J
a university for the worldreal R 22
Efficiency of the bubble sort algorithm
• By analysing the algorithm’s efficiency, with respect to the length n of
the array and the number of comparisons ‘A[j+1] > A[j]’ performed, we
found:
• Space efficiency
– No temporary space needed
• Stable
CAB301 Algorithms and Complexity��Lecture 4 – Basic sorting algorithms
Aims of this lecture
References
Sorting algorithms
An application of stable sorting algorithms
Insertion sort
Insertion sort
Insertion sort
Insertion sort
Insertion sort
Efficiency of the insertion sort algorithm
Selection sort
Selection sort
Selection sort
Selection sort
Selection sort
Efficiency of the selection sort algorithm
Bubble sort
Bubble sort
Bubble sort
Bubble sort
Efficiency of the bubble sort algorithm